题目链接：https://nanti.jisuanke.com/t/39279
题意：给定n个不同的数表示的序列，定义两种操作：1. 交换前一半和后一半（如果有奇数个，则中间的不管）。2. 交换每个偶数位和它之前的数（如果有奇数个，最后一个不管）。问通过这两种操作，可以得到多少个不同的序列。
思路：典型的打表找规律的题，下次比赛吸取教训。打表的代码如下：
#include<cstdio> using namespace std; int a[10005],b[10005]; int n,ans; bool check(){ bool flag=1; for(int i=1;i<=n;++i) if(a[i]!=b[i]){ flag=0; break; } return flag; } int main(){ for(n=1;n<=30;++n){ int hf=n/2; ans=0; for(int i=1;i<=n;++i) a[i]=i,b[i]=i; while(1){ for(int i=1;i<=hf;++i){ int tmp=b[i]; b[i]=b[n-hf+i]; b[n-hf+i]=tmp; } if(check()) break; ++ans; for(int i=1;i<=n-1;i+=2){ int tmp=b[i]; b[i]=b[i+1]; b[i+1]=tmp; } if(check()) break; ++ans; } printf("%d:%d\n",n,ans+1); } return 0; }
然后就可以找到规律了：
n%4==0: ans=4
n%4==1: if(n==1) ans=1
else ans=2*n
n%4==2: ans=n
n%4==3: if(n==3) ans=6
else ans =12
AC代码：
#include<cstdio> using namespace std; int a[10005],b[10005]; int n,ans; bool check(){ bool flag=1; for(int i=1;i<=n;++i) if(a[i]!=b[i]){ flag=0; break; } return flag; } int main(){ for(n=1;n<=30;++n){ int hf=n/2; ans=0; for(int i=1;i<=n;++i) a[i]=i,b[i]=i; while(1){ for(int i=1;i<=hf;++i){ int tmp=b[i]; b[i]=b[n-hf+i]; b[n-hf+i]=tmp; } if(check()) break; ++ans; for(int i=1;i<=n-1;i+=2){ int tmp=b[i]; b[i]=b[i+1]; b[i+1]=tmp; } if(check()) break; ++ans; } printf("%d:%d\n",n,ans+1); } return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10927161.html
