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
1 /* 2 Uva 12657 3 双向链表 4 */ 5 #include<iostream> 6 #include<cstdio> 7 #include<algorithm>//swap函数在其内部 8 using namespace std; 9 const int maxn = 100000 + 5; 10 int r[maxn], l[maxn]; 11 void link(int x, int y) 12 { 13 r[x] = y, l[y] = x; 14 } 15 int main() 16 { 17 int n, signify, kase = 0; 18 while (scanf("%d%d", &n, &signify) == 2) 19 { 20 for (int i = 1; i <= n; i++) 21 { 22 l[i] = i - 1; 23 r[i] = (i + 1) % (n + 1); 24 } 25 r[0] = 1; 26 l[0] = n; 27 int op, x, y, mark = 0; 28 while (signify--) 29 { 30 scanf("%d", &op); 31 if (op == 4)mark = !mark; 32 else 33 { 34 scanf("%d%d", &x, &y ); 35 if (op == 3 && r[y] == x)swap(x, y);//确保x在y的左边,统一一下，后面方便处理 36 if (op != 3 && mark)op = 3 - op; 37 if (op == 1 && x == l[y])continue; 38 if (op == 2 && x == r[y])continue; 39 int lx = l[x], rx = r[x], ly = l[y], ry = r[y];//在连接节点的过程中，原始值会发生改变l[x],r[x]之类的会因为link函数发生改变，会导致之后系列的连接出错，所以要存储其初始值 40 if (op == 1) 41 { 42 link(lx, rx);//x的上一个节点和下一个节点形成双向链表 43 link(ly, x);//y的上一个节点和x形成双向链表 44 link(x, y);//y的上一个节点和y形成双向链表 45 } 46 else if (op == 2) 47 { 48 link(lx, rx); 49 link(x, ry); 50 link(y, x); 51 } 52 else if (op == 3) 53 { 54 if (r[x] == y) { link(lx, y); link(y, x); link(x, ry); } 55 else { link(lx, y); link(y, rx); link(ly, x); link(x, ry); } 56 } 57 } 58 } 59 int b = 0; 60 long long ans = 0; 61 for (int i = 1; i <= n; i++) 62 { 63 b = r[b]; 64 if (i % 2 == 1)ans += b; 65 } 66 if (mark && n % 2 == 0)ans = (long long)(n * ((long long)n + 1)) / 2 - ans;//考虑n的奇偶数 67 printf("Case %d: %lld\n", ++kase, ans); 68 } 69 70 return 0; 71 }