令 $m$ 为不超过 $\lfloor \frac{n}{2} \rfloor$ 的最大奇数。
对前一半 $(1 \sim \lfloor \frac{n}{2} \rfloor)$，首先用 $m+1$ 的反转归位，到了当前位置离目标位置小于 $m+1$ 的时候，把他反转到目标 $+m$ 的位置。
对于后半部分，考虑交换任意 $u$ 和 $v$ 的位置。
你考虑同时操作 $m+1$ 和 $m-1$ 可以仅交换 $i$ 和 $i+m$ 位置上的值。
所以，当 $v$ 不等于 $u+m$ 的时候，先把他扔到 $[u,u+m]$ 里，如果他俩奇偶性不同，则执行一次交换让他俩奇偶性相同。
然后，你就直接找到一个中点反转，就能归位了。
题解做法好像反过来了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include<bits/stdc++.h>
using namespace std;
int n,a[1005],cnt;
pair<int,int>b[1000005];
void print(){
for(int i=1;i<=n;++i){
cout<<a[i]<<' ';
if(i%10==0)cout<<endl;
}
cout<<endl;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
if(n>10){
int m=n/4;
if(!(m&1))--m;
for(int i=1;i*2<=n;++i){
int j=i;
while(j<n&&a[j]!=i)++j;
while(j-m>=i){
reverse(a+j-m,a+j+1);
b[++cnt]={j-m,j};j-=m;
}
if(i==j)continue;
int l=i,r=i+m;
if((l-j)&1){
reverse(a+j,a+j+m+1);
b[++cnt]={j,j+m};j+=m;
}
reverse(a+(r+j)/2-(m+1)/2+1,a+(r+j)/2+(m+1)/2+1);
b[++cnt]={(r+j)/2-(m+1)/2+1,(r+j)/2+(m+1)/2};
reverse(a+r-m,a+r+1);
b[++cnt]={r-m,r};
}
for(int i=n;i>=n/2+1;--i){
int j=i;
while(j>1&&a[j]!=i)--j;
while(j+m<=i){
reverse(a+j,a+j+m+1);
b[++cnt]={j,j+m};j+=m;
}
if(j==i)continue;
int l=i-m,r=i,t=0;
if((r-j)&1){
reverse(a+j-m,a+j+1);
b[++cnt]={j-m,j};j-=m;t=1;
}
reverse(a+(l+j)/2-(m+1)/2+1,a+(l+j)/2+(m+1)/2+1);
b[++cnt]={(l+j)/2-(m+1)/2+1,(l+j)/2+(m+1)/2};
reverse(a+l,a+l+m+1);
b[++cnt]={l,l+m};
reverse(a+l+1,a+l+m);
b[++cnt]={l+1,l+m-1};
reverse(a+(l+j)/2-(m+1)/2+1,a+(l+j)/2+(m+1)/2+1);
b[++cnt]={(l+j)/2-(m+1)/2+1,(l+j)/2+(m+1)/2};
if(t)reverse(a+j,a+j+m+1),b[++cnt]={j,j+m};
}
cout<<m<<'\n'<<cnt<<'\n';
for(int i=1;i<=cnt;++i)cout<<b[i].first<<' '<<b[i].second<<'\n';
return 0;
}
cout<<3<<'\n';
for(int i=1;i<=n;++i){
if(a[i]!=i){
int id=i+1;
for(int j=i+1;j<=n;++j)
if(a[j]==i){id=j;break;}
int j=id;
for(j=id;j>=i+3;j-=3){
reverse(a+j-3,a+j+1);
b[++cnt]={j-3,j};
}
for(;j>i;--j){
b[++cnt]={j-1,j};
swap(a[j-1],a[j]);
}
}
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;++i)cout<<b[i].first<<' '<<b[i].second<<'\n';
return 0;
}
|
