题目链接：https://www.luogu.org/problemnew/show/UVA12657
分析：
此题使用手写链表+模拟即可。（其实可以用list，而且更简便，但是会大大的超时）
肯定是不能直接用数组模拟了，因为n，m的大小会达到100000. 然后， 1.可以编写一些辅助函数来设置链接关系。 2.注意 op==3的时候，要对xy相邻的情况进行特判，因为有这种情况 2 1 （头节点） 3 1 2 （尾节点） 3.我们会发现如果反转两次，就相当于没有翻转。如果翻转一次，op=1变为op=2;op=2变为op=1;如果翻转一次，n为奇数时，奇数位置不变，但是n为偶数的时候，奇数变偶数。 （为什么要用双向链表？因为我们需要知道它左边和右边）
代码：
#include<cstdio>
#include<algorithm>
using namespace std
;
const int maxn
=100000+10;
int left
[maxn
],right
[maxn
],inv
;
void link(int L
,int R
)
{
left
[R
]=L
;
right
[L
]=R
;
}
long long number(int n
)
{
int x
=0;
long long total
=0;
for(int i
=1;i
<=n
;i
++)
{
x
=right
[x
];
if(i
%2!=0)total
+=x
;
}
if(inv
!=0&&n
%2==0)total
=(long long)n
*(n
+1)/2-total
;
return total
;
}
int main()
{
int n
,m
,T
=1;
while(scanf("%d %d",&n
,&m
)==2)
{
for(int i
=1;i
<=n
;i
++)
{
left
[i
]=i
-1;
right
[i
]=(i
+1)%(n
+1);
}
right
[0]=1;
left
[0]=n
;
inv
=0;
while(m
--)
{
int order
,X
,Y
;
scanf("%d",&order
);
if(order
==4)
{
inv
=!inv
;
continue;
}
scanf("%d %d",&X
,&Y
);
if(order
==3&&right
[Y
]==X
)swap(X
,Y
);
if(order
!=3&&inv
)order
=3-order
;
if(order
==1&&left
[Y
]==X
)continue;
if(order
==2&&right
[Y
]==X
)continue;
int LX
,RX
,LY
,RY
;
LX
=left
[X
];
RX
=right
[X
];
LY
=left
[Y
];
RY
=right
[Y
];
if(order
==1)
{
link(X
,Y
);
link(LX
,RX
);
link(LY
,X
);
}
else
if(order
==2)
{
link(Y
,X
);
link(LX
,RX
);
link(X
,RY
);
}
else
if(order
==3)
{
if(right
[X
]==Y
)
{
link(LX
,Y
);
link(Y
,X
);
link(X
,RY
);
}
else
{
link(LX
,Y
);
link(Y
,RX
);
link(LY
,X
);
link(X
,RY
);
}
}
}
printf("Case %d: %lld\n",T
++,number(n
));
}
return 0;
}
撒花
~
转载于:https://www.cnblogs.com/vercont/p/10210034.html
相关资源：JAVA上百实例源码以及开源项目
