UVA 12657 Boxes in a Line
You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands: • 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y ) • 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y ) • 3 X Y : swap box X and Y • 4: reverse the whole line. Commands are guaranteed to be valid, i.e. X will be not equal to Y . For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2 Input There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command. Output For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right. Sample Input 6 4 1 1 4 2 3 5 3 1 6 4 6 3 1 1 4 2 3 5 3 1 6 100000 1 4 Sample Output Case 1: 12 Case 2: 9 Case 3: 2500050000
题意：
对链表进行4项操作，分别是 x 移到 y的左边或右边，交换 x， y 和 排列顺序逆转；
思路： 用双向链表对数据进行插入和删除，实现链表的方法有 3 种，一种是list 一种是指针链表，但事实上，这两者都会超时， 因为题目中，需要进行的操作次数有 10^5 而且，n的大小也可能为10^5，所以，很容易超时，数组模拟链表的好处就是能直接通过数字来找出位置，但是，这种情况只有当数据是连续的，比如 1到n这样的数据，才能直接找到位置；数组模拟的过程如果对指针链表的插入删除不熟悉的话，可能会比较难懂，建议先学会指针链表在去学数组模拟链表；除了第 4 个操作，其他操作都是插入删除的操作， 至于 4 这个操作，只需要一个变量去记录一下，如果是倒序的，那么接下来如果还有操作，如果 是1操作，那么 x 移到 y的左边其实就是移到右边，2的操作也是一样的道理，所以只要记录 倒序了几次，判断这个时候的链表是正序的还是倒序的就行；下面给出代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; #define Maxn 100100 int n,m,left[Maxn],right[Maxn]; long long cnt; // 连接两个节点，只需把左边的节点的 right 指向 右边的数，同样的 // 右边的 left 指向 左边的数，如果对指针链表熟悉的话就比较好理解； void link(int L, int R) { right[L] = R; left[R] = L; } void init() { right[0] = 1; left[0] = n; // 注意别忘了给 0 这个部分初始化 for(int i = 1 ; i <= n ; ++i) { left[i] = i - 1; right[i] = (i + 1)%(n + 1); //对 n+1 取余 是为了让最后一位的right[n] = 0; } } void cmd_1_2(int cd,int x,int y,int sg) { // 为了保险，把一个数的左右的值先保存下来 int LX,RX,LY,RY; LX = left[x]; RX = right[x]; LY = left[y]; RY = right[y]; // 如果 sg == -1 说明链表是倒序的，那么如果cd == 1,那么执行 2的操作 // 反过来一样，如果是 2 执行 1的操作 if(sg == -1) cd = 3 - cd; //如果 y，x已经符合操作了就直接返回； if(left[y] == x && cd == 1) return; if(right[y] == x && cd == 2) return; // 把 x 删除，只要把 x 左边的数和右边的数连在一样就行了 link(LX,RX); if(cd == 1) { link(LY,x); link(x,y); } else if(cd == 2) { link(y,x); link(x,RY); } } void Swap(int x,int y) { if(right[x] == y) swap(x,y); // 相邻的数交换，链表会出错，这里统一当 YX这种情况处理 int LX,RX,LY,RY; LX = left[x]; RX = right[x]; LY = left[y]; RY = right[y]; if(right[y] == x) { link(LY,x); link(x,y); link(y,RX); } // 统一的情况，如果没有上面那个swap， else { // 就要写两两种情况； link(LX,y); link(y,RX); link(LY,x); link(x,RY); } } void solve(int sg) { int p = right[0]; // 相当于头指针head cnt = 0; for(int i = 1 ; i <= n ; ++i) { if(i % 2 != 0) cnt+=p; p = right[p]; } if(sg == -1 && n % 2 == 0) cnt = (long long)n*(n+1)/2 - cnt; } int main(void) { int cmd,x,y,sigh,t = 0; while(scanf("%d%d",&n,&m)!=EOF) { memset(left,0,sizeof(left)); memset(right,0,sizeof(right)); sigh = 1; init(); while(m--) { scanf("%d",&cmd); if(cmd == 4) sigh*=(-1); else { scanf("%d%d",&x,&y); if(cmd == 1 || cmd == 2) cmd_1_2(cmd,x,y,sigh); else if(cmd == 3) Swap(x,y); } } solve(sigh); printf("Case %d: %lld\n",++t,cnt); } return 0; }
