UVA-12657 Boxes in a Line（数据结构）

本文主要是介绍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

数据结构链表部分的题。
和以前数据结构课上用的链表不太一样，这里是用数组表示的。
用left和right两个数组分别表示当前数字左右的元素。
这个题做了好久，写代码不够严谨。
最开始的给两个数组赋初值的操作，我是看到书上的函数，就照着写了一个一样的，然后因为这个函数，后面的结果出了些问题，找了好久才找到原因。
然后改回了最简单的赋值操作。
后面的各种操作，就是把每个数字的左右指向改变。修改的话用函数实现，没什么难度。不过在进行操作的时候要考虑是否进行过将整个数列颠倒的操作。
在模拟过程中，如果真的将整个数列改变一下，操作量是非常大的。
可以用一个标记来表示，是否进行过这个操作。
然后在进行移动数字的时候，就要考虑，如果移动过，那么，左移右移的操作应该是正好相反的。
我在操作的时候是用l1,l2,r1,r2表示两个操作对象的左右的数字。
但是，这样直接操作的时候要考虑到，如果两个操作对象相邻的问题。这是一个需要注意的地方。
不然的话，会出现混乱。
所以要把相邻的情况拿出来。
当两个数字相邻的时候，作左右移动操作，其实就是交换两个数字。这时候直接用swap函数进行操作即可。

具体代码如下。

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<cstdio>
#define Max 100000+5using namespace std;int Left[Max],Right[Max];void link(int l,int r)
//链接函数
{Right[l]=r;Left[r]=l;
}void swap3(int a,int b)
{int l1,l2,r1,r2;if(Right[a]==b){l1=Left[a];r2=Right[b];Left[b]=l1;Right[a]=r2;Right[b]=a;Left[a]=b;Right[l1]=b;Left[r2]=a;}else if(Left[a]==b){l1=Left[b];r2=Right[a];Left[a]=l1;Right[b]=r2;Left[b]=a;Right[a]=b;Right[l1]=a;Left[r2]=b;}else{l1=Left[a];l2=Left[b];r1=Right[a];r2=Right[b];Right[l1]=b;Left[r1]=b;Right[l2]=a;Left[r2]=a;Right[a]=r2;Left[a]=l2;Right[b]=r1;Left[b]=l1;}
}void r2(int a,int b)//a移动到b的右边
{int l1,l2,r1,r2;if(Left[b]==a){swap3(a,b);}else{l1=Left[a];l2=Left[b];r1=Right[a];r2=Right[b];Right[l1]=r1;Left[r1]=l1;Right[b]=a;Left[r2]=a;Right[a]=r2;Left[a]=b;}
}void l1(int a,int b)//a移动到b的左边
{int l1,l2,r1,r2;if(Right[b]==a)//a是b右边一个{swap3(a,b);}else{l1=Left[a];l2=Left[b];r1=Right[a];r2=Right[b];Right[l2]=r2;Left[r2]=l2;Right[l1]=b;Left[a]=b;Right[b]=a;Left[b]=l1;}
}
int main()
{char c;string s;long long sum,S;bool inverse;int T=0;int i,j,k,t;int n,m,choose,x,y;while(~scanf("%d %d",&n,&m)){T++;//for(i=1; i<=n; i++)//link(i,i+1);for(i=1; i<n+1; i++){Right[i]=i+1;Left[i]=i-1;}Right[0]=1;Left[n+1]=n;for(i=0,inverse=false; i<m; i++){scanf("%d",&choose);if(choose==4){if(inverse)inverse=false;else inverse=true;}else if(choose==3){scanf("%d %d",&x,&y);swap3(x,y);}else{scanf("%d %d",&x,&y);if(inverse){if(choose==1){if(Left[x]!=y)r2(x,y);}else if(choose==2){if(Right[x]!=y)l1(y,x);}}else{if(choose==1){if(Right[x]!=y)l1(y,x);}else if(choose==2){if(Left[x]!=y)r2(x,y);}}}//输出一下数列查看操作是否正确
//            for(k=0,t=Right[0]; k<n+1; k++)//          {//            cout<<t<<" ";//          t=Right[t];//    }//  cout<<endl;//for(k=0,t=Left[n+1]; k<n+1; k++)//{//  cout<<t<<" ";// t=Left[t];//}//cout<<endl<<endl;}for(sum=0,S=0,i=Right[0],j=1; j<=n; j++){if(j%2==1)sum+=i;S+=i;i=Right[i];}if(inverse)
//进行反向操作{if(n%2==0)
//偶数个数的时候，正反向看，奇偶位置的数字刚好错开printf("Case %d: %lld\n",T,S-sum);else
//奇数个数的时候是一样的printf("Case %d: %lld\n",T,sum);}elseprintf("Case %d: %lld\n",T,sum);}return 0;
}