关于这题的坑点，我已经不能再说什么了。。
首先，对于数据上的坑点（也就是调试时要注意的） 大家要注意这么几个
我就简而言之了：对于初始化n为6的队列，要注意的操作
- 3 3 4
- 3 4 3
- 2 1 6
- 2 6 1
如果能把这几组数据过了，想必就没有问题了
但其实，对于我这个小白来说，最坑的是。。。。 最初判断时用的是
while(1)
{
cin>>n>>m;
...........
}
于是不停的TLE
后来改成
while(cin>>n>>m)
{
.......
}
就能过了。。。
最初为了检验程序的错误，还自己编了一个数据生成器，可以一次生成10组数据，就在此送给小伙伴了
代码如下
//移动盒子数据生成器
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout<<"请分别输入盒子数量n以及需要指令的数量q"<<endl;
//freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
srand(346521341);
int q,w;
cin>>q>>w;
for(int j=1;j<=10;j++)
{
cout<<q<<" "<<w<<endl;
for(int i=1;i<=w;i++)
{
int t=rand();
if(t%15==0)
cout<<"4"<<endl;
else if((((t*42+678*j)/572)%(q-1)+1)!=(((t*j+654)/54)%(q-1)+1))
cout<<(t*j)%3+1<<" "<<((t*j+654)/54)%(q-1)+1<<" "<<((t*42+678*j)/572)%(q-1)+1<<endl;
else
cout<<(t*j)%3+1<<" "<<(t*j)%3+2<<" "<<((t*42+678*j)/572)%(q-1)+1<<endl;
}
}
}
建议最开始从小的数据试起，可以拿下面的程序对拍
那么进入正文
其实本题就是一个链表题，原题载于UVA（但UVA上测评也很坑，，没给分数）
写这道题还要注意的就是操作4，可以通过加标记的方法来减短运行时间，因为经过一次操作4后左右顺序会对调，会对操作1 2造成影响，但其实只要几个判断，比如，操作4一次以后，原本往左放就变成往右放，这点在代码里有所处理。
那么代码如下，注释就敲在代码里：
//移动盒子
#include <bits/stdc++.h>
using namespace std;
struct node
{
int right,left;
} a[100005];
void link(int x,int y)//linx操作可以把两个点连起来
{
a[x].right=y;
a[y].left=x;
};
void sc(int t)
{
link(a[t].left,a[t].right);//这步很重要哦
a[t].left=0;a[t].right=0;
}
void addleft(int x,int y)// a[y].left x y
{
sc(x);//一定要先把要转移的点删除
link(a[y].left,x);
link(x,y);
}
void addright(int x,int y)// y x a[y].right
{
sc(x);
link(x,a[y].right);
link(y,x);
}
void achange(int x,int y)// l1 x r1 ....l2 y r2
{
int l1=a[x].left,r1=a[x].right,l2=a[y].left,r2=a[y].right;
//下面的两步特判就是来解决 x，y相邻的问题的
if(r1==y)// l1 x y r2
{
sc(x);sc(y);
link(l1,y);
link(y,x);
link(x,r2);
}
else if(r2==x)// l2 y x r1
{
sc(y);sc(x);
link(l2,x);
link(x,y);
link(y,r1);
}
else// l1 x r1 ....l2 y r2
{
link(l1,y);
link(y,r1);
link(l2,x);
link(x,r2);
}
}
long long sum;//因为数据很大，sum要用longlong
int main()
{
//freopen("out.txt","r",stdin);
int jsq=0;
int n=0,m=0;
bool num=0;
while(cin>>n>>m)
{
jsq++;
num=0;
for(int i=0; i<n+1; i++)//通过这一步来建表
link(i,i+1);
for(int i=1; i<=m; i++)
{
int q=0,x1=0,y1=0;
cin>>q;
if(q!=4)
{
cin>>x1>>y1;
if((q==1&&!num)||(q==2&&num))//这几步一定要注意~通过num来标记操作4
addleft(x1,y1);
if((q==1&&num)||(q==2&&!num))
addright(x1,y1);
if(q==3)
achange(x1,y1);
}
else
num=!num;//num就是操作4，在这里通过加标记的方法来处理操作4，因为操作4以后，原本左边的会变成右边，因而用了以上代码
//通过标记的方法处理操作4能够减短运行时间
// for(int i=a[0].right; i!=n+1; i=a[i].right) cout<<i<<" "; cout<<endl;
}
sum=0;
bool t=0;//通过t来判断奇数偶数
for(int i=a[0].right; i!=n+1; i=a[i].right)
{
if(!t)
sum+=i;
t=!t;
}
if(num&&n%2==0)//如果队列是奇数项并且操作4的数量也为奇数
sum=(long long)n*(n+1)/2-sum;
cout<<"Case "<<jsq<<": "<<sum<<endl;
}
}
话说终于打完了
我去吃饭了上课了
