P3516 [POI2011]PRZ-Shift
Description
题目链接：P3516
给定一个长度为 n 的排列，有两种操作：
- (a) 将最后一个数移到最前面。
- (b) 把第三个数移到最前面。
连续 k 个操作可以合并成一块，表示为 ka 或 kb，要求输出一个长度小于 n^2 操作序列使得进行操作后排列变为 1,2,3,dots,n。
无解输出 NIE。
1leq n leq 2000
Solution
这里提供一个船新做法，可能会跑得快点。
考虑在前 i-1 个数字已经有序排列的情况下，如何把数 i 移动到第 i 个位置。
- 第 i 个数字已经在第 i 个位置了，那么不需要动。
- 第 i 个数字必定在第 j 个位置，其中 j>ii 个数字移动到位置 1，然后每次执行 2 次 a，再做一次 b，这样不断往复就可以把前 i-1 个数字移动到最末尾，此时再做 i-1 次 a 即可。
然后最后可能会尴尬的剩下两个数，比如说下面的数据：
代码语言：javascript复制8
1 2 3 4 5 6 8 7我们发现：可以做两次 a，然后再做一次 b，即可实现将一个数向左移动两个单位，那么针对上面的数据，如果 n 是奇数，肯定无解，如果是偶数，可以用上面的规律移动即可。
然后细节可能有点多，需要细心点。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=2010;
int n,a[N<<1],b[N],s[5],p[N<<1],h;
#define P pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<P> Ans,F;
I void Move(CI t,CI x){//模拟移动，把他拉成一个环，做到 O(1) 模拟。
RI i;if(t==1) (h =n-x)%=n;
else{
for(i=3-x 1;i<=3;i ) p[i-(3-x)]=a[h i];for(i=1;i<=3-x;i ) p[x i]=a[h i];
for(i=1;i<=3;i ) a[h i]=p[i];for(i=1;i<=3;i ) a[(h n i)%(2*n)]=p[i];
}
}
int main(){
RI i,j,k,t;for(read(n),i=1;i<=n;i ) read(a[i]),b[i]=a[i];for(i=n 1;i<=2*n;i ) a[i]=a[i-n];
for(i=1;i<=n-2;i ){
for(j=1;j<=n;j ) if(a[h j]==i) break ;
if(j==i) continue ;
k=i-1,!k&&(k=n),t=0;if(j>1) Ans.push_back(MP(1,n-j 1)),k =n-j 1,Move(1,n-j 1);
k%=n,!k&&(k=n),swap(j,k);W(j 2<=n) Ans.push_back(MP(1,2)),Move(1,2),Ans.push_back(MP(2,1)),Move(2,1),j =2,t ;
if(j 1<=n) Ans.push_back(MP(1,1)),Move(1,1),Ans.push_back(MP(2,2)),Move(2,2),j ,t ;//注意判断边界
Ans.push_back(MP(1,i-1)),Move(1,i-1);
}for(i=n-1;i<=n;i ) s[i-(n-2)]=a[h i]-(n-2);for(i=1;i<=2;i ) a[i]=s[i];if(a[1]==2&&a[2]==1){
if(n&1) return puts("NIE"),0;
for(Ans.push_back(MP(1,2)),i=n/2-1;i>=1;i--) Ans.push_back(MP(1,2)),Ans.push_back(MP(2,1));Ans.push_back(MP(1,n-1));//如果出现最后两个不符情况
}for(i=0;i<Ans.size();){
j=i 1;W(j<Ans.size()&&Ans[j].fi==Ans[i].fi) Ans[i].se =Ans[j].se,j ;if(Ans[i].fi&1) Ans[i].se%=n;else Ans[i].se%=3;
Ans[i].se&&(F.push_back(Ans[i]),0);i=j;//合并输出
}writeln(F.size());for(auto i:F) write(i.se),pc(i.fi 'a'-1),pc(' ');
return pc('n'),0;
}
