CF1882E1 题解
xkcdjerry
·
·
题解
很有意思题，爱来自瓷器。
我们暂时先假装只有一个数组需要我们排序，分别把两个做出来之后再想办法让它们长度匹配即可。
发现一个操作会让整个数组中大部分数的位置改变，对于任何类型的排序都很不友好，考虑想办法降低改变的数量。
这道题可以采用把若干个操作捆绑起来当一个更容易分析的大操作看待。又因为我们在排序，所以尽量往插入或者交换的方向思考。
令 A,B,C 分别表示一个串，1,2 表示单个数字，方括号表示本轮选中方括号内的数进行操作，则：
\text{A[1]B2C}$ -> $\text{B2C1A}
\text{B[2]C1A}$ -> $\text{C1A2B}
\text{C[1]A2B}$ -> $\text{A2B1C}
至此，我们使用三次操作，在不影响其他数位置的情况下交换了 1,2 的位置。
然后由于我们可以使用 n-1 次交换使任何数组有序，我们就可以使用至多 3n-3 次操作将长度为 n 的数组排序。
解决了排序问题之后考虑下一个问题：如何将两个数组的排序序列调整至相同长度。
这里令第一个字符串需要的操作序列为 N，第二个字符串需要的操作序列为 M，不失一般性的，我们假设 |N| \geqslant |M|：
若 |N|-|M| 为偶数，则在 M 末尾不断插入 1,m 直到 |N|=|M|，显然不会影响字符串的有序性。
若 |N|-|M| 为奇数，则两者可以被调整为相等当且仅当 n,m 中至少一个为奇数：
若 n 为奇数，则在 N 的最后插入 n 个 n，否则若 m 为奇数，在 M 的末尾插入 m 个 m。
（|N|-|M| 为奇数且 n,m 均为偶数的情况不可行原因稍后证明）
算一下操作次数：排序一个数列最多需要 \max(|N|,|M|) \leqslant 3 \max(n,m)-3 次操作，若 |N|,|M| 奇偶性不同还最多需要花 \max(n,m) 次操作调整。所以共计操作数 \leqslant 4 \max(n,m) -3，能够通过本题。
考虑对于一个长度为偶数 $n$ 的数组进行一次操作时逆序对数的变化。令 $A,B$ 为长度分别为 $a,b$ 的串，$c$ 为单个数字，则：
交换前数组为 $\text{AcB}$，逆序对数为：
$$Orig=\sum_{i \in A} \sum_{j \in B} [i>j] + \sum_{i \in A} [i>c] + \sum_{i \in B} [i<c]$$
交换后数组为 $\text{BcA}$，逆序对数为：
$$New=\sum_{i \in A} \sum_{j \in B} [i<j] + \sum_{i \in A} [i<c] + \sum_{i \in B} [i>c]$$
又因为数组是排列，故元素两两不同：
$$New=\sum_{i \in A} \sum_{j \in B} 1-[i>j] + \sum_{i \in A} 1-[i>c] + \sum_{i \in B} 1-[i<c]$$
$$New=(ab-\sum_{i \in A} \sum_{j \in B} [i>j])+(a-\sum_{i \in A} [i>c])+(b-\sum_{i \in B} [i<c])$$
$$New=ab+a+b-Orig$$
又因为 $a+1+b=n$，所以 $a,b$ 一奇一偶，即 $ab+a+b$ 为奇数。
由此，得出结论：长度为偶数的序列一次操作后逆序对数量**奇偶翻转**。
那么由于任意序列的逆序对数量均是确定的，显然对于任意的给定的长度为偶数的起始和终止序列，操作数的奇偶性也是确定的，无法通过任何方式进行调整。
---
略加修订的[赛时代码](https://codeforces.com/contest/1882/submission/225148992)：
```c++
#include <cstdio>
#define N 3010
#define M 10010
#define ll long long
int n,m,a[N],b[N];
int s1[M],t1,s2[M],t2;
void swap(int &x,int &y) {int t=x;x=y;y=t;}
int main()
{
scanf("%d%d",&n,&m); t1=t2=0;
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=m;i++) scanf("%d",b+i);
//如果开一个反向索引数组复杂度可以降低到 O(n)
//但是 n^2 能过就别搞复杂玩意了万一写挂了就好玩了
for(int i=1;i<=n;i++)
{
if(a[i]==i) continue;
for(int j=i;j<=n;j++) if(a[j]==i)
{
//根据上面给出的交换方式推算每次操作的数的位置
//那么这段应该不难理解
int l1=i-1,l2=j-i-1,l3=n-j;
s1[t1++]=l1+1;
s1[t1++]=l2+1;
s1[t1++]=l3+1;
swap(a[i],a[j]); //记得更新数组
break;
}
}
//比赛没时间模块化了直接复制粘贴的
//平时还是建议封装个函数方便调试修改
for(int i=1;i<=m;i++)
{
if(b[i]==i) continue;
for(int j=i;j<=m;j++) if(b[j]==i)
{
int l1=i-1,l2=j-i-1,l3=m-j;
s2[t2++]=l1+1;
s2[t2++]=l2+1;
s2[t2++]=l3+1;
swap(b[i],b[j]);
break;
}
}
//调整奇偶性
if(t1%2!=t2%2)
{
if(n&1) for(int i=1;i<=n;i++) s1[t1++]=n;
else if(m&1) for(int i=1;i<=m;i++) s2[t2++]=m;
else return puts("-1"),0;
}
//补足偶数差
while(t1<t2) s1[t1++]=1,s1[t1++]=n;
while(t2<t1) s2[t2++]=1,s2[t2++]=m;
//输出
printf("%d\n",t1);
for(int i=0;i<t1;i++) printf("%d %d\n",s1[i],s2[i]);
}
```