题意

Link

有一个排列 \(a\)，你可以执行两种操作：

• A：将最后一个数移到最前面
• B：将第三个数移到最前面

构造一组操作序列将其变为递增排列，输出形如 5a 2b ... 表示执行 \(5\) 次 A 操作再执行 \(2\) 次 B 操作。

思路

很有意思的构造。仔细思考，操作 A 使我们能将原排列变为它的任何一个循环同构^[1]，于是配合操作 B，我们就可以将任意一个数（除最前面两个数）向前移动两步。具体的方法就是假设我们想移的数位置为 \(pos\)，我们同构操作 A 将 \((pos-2,pos-1,pos)\) 移到最前面，经过一次操作 B 变为 \((pos,pos-2,pos-1)\)，然后再通过操作 A 移回去。

到这里我们已经可以处理所有长度为偶数的移动了，那么奇数呢？我们会发现，假设连续执行两次操作 B，我们就可以将任意一个数（除第一个和最后一个数）向前移动一步。具体还是仿照之前那样将 \((pos-1,pos,pos+1)\) 移到最前面，执行两次 B，就会变成 \((pos,pos+1,pos-1)\)，再移回去。

有个问题，移动之后 \(pos-1\) 和 \(pos+1\) 的相对顺序乱了，但这不要紧，我们考虑 \(1,2,\dots,n\) 依次移动每个数的位置，我们只要确保每次操作不影响小于 \(a[pos]\) 的数就行，而当我们需要 \(pos\) 和 \(pos-1\) 交换位置时\(a[pos-1]\) 肯定是大于 \(a[pos]\) 的，因此这不影响。

到了最后两个数时，会有两种情况，第一种是 \(a[n-1]=n-1,a[n]=n\)，说明排序好了；另外一种是 \(a[n-1]=n,a[n]=n-1\)，但这个时候我们无法用之前的办法来移动一步，因为此时可以动的数少于 \(3\) 个，此时应该用移动两步的方法将 \(n\) 移到最前面，再用 \(n-1\) 次操作 A 将后面的移到前面来，完成排序；但如果 \(n\) 前面有奇数个数，则无法用移动两步的方法移到最前面，说明无解。

代码

不要忘了特判 \(n\leq 2\) 的情况。

另外注意操作 A 次数要模 \(n\)，操作 B 次数要模 \(3\)。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=2e3+5;
int n,a[MAXN];
vector<pii>opt,ans;
inline void shift1(int pos){
    assert(2<=pos && pos<=n-1);
    int prelen=pos-2;
    if(prelen>0) opt.emplace_back(1,n-prelen);
    opt.emplace_back(2,2);
    if(prelen>0) opt.emplace_back(1,prelen);

    int x=a[pos-1],y=a[pos],z=a[pos+1];
    a[pos-1]=y;a[pos]=z;a[pos+1]=x;
}
inline void shift2(int pos){
    assert(3<=pos);
    int prelen=pos-3;
    if(prelen>0) opt.emplace_back(1,n-prelen);
    opt.emplace_back(2,1);
    if(prelen>0) opt.emplace_back(1,prelen);

    int x=a[pos-2],y=a[pos-1],z=a[pos];
    a[pos-2]=z;a[pos-1]=x;a[pos]=y;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(n==1){
        puts("0");
        return 0;
    }
    if(n==2){
        if(a[1]==1 && a[2]==2) puts("0");
        else puts("1\n1a");
        return 0;
    }
    int pos;
    for(int num=1;num<=n-2;num++){
        for(int i=1;i<=n;i++)
            if(a[i]==num){pos=i;break;}
        assert(pos>=num);
        if(pos==num) continue;
        while(pos-num>=2){
            shift2(pos);
            pos-=2;
        }
        if(pos>num){
            shift1(pos);
            pos-=1;
        }
        assert(pos==num);
    }
    if(a[n-1]==n){
        pos=n-1;
        if((pos-1)%2==1){
            puts("NIE DA SIE");
            return 0;
        }
        else{
            while(pos!=1){
                shift2(pos);
                pos-=2;
            }
            opt.emplace_back(1,n-1);
        }
    }
    for(auto it:opt){
        if(ans.empty() || ans.back().first!=it.first) ans.push_back(it);
        else ans.back().second+=it.second;
        if(ans.back().first==1 && ans.back().second>=n){
            ans.back().second%=n;
            if(ans.back().second==0) ans.pop_back();
        }
        else if(ans.back().first==2 && ans.back().second>=3){
            ans.back().second%=3;
            if(ans.back().second==0) ans.pop_back();
        }
    }
    cout<<ans.size()<<endl;
    for(auto it:ans){
        cout<<it.second<<(it.first==1?'a':'b')<<' ';
    }
    return 0;
}