题解 CF1882E1 - Two Permutations

· · 题解

Easy Version

Easy Version 只需构造任意一种合法方案即可。

容易想到把两个排列分开考虑。

方案 1

对于一个排列，考虑每次让 i+1 接在 i 的后面：

此时我们发现对任意一个长度为 n 的排列都可以在 2n 次操作内做到符合题目要求。

方案 2

考虑对任意排列中两个不同的数 x 和 y，考虑依次对 x,\ y,\ x 操作，

AxByC\to ByCxA\to CxAyB\to AyBxC

就交换了这两个数。

而 1\sim n 的排列可以通过类似冒泡排序的过程在 n 次交换内完成排序，故至多用 3n 次操作。

（个人认为方案 1 更容易想到，方案 2 则是 CodeForces 提供的解法。）

考虑怎么使得两个排列操作次数相同。容易想到添加一段操作序列使得排列不变。

所以只需在操作次数奇偶性相同时用第一种方案补齐；奇偶性不同时则先用第二种方案对长度为奇数的排列操作，使得奇偶性相同，再用第一种方案补齐。否则一定不能成功，证明见题解末。

此时至多再操作 n 次。总共不超过 3n 次（方案 2 则是 4n 次）。

Hard Version

考虑在序列开头加一个 0，再把数列放到环上（即 0 代表序列的开始）：

考虑对一个数进行操作，则容易发现操作在环上等价于 0 与这个数交换之后再进行旋转。

于是问题转化为，在序列 [0,\ p_1,\ p_2,\ \cdots,\ p_n] 上每次将 0 与另一个数交换，使得序列变为 [0,\ 1,\ 2,\ \cdots,\ n],\ [n,\ 0,\ 1,\ 2,\ \cdots,\ n-1],\ [n-1,\ n,\ 0,\ 1,\ 2,\ \cdots,\ n-2],\ \cdots 之一。

此时容易联想到另一个模型：在一个排列上，要用交换使得排列升序，将每个位置指向位置上数应该在的位置，形成一个图，则交换次数至少是 n 减去环的个数。

我们的目标是将这个模型运用到这个问题上。容易想到对每个环，设环的大小为 x：

枚举序列操作的 n 种可能结果，计算最优解即可。

而对于两个序列同时操作，只需求最优解时分别求出奇数步操作和偶数步操作的最优解，然后取奇数偶数中更优的即可（如果不理解，可以参考代码）。

时间复杂度 \Theta(n^2)。

注：文末的代码为了方便，先求出了交换的数值的序列而非位置，再进行转换。

证明

求证：长度为偶数的序列 a_1,\ a_2,\ \cdots,\ a_n 在操作后的逆序对数量奇偶性总是改变。这将得出操作序列的长度的奇偶性是确定的。

设对下标 x 进行操作，则：

综上，逆序对的数量总是改变。

代码

#include<bits/stdc++.h>
using namespace std;
const int INF=100000;

struct SolveResult{
    int minEven,minOdd;
    vector<int> even,odd;
};

vector<int> solveOperations(vector<int> v,vector<int> op){
    vector<int> res;
    for(int x :op){
        int id=0;
        while(v[id]!=x)id++;
        res.push_back(id+1);
        vector<int> newv;
        for(int i=id+1;i<v.size();i++)newv.push_back(v[i]);
        newv.push_back(v[id]);
        for(int i=0;i<id;i++)newv.push_back(v[i]);
        v=newv;
    }
    return res;
}

SolveResult solve(vector<int> v){
    SolveResult res; res.minEven=res.minOdd=INF;
    int n=v.size();
    vector<int> a;
    a.push_back(0);
    for(int i=0;i<n;i++)a.push_back(v[i]);
    for(int k=0;k<=n;k++){
        vector<int> op;
        bool vis[2501]={};
        int pos[2501]={};
        pos[0]=k;
        for(int i=1;i<=k;i++)pos[n-k+i]=i-1;
        for(int i=k+1;i<=n;i++)pos[i-k]=i;
        for(int i=0;i<=n;i++){
            if(vis[i])continue;
            vector<int> t;
            vis[i]=true,t.push_back(i);
            int p=pos[a[i]];
            while(p!=i)t.push_back(p),vis[p]=true,p=pos[a[p]];
            if(i==0){
                for(int j=t.size()-1;j>0;j--)
                    op.push_back(a[t[j]]);
            }
            else{
                if(t.size()==1)continue;
                for(int j=t.size()-1;j>=0;j--)
                    op.push_back(a[t[j]]);
                op.push_back(a[*(t.rbegin())]);
            }
        }
        if(op.size()%2==0&&op.size()<res.minEven){
            res.minEven=op.size();
            res.even=op;
        }
        if(op.size()%2==1&&op.size()<res.minOdd){
            res.minOdd=op.size();
            res.odd=op;
        }
    }
    if(res.minOdd<INF)res.odd=solveOperations(v,res.odd);
    if(res.minEven<INF)res.even=solveOperations(v,res.even);
    return res;
}

int main(){
    int n,m;
    vector<int> a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        a.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x; scanf("%d",&x);
        b.push_back(x);
    }
    SolveResult A=solve(a),B=solve(b);
    vector<int> opA,opB; int step=INF;
    if(A.minEven<=INF&&B.minEven<=INF
        &&(step==INF||step>max(A.minEven,B.minEven)))
        step=max(A.minEven,B.minEven),opA=A.even,opB=B.even;
    if(A.minOdd<=INF&&B.minOdd<=INF
        &&(step==INF||step>max(A.minOdd,B.minOdd)))
        step=max(A.minOdd,B.minOdd),opA=A.odd,opB=B.odd;
    if(step==INF)return printf("-1\n"),0;
    while(opA.size()<opB.size())
        opA.push_back(1),opA.push_back(n);
    while(opA.size()>opB.size())
        opB.push_back(1),opB.push_back(m);
    printf("%d\n",step);
    for(int i=0;i<step;i++)
        printf("%d %d\n",opA[i],opB[i]);
    return 0;
}