前记
第一篇黑题题解。难调。好写。码量不大。
Description
给定一个大小为 n n n 的排列 p p p，选择一个 k k k，对 p p p 执行操作若干次使得 p i = i p_i=i pi=i。
每次操作有两个参数 i , j i,j i,j 表示将从 p i p_i pi 开始的连续 k k k 个数从 p p p 中取出，再插入此时 p p p 中第 j − 1 j-1 j−1 和第 j j j 个数之间。
如， p = [ 1 , 2 , 3 , 4 , 5 ] p=[1,2,3,4,5] p=[1,2,3,4,5]， k k k 取 3 3 3，依次执行操作 ( 2 , 1 ) (2,1) (2,1)、 ( 3 , 2 ) (3,2) (3,2)：
将 [ 2 , 3 , 4 ] [2,3,4] [2,3,4] 取出，此时 p = [ 1 , 5 ] p=[1,5] p=[1,5]，在将 [ 2 , 3 , 4 ] [2,3,4] [2,3,4] 放在第 0 0 0 个数和第 1 1 1 个数之间（即开头），操作完成后 p = [ 2 , 3 , 4 , 1 , 5 ] p=[2,3,4,1,5] p=[2,3,4,1,5]。
再执行 ( 3 , 2 ) (3,2) (3,2)， p = [ 2 , 4 , 1 , 5 , 3 ] p=[2,4,1,5,3] p=[2,4,1,5,3]。
Solution
结论： k ≥ n − 3 k\ge n-3 k≥n−3。
可通过打表瞎猜得出。
实际上不一定要得出这个结论，因为题目要求最大化 k k k，所以 k k k 从 n n n 依次递减，越早能构造出越好。
下面证明并构造。
k = n k=n k=n 时
此时序列无论如何操作都不会变，所以要求 p p p 一开始就符合条件。
k = n − 1 k=n-1 k=n−1 时
此时序列每次操作等于循环移一位，要求 p p p 一开始在循环移若干位后能满足条件。
k = n − 2 k=n-2 k=n−2 时
先考虑 n n n 为奇数的情况。
每一次执行 ( 3 , 1 ) (3,1) (3,1) 相当于循环移 2 2 2 位，由于 n n n 为奇数，每个数所在下标奇偶性会改变，所以在执行 n n n 此操作以内能使序列循环移位任意长度。
-
先把 n o w now now（初始为 2 2 2）移到第 1 1 1 位，操作为 ( 3 , 1 ) (3,1) (3,1)
-
在后 n − 1 n-1 n−1 个数中不断移位使 n o w − 1 now-1 now−1 在第 n n n 位，操作为 ( 3 , 2 ) (3,2) (3,2)。
-
循环移一次，使得 n o w now now 接在 n o w − 1 now-1 now−1 的后面，操作为 ( 3 , 1 ) (3,1) (3,1)。
这样 n o w now now 和 n o w − 1 now-1 now−1 就有序了，并且之后不会再分开。
然后 n o w = n o w + 1 now=now+1 now=now+1，重复以上步骤直至 n o w = n + 1 now=n+1 now=n+1 时停止。
再考虑 n n n 为偶数的情况。
每一次执行 ( 3 , 1 ) (3,1) (3,1) 也相当于循环移 2 2 2 位，但无法改变下标奇偶性，所以在上面操作 1 1 1 中， n o w now now 可能无法移到第 1 1 1 位，但一定能移到第 1 1 1 或 n n n 位，因为 1 1 1 和 n n n 奇偶性不同。
如果能移到第 1 1 1 位，就同上操作，否则移到第 n n n 位，再在前 n − 1 n-1 n−1 个数中循环移位直到第 n − 1 n-1 n−1 位为 n o w − 1 now-1 now−1，操作为 ( 2 , 1 ) (2,1) (2,1)，注意此时不再需要操作 3 3 3。
考虑 1 1 1 到 n − 2 n-2 n−2 已排好序，此时有六种情况：
-
n , n − 1 , 1 … n − 2 n,n-1,1\dots n-2 n,n−1,1…n−2
-
n − 1 , n , 1 … n − 2 n-1,n,1\dots n-2 n−1,n,1…n−2
-
n , 1 … n − 2 , n − 1 n,1\dots n-2,n-1 n,1…n−2,n−1
-
n − 1 , 1 … n − 2 , n n-1,1\dots n-2,n n−1,1…n−2,n
-
1 … n − 2 , n , n − 1 1\dots n-2,n,n-1 1…n−2,n,n−1
-
1 … n − 2 , n − 1 , n 1\dots n-2,n-1,n 1…n−2,n−1,n
第 2 2 2 种能移位成第 5 5 5 种，第 4 4 4 种通过操作 ( 2 , 1 ) (2,1) (2,1) 变为第 5 5 5 种。
另外 3 3 3 种无论如何都无法变为第 5 5 5 种。
为什么？
对于操作 ( i , j ) (i,j) (i,j)，若 [ p i , p i + 1 , p i + k − 1 ] [p_i,p_{i+1},p_{i+k-1}] [pi,pi+1,pi+k−1] 会与 [ p x … p y ] [p_x\dots p_y] [px…py] 相对位置发生变化，设原来有 a a a 对逆序对，操作后则会有 k × ( y − x + 1 ) − a k\times(y-x+1)-a k×(y−x+1)−a 对逆序对，发现逆序对数奇偶性不变，因为 k k k 为偶数， k × ( y − x + 1 ) k\times(y-x+1) k×(y−x+1) 也就变为偶数。
因此每次操作无法改变序列内逆序对个数。
若初始时 p p p 就有奇数个逆序对，则最终总会有 1 1 1 个逆序对不会被消去。
那么此时 k = n − 3 k=n-3 k=n−3 才能解决问题。
k = n − 3 k=n-3 k=n−3 时
先将 n n n 移到第 n n n 位。
这里的操作较特殊。
设 x x x 表示 n n n 所在下标。
若 x ≥ k x\ge k x≥k，则将以 n n n 为结尾的长度为 k k k 的段放在末尾即可，操作为 ( x − ( n − 3 ) + 1 , 4 ) (x-(n-3)+1,4) (x−(n−3)+1,4)。
若 x < k x<k x<k，则将以 1 1 1 为开头的长度为 k k k 的段放在末尾，操作为 ( 1 , 4 ) (1,4) (1,4)，即循环移位 3 3 3 位，直到满足上面的条件并执行上面的操作。
然后使 1 … n − 1 1\dots n-1 1…n−1 在前 n − 1 n-1 n−1 位排序，可以发现，此时总长 n − 1 n-1 n−1 为奇数，且 k = n − 3 = ( n − 1 ) − 2 k=n-3=(n-1)-2 k=n−3=(n−1)−2，所以将其视为上面 n n n 为奇数的情况并做操作即可。
注意下面实现时，每次操作暴力改变是 O ( n ) O(n) O(n) 的，但实际上可以用 O ( 1 ) O(1) O(1) 的链表或其他东西维护，使其总时间复杂度降为 O ( n 2 ) O(n^2) O(n2)，但由于 n 2 n^2 n2 次操作严格跑不满，所以 O ( n 3 ) O(n^3) O(n3) 也能过。
Code
#include<bits/stdc++.h>
using namespace std;
int t;
int n,k,cnt,now;
int a[1010],b[1010];
int ans[5000500][2];
void alter(int x,int y){
int s=1;
ans[++cnt][0]=x,ans[cnt][1]=y;
for(int i=1;i<y;i++){
if(s>=x&&s<=x+k) s=x+k;
b[i]=a[s++];
}
for(int i=y;i<=y+k-1;i++){
b[i]=a[x+i-y];
}
for(int i=y+k;i<=n;i++){
if(s>=x&&s<=x+k) s=x+k;
b[i]=a[s++];
}
for(int i=1;i<=n;i++){
a[i]=b[i];
}
}
int find(int x){
for(int i=1;i<=n;i++){
if(a[i]==x) return i;
}
}
void print(){
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++){
cout<<ans[i][0]<<" "<<ans[i][1]<<'\n';
}
}
void solve(){
cin>>n;
cnt=0;
int cnt1=0,cnt2=0;
cin>>a[1];
for(int i=2;i<=n;i++){
cin>>a[i];
if(a[i]!=a[i-1]+1) cnt2++;
for(int j=1;j<i;j++){
if(a[i]<a[j]) cnt1++;
}
}
if(cnt2==0){
cout<<n<<'\n'<<0<<'\n';
return ;
}
if(cnt2==1){
k=n-1;
cout<<k<<'\n';
while(a[1]!=1){
alter(2,1);
}
print();
return ;
}
if(n%2==1){
k=n-2,now=2;
cout<<k<<'\n';
while(now<=n){
while(a[1]!=now){
alter(3,1);
}
while(a[n]!=now-1){
alter(3,2);
}
alter(3,1);
now++;
}
while(a[1]!=1){
alter(3,1);
}
print();
return ;
}
if(cnt1%2==0){
k=n-2,now=2;
cout<<k<<'\n';
int type;
while(now<=n){
type=find(now)%2;
if(type==0){
while(a[n]!=now){
alter(3,1);
}
while(a[n-1]!=now-1){
alter(2,1);
}
now++;
}else{
while(a[1]!=now){
alter(3,1);
}
while(a[n]!=now-1){
alter(3,2);
}
alter(3,1);
now++;
}
}
while(a[1]!=1){
alter(3,1);
}
print();
return ;
}else{
k=n-3,now=2;
cout<<k<<'\n';
while(a[n]!=n){
int x=find(n);
if(x<n-3){
alter(1,4);
}else{
alter(x-(n-3)+1,4);
}
}
while(now<=n-1){
while(a[1]!=now){
alter(3,1);
}
while(a[n-1]!=now-1){
alter(3,2);
}
while(a[1]!=1){
alter(3,1);
}
now++;
}
print();
return ;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while(t--){
solve();
}
return 0;
}