第一次接触list 感觉有点坑啊 很多时候感觉很简单但是坑异常的多 要注意指针的指向！
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
int le[1000000];
int rig[1000000];
void link(int l,int r)
{
le[r]=l;
rig[l]=r;
}
void change(int l,int r)//不相邻的 交换 直接重新构建指针
{
int ll=le[l];
int lr=rig[l];
int rl=le[r];
int rr=rig[r];
link(ll,r);
link(r,lr);
link(rl,l);
link(l,rr);
}
void swapp(int a,int b)//相邻的需要注意一下
{
link(le[a],b);
link(a,rig[b]);
link(b,a);
}
int main()
{
int n,m;
int cnt=1;
while(cin>>n>>m)
{
memset(le,0,sizeof(le));
memset(rig,0,sizeof(rig));
for(int i=0;i<=n;i++)
{
link(i,(i+1)%(n+1));
}
int state=0;
for(int i=1;i<=m;i++)
{
int op,a,b;
cin>>op;
if(op==4) state=!state;
else
{
cin>>a>>b;
if(op==3)
{
if(rig[a]==b)
{swapp(a,b);}
else if(le[a]==b)
{swapp(b,a);}
else
{change(a,b);continue;}
}
if(state) op=3-op;
if(op==1)//注意第二个和第三个不能反 如果先进行第三个 那么le[b]就不是我们所期待的了
{
link(le[a],rig[a]);
link(le[b],a);
link(a,b);
}
else if(op==2)//原理同上
{
//cout<<'!'<<endl;
link(le[a],rig[a]);
link(a,rig[b]);
link(b,a);
}
}
/* for(int i=0;i<=n;i++)
cout<<rig[i];
cout<<endl;
for(int i=0;i<=n;i++)
cout<<le[i];*/
}
long long sum=0;
if(state==0)
{
int start=rig[0];
for(int i=1;i<=n/2;i++)
{
sum+=start;
//cout<<start<<endl;
start=rig[rig[start]];
}
if(n%2) sum+=le[0];
}
else
{
int start=le[0];
for(int i=1;i<=n/2;i++)
{
sum+=start;
start=le[le[start]];
}
if(n%2) sum+=rig[0];
}
cout<<"Case "<<cnt++<<':'<<' ';
cout<<sum<<endl;
//int start=0;
/* while(rig[start]!=0)
{
cout<<' '<<rig[start];
start=rig[start];
}*/
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1296543.html
