链接
题意
给出一段长度为$n$(奇数)的$[1,n]$序列，让你每次可以对前缀奇数长度的序列进行操作，问是否能够在$\frac{5n}{2}$次操作之内使得这段序列有序。
分析
首先我们这样想，每次我们操作的长度是奇数，那么每个数的下标奇偶性肯定不会改变，那么如果奇数放在偶数位置，或者偶数放在奇数位置肯定一定没有答案。
对前缀操作，那么后缀是不受影响的。那么我们肯定先确定后面的数。那么我们就需要从大的开始操作，在看下给出的$\frac{5n}{2}$那么肯定是让我们 两个一对，让后对这一对进行操作5次让他归位。那么我们假设 a[x]=i,a[y]=i-1,那么我们需要怎么操作那？
首先很明显我们需要将$i$和$i-1$放在一起。那么我们假设找到$i$的位置，将其换到最前面，然后将其倒置到y-1位置，这样他们就连起来了，但是不是我们要的顺序，我们还需要借助一个数使得他变成我们要的顺序，最后换到对应的位置。操作是${x,y-1,y+1,3,i}$。
这里还要说一下，为什么不是直接对$i-1$第一步操作，这样就免掉了换成我们要的那个顺序，因为，$i-1$一定是偶数，我们只能对奇数长度进行操作，
ll n,m;
ll a[maxn];
ll f(ll x){
for(ll i=1;i<=n;i++) if(a[i]==x) return i;
return -1;
}
ll ans[maxn],cnt;
void add(int x){
ans[++cnt]=x;
reverse(a+1,a+1+x);
}
void solve()
{
cnt=0;
cin>>n;
bool flag=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]%2!=i%2){
flag=1;
}
}
if(flag) {
puts("-1");
return ;
}
for(int i=n;i>1;i-=2){
ll x=f(i);
add(x);
ll y=f(i-1);
add(y-1);
add(y+1);
add(3);
add(i);
}
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++)cout<<ans[i]<<" ";
puts("");
}
链接
题意：
你有一行盒子，从左到右依次编号为1,2,3,…,n。你可以执行四种指令：
- X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令）。
- X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令）。
- X Y表示交换盒子X和Y的位置。
- 表示反转整条链。
指令保证合法，即X不等于Y。例如，当n=6时在初始状态下执行1 1 4后，盒子序列为2 3 1 4 5 6。接下来执行2 3 5，盒子序列变成2 1 4 5 3 6。再执行3 1 6，得到2 6 4 5 3 1。最终执行4，得到1 3 5 4 6 2。
分析：
首先我们可以直接用链表模拟这个过程，这个懂，但是每次翻转4操作，我们就得考虑，1和2的对于翻转的左右的判断。
我们看1 2 3 4 5 6 对其操作，1 2 5 变成1 3 4 2 5 6 ,而如果我们对其进行2 2 5，变成1 3 4 5 2 6。
那如果我们对6 5 4 3 2 1进行1 2 5操作变成6 2 4 3 2 1与上面正序操作2 2 5的倒序，是不是一样。所以我们看翻转次数，看左右。
还需要注意的是：
就是如果我们操作的连个数左右相邻那个我们就得特殊考虑：
一下列出一部分情况：a x b a表示x左边连的数，b表示x右边连的数c y d c表示y左边连的数，d表示y右边连的数。
操作1 X Y
就是将 a x b ----c y d变成a b ---- c x y d.
如果原本是这样的axyd那么不用在进行操作了，
如果原本是这样的cyxb那么我们将其变成cxyb
这是正序进行1操作，其他的类比推一下就好了，博主写的比较复杂，没有写函数，写函数的话，要捋得清，不然容易乱。对着题意思路捋一遍这个过程就出来了，再把相邻的特殊判一下。OK
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int dx[] = {
0, 1, -1, 0, 0};
const int dy[] = {
0, 0, 0, 1, -1};
const int dz[] = {
1, -1, 0, 0, 0, 0 };
int day[] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void init(){
}
ll T;
ll n,m;
ll l[maxn],r[maxn];
ll flag=1;
void out(){
///调试BUG用的
/*if(flag){
ll num=0;
for(int i=1;i<=n;i++){
num=r[num];
cout<<num<<" ";
}
cout<<endl<<"*******"<<endl;
}else {
ll num=n+1;
for(int i=1;i<=n;i++){
num=l[num];
cout<<num<<" ";
}
cout<<endl<<"*******"<<endl;
}*/
}
void solve()
{
flag=1;
r[0]=1;
l[n+1]=n;
for(int i=1;i<=n;i++){
l[i]=i-1;
r[i]=i+1;
}
while(m--){
ll op;
cin>>op;
if(op==1){
ll x,y;
cin>>x>>y;
if(flag){
ll a=l[x],b=r[x];
ll c=l[y],d=r[y];
if(b==y) {
out();
continue;
}
if(d==x){
r[c]=x;
l[x]=c;
r[x]=y;
l[y]=x;
r[y]=b;
l[b]=y;
out();
continue;
}
l[b]=a;
r[a]=b;
r[c]=x;
l[x]=c;
r[x]=y;
l[y]=x;
}else {
ll a=l[x],b=r[x];
ll c=l[y],d=r[y];
if(d==x){
out();
continue;
}
if(b==y){
l[d]=x;
r[x]=d;
l[x]=y;
r[y]=x;
l[y]=a;
r[a]=y;
out();
continue;
}
l[b]=a;
r[a]=b;
l[d]=x;
r[x]=d;
l[x]=y;
r[y]=x;
}
}else if(op==2){
ll x,y;
cin>>x>>y;
if(!flag){
ll a=l[x],b=r[x];
ll c=l[y],d=r[y];
if(a==y){
l[b]=y;
r[y]=b;
l[y]=x;
r[x]=y;
l[x]=c;
r[c]=x;
out();
continue;
}
if(b==y) {
out();
continue;
}
l[b]=a;
r[a]=b;
l[y]=x;
r[x]=y;
l[x]=c;
r[c]=x;
}else {
ll a=l[x],b=r[x];
ll c=l[y],d=r[y];
if(d==x){
out();
continue;
}
if(b==y){
l[y]=a;
r[a]=y;
r[y]=x;
l[x]=y;
r[x]=d;
l[d]=x;
out();
continue;
}
l[b]=a;
r[a]=b;
l[x]=y;
r[y]=x;
r[x]=d;
l[d]=x;
}
}else if(op==3){
ll x,y;
cin>>x>>y;
ll a=l[x],b=r[x];
ll c=l[y],d=r[y];
if(d==x){
r[c]=x;
l[x]=c;
r[x]=y;
l[y]=x;
r[y]=b;
l[b]=y;
out();
continue;
}
if(b==y){
r[a]=y;
l[y]=a;
r[y]=x;
l[x]=y;
r[x]=d;
l[d]=x;
out();
continue;
}
l[y]=a;
r[a]=y;
r[y]=b;
l[b]=y;
l[x]=c;
r[c]=x;
l[d]=x;
r[x]=d;
}else if(op==4){
flag=!flag;
}
out();
}
printf("Case %lld: ",++T);
if(flag){
ll num=0,sum=0;
for(int i=1;i<=n;i++){
num=r[num];
if(i%2) sum+=num;
}
cout<<sum<<endl;
}else {
ll num=n+1,sum=0;
for(int i=1;i<=n;i++){
num=l[num];
if(i%2) sum+=num;
}
cout<<sum<<endl;
}
}
int main()
{
init();
//ll t = 1;
/// scanf("%lld",&t);
while(~scanf("%lld%lld",&n,&m))
{
solve();
}
return 0;
}
