UVa12657 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.
1.第一遍读题，感觉很懵，顺便看了看右边的解析，知道了要用双向链表。由于在上一个题刚刚复习了单向链表，自己手动打板子，很快写了模板，套上题目，发现一个问题：我们每一次都要去找链表中的x和y的位置，这样每次都有小于1e5的线性遍历，应该会超时。交了一发，果断TLE。但是测试了样例和下面会提到的“坑”，也都是对的。有想法的小伙伴可以去看看。代码链接
2.看了看双向链表的数组模拟，还是感觉不对劲，每一个节点存的值还是会慢慢变化，当我们需要根据值来交换值的位置时，仍然要遍历去找？一头雾水ing
3.读LRJ代码，读了两遍，看懂了链表的初始化以及对于操作四的处理（这点是非常的佩服，因为我也想着怎么高效处理这个麻烦的家伙）。Link函数，下面的一堆调用Link函数以及op==3时的swap（），都还不懂
4.自己在纸上模拟了一下数组版的双向链表，发现了一个根本问题，由于链表初始化时每一个节点的权值刚好和对应的位置节点是相等的，因此，只需要保存前后的位置，每个位置保存的下一个位置刚好是下个位置，也是它的权值。上面的疑惑之一解决
5.按样例一的第一个操作来，如果把y放在x的左边，我们发现需要1的左节点left[1]=0,需要1的右节点right[1]=2;需要4的左节点left[4]=3。都找到之后，由于这样的双向链表不必考虑更改连接点时前后节点（而指针链表必须考虑）。所以我们之间重新连就行了
6.（接上）节点0的操作：right[0]=2，left[2]=0;节点1和3操作：left[1]=3，right[3]=1;节点4操作：left[4]=1，right[1]=4。我们再看看Link() 函数的形式，不难看出它这里存在的意义！又解决了一个疑惑，感觉可以写了，自己写了交一发，WA
7.还是看不懂swap（）是干啥的，没办法了去求助博客。几乎所有的博客下面都写着当x、y相邻时，操作三需要特判。于是自己去写了一下，交了还是WA，按书上来改点东西，连WA四次，月下无限WA！！！
8.晚上继续看，正好看到一篇博客和我写的很相似，就看了一下，以为是我调用Link函数的顺序出了毛病，但我也不确定是不是需要顺序。就这样交了，然后AC。莫名其妙，真的莫名其妙！（博客链接）
PS:在遍历求奇数和时，我刚开始并没有看懂LRJ老师的方法（意思是如果最后的flag表示需要倒序求奇数和，就拿总和减去顺序求的奇数和），而是自己写了一个，因为我们没用到left啊，刚好left求倒序的和，它不香吗？
代码：(可以优化长度，但是我觉得还是简单易懂重要）
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+10;
int left1[maxn],right1[maxn];
void Link(int l,int r){
right1[l]=r;
left1[r]=l;
}
int main(){
int n,m,t,x,y,c=0;
while(scanf("%d%d",&n,&t)!=EOF){
int flag=0;
for(int i=1;i<=n;i++){
left1[i]=i-1;
right1[i]=(i+1)%(n+1); ///这里有必要去了解一下，你会发现0节点（head节点）刚好和最后一个节点是相互连起来的
}
left1[0]=n;
right1[0]=1;
while(t--){
scanf("%d",&m);
if(m==4){
flag=!flag;
continue;
}
if(flag&&m<=2) m=3-m;
if(m==1){
scanf("%d%d",&x,&y);
if(left1[y]==x) continue;
int lx=left1[x],rx=right1[x],ly=left1[y];
Link(lx,rx);
Link(ly,x);
Link(x,y);
}else if(m==2){
scanf("%d%d",&x,&y);
if(right1[y]==x) continue;
int lx=left1[x],rx=right1[x],ry=right1[y];
Link(lx,rx);
Link(x,ry);
Link(y,x);
}else if(m==3){
scanf("%d%d",&x,&y);
int lx=left1[x],rx=right1[x],ly=left1[y],ry=right1[y];
if(rx==y){
Link(lx,y);
Link(y,x);
Link(x,ry);
}else if(lx==y){
Link(y,rx);
Link(ly,x);
Link(x,y);
}else{
Link(y,rx);
Link(ly,x);
Link(lx,y);
Link(x,ry);
}
}
}
long long ans=0;
int t=0;
if(flag){
for(int i=1;i<=n;i++){
t=left1[t];
if(i&1) ans+=t;
}
}else{
for(int i=1;i<=n;i++){
t=right1[t];
if(i&1) ans+=t;
}
}
printf("Case %d: %lld\n",++c,ans);
}
return 0;
}