題意

你有一行盒子，從左到右依次編號(hào)為1, 2, 3,…, n。可以執(zhí)行以下4種指令：
1 X Y表示把盒子X(jué)移動(dòng)到盒子Y左邊（如果X已經(jīng)在Y的左邊則忽略此指令）。
2 X Y表示把盒子X(jué)移動(dòng)到盒子Y右邊（如果X已經(jīng)在Y的右邊則忽略此指令）。
3 X Y表示交換盒子X(jué)和Y的位置。
4 表示反轉(zhuǎn)整條鏈。

思路

雙向鏈表
每次操作只需修改鏈表中的元素指向
另外, 如果程序一直在反轉(zhuǎn)整條鏈, 如果一直操作的話必然復(fù)雜度很高
因?yàn)轭}目只求所有奇數(shù)位置標(biāo)號(hào)之和, 當(dāng)boxnum為奇數(shù), 盒子逆序無(wú)影響
boxnum為偶數(shù)時(shí)才有影響, 再具體判斷即可 . 所以將反轉(zhuǎn)鏈操作用bool標(biāo)記即可

AC代碼

#include <iostream> #include <cstdio> #include <cstring>using namespace std; typedef long long ULL; const int maxn = 100000 + 10; int l[maxn],r[maxn];void link( int left, int right ){r[left] = right;l[right] = left; }int main() {int boxnum, casenum, i;int x, a, b, num = 0;ULL result;bool ok;while( ~scanf("%d%d",&boxnum, &casenum) ){for( i = 1; i <= boxnum; i++ ){l[i] = i - 1;r[i] = ( i + 1 ) % ( boxnum + 1 );}l[0] = boxnum;r[0] = 1;ok = false;while( casenum-- ){scanf("%d",&x);if( x == 4 ){ //反轉(zhuǎn)ok = !ok;continue;}scanf("%d%d",&a,&b);if( x == 3 && r[b] == a ) swap(a,b);if( x != 3 && ok ) x = 3 - x;if( (x == 1 && l[b] == a) || (x == 2 && r[b] == a) ) continue;int la = l[a], ra = r[a], lb = l[b], rb = r[b];if( x == 1 ){link(la, ra);link(a, b);link(lb, a);}else if( x == 2 ){link(la, ra);link(b, a);link(a, rb);}else if( x == 3 ){if( ra == b ){link(la, b);link(b, a);link(a, rb);}else{link(la, b);link(b, ra);link(lb, a);link(a, rb);}}}int t = 0;result = 0;for( int i = 1; i <= boxnum; i++ ){t = r[t];if( i % 2 != 0 ) result += t;}if( ok && boxnum % 2 == 0 )result = (ULL)boxnum*(boxnum+1)/2 - result;//cout << boxnum*(boxnum+1)/2 ;printf("Case %d: %llu\n",++num, result);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/JinxiSui/p/9740611.html

總結(jié)

以上是生活随笔為你收集整理的UVa 12657 - Boxes in a Line ( 双向链表 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。