紫书一移动盒子（Boxes in a Line）

JNzH 2019-01-16 原文

【题目】

　　一行中有 n 个框 1…n 从左到右。你的任务是模拟 4 种命令：
　　•1 X Y：将框 X 左移到 Y（如果 X 已经是 Y 的左边，则忽略）。
　　•2 X Y：将框 X 右移到 Y（如果 X 已经是 Y 的右边，则忽略）。
　　•3 X Y：交换框 X 和 Y。
　　•4：反转整行。
　　命令保证有效，即 X 不等于 Y。
　　例如，如果 n=6，执行 1 1 4 后，该行变为 2 3 1 4 5 6。然后执行 2 3 5，该行变为 2 1 4 5 3 6。然后在执行 3 1 6 后，该行变为 2 6 4 5 3 1。然后在执行 4 之后，行变为 1 3 5 4 6 2。

【输入格式】
　　输入包含不超过10组数据，每组数据第一行为盒子数n和指令m，以下m行每行包含一条指令。
【输出格式】
　　每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。
【输入样例】
　　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
【输出样例】

Case 1: 12
Case 2: 9
Case 3: 2500050000

分析:(双向链表)

运用left数组和right数组来存储某个数左右两边的盒子编号，然后根据输入输出来模拟移动盒子的过程。书上的代码看了之后感觉细节满满Orz，有很多可以学习借鉴的地方。

由于之间链接时的操作较多，书上使用了一个link函数，很是方便，对我来说就很难想到了。。

这个我在后面也理解了好久(扶额..)

1 void link(int L,int R)
2 {
3     right[L]=R;
4     left[R]=L;
5 }

需要注意的有:

1.程序里面的一个的链接顺序不一定要与书上完全一样,一开始我尝试自己写的时候带了一点写链表的谨慎(滑稽),写了发现根书上不一样，但也是正确的

2.新建变量一定要初始化！新建变量一定要初始化！新建变量一定要初始化！　　我一开始本地测试样例出错的时候我看关键部分左看右看都是正确的，找了好久才找出b没有赋初值QAQ..

3.C++的库函数algorithm里面有包括的swap函数(交换函数)，我一开始没有引用这个库函数，而是自己写了一个swap，开始本地测试没有问题，但是在oj上连续WA之后才找到原因。。

更多注意的在下面代码注释里：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAX=100010;
 6 int right[MAX],left[MAX];
 7 void link(int L,int R)
 8 {
 9     right[L]=R;
10     left[R]=L;
11 }
12 int main()
13 {
14     int i,n,m,kase=0;
15     while(scanf("%d%d",&n,&m)==2)
16     {
17         for(i=1;i<=n;i++)
18         {
19             left[i]=i-1;
20             right[i]=(i+1)%(n+1);　　//运用了余数和周期的规律巧妙地使首尾相连
21         }
22         right[0]=1;left[0]=n;
23         int op,X,Y,turn=0;
24         while(m--)
25         {
26             scanf("%d",&op);
27             if(op==4)    turn=!turn;　　　　//根据执行操作4的次数决定是否反转
28             else 
29             {
30                 scanf("%d%d",&X,&Y);
31                 if(op==3&&right[Y]==X)    swap(X,Y);
32                 if(op!=3&&turn)    op=3-op;
33                 if(op==1&&X==left[Y])    continue;　　　　//本来就在左边了，就不用移了
34                 if(op==2&&X==right[Y])    continue;　　　　//同上
35                 
36                 
37                 int LX=left[X],LY=left[Y],RX=right[X],RY=right[Y];
38                 if(op==1)
39                 {
40                     link(LX,RX);link(LY,X);link(X,Y);
41                 }
42                 else if(op==2)
43                 {
44                     link(LX,RX);link(Y,X);link(X,RY);
45                 }
46                 else if(op==3)
47                 {
48                     if(right[X]==Y)    
49                     {
50                         link(LX,Y);link(X,RY);link(Y,X);
51                     }
52                     else 
53                     {
54                         link(LX,Y);link(Y,RX);link(LY,X);link(X,RY);
55                     }
56                 }
57             }
58         }
59         long long ans=0;
60         int b=0;
61         for(i=1;i<=n;i++)
62         {
63             b=right[b];
64             if(i%2!=0) ans+=b;
65         }
66         if(turn&&n%2==0) ans=(long long)n*(n+1)/2-ans;　　　//n奇数情况反转，结果不变。偶数情况用总数减去结果得到的就是奇数项的。
67         printf("Case %d: %lld\n",++kase,ans);
68     }
69     return 0;
70 }