题目大意：给一个1~n的序列，每次操作可以把长度为偶数的序列交换前一半和后一半的位置。求出将这个序列变成升序的步骤。
题目分析：构造求解。
代码如下：
# include# include # include # include # include using namespace std;int a[10005],pos[10005],n;queue L,R;void print(int ans){ printf("%d\n",ans); while(!L.empty()){ printf("%d %d\n",L.front(),R.front()); L.pop(),R.pop(); }}void change(int l,int r){ L.push(l),R.push(r); for(int i=l,j=l+(r-l)/2+1;j<=r;++i,++j){ pos[a[i]]=j,pos[a[j]]=i; swap(a[i],a[j]); }}void solve(){ while(!L.empty()) L.pop(); while(!R.empty()) R.pop(); int l=1,ans=0; while(l<=n) { for(int i=l;i<=n;++i){ if(a[i]==i){ ++l; continue; } ++ans; int p=pos[i]; if(2*p-i-1<=n) change(i,2*p-i-1); else{ if((p-i)&1) change(i,p); else change(i+1,p); } if(a[i]==i) ++l; break; } } print(ans);}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",a+i); pos[a[i]]=i; } solve(); } return 0;}