【题解】P8210 [THUPC2022 初赛] 造计算机

· · 题解

这题本人曾经在去年 6 月搬到过联考，而且是在最小化 m 的前提下最小化 k 的加强版。

首先特判所有数已经归位的情况，这时 m=0。其余情况下都有 m=2（m=1 的话你把 n+1 交换到前 n 个位置之后就回不去了）。

以下的「Solution 1」为本题做法（你可以在 Matrix 67 的博客 里面找到本题），「Solution 2」为最小化 k 的做法。代码是最小化了 k 的。

该问题最早出现于 Futurama 第 6 季第 10 集 The Prisoner of Benda。（虽然出题人并没有看过）

下面将交换 a_i,a_j 的操作记为 (ij)。记 x=n+1,y=n+2。

Solution 1

原动画中给出了如下的构造解：

将排列 a 分解为多个非空的环之积，考虑分别处理每个环。不失一般性地，我们考虑 a=[2,\cdots n,1]，对此进行操作：(1x)\to(2y)\to(3y)\to(4y)\cdots\to(ny)\to(2x)\to(1y)。在处理完每个环之后，x,y 的位置可能互换，此时我们需要再做 (xy)。

设 a 为 r 个非空的环之积，环长之和为 m，则其需要 m+2r+(r \bmod 2) 次操作。这在环数大于 2 时不是最优解。期望得分 64 分。

Solution 2

这篇论文 给出了最优构造（如果你想要阅读原论文的话，注意此处的操作是自左向右执行的，而论文中是从右向左执行的）：

考虑将原排列分解为多个非空的环 C_i 之积，每个环形如：

\begin{pmatrix} a_1,a_2,a_3,\cdots a_k\\ a_k,a_1,a_2,\cdots a_{k-1} \end{pmatrix}

以 C_1 为例，我们定义：

进行操作：

&F_r(y)\to F_{r-1}(y)\to \cdots\to F_{2}(y)\\ \to & \left[(a_1x)\to G_1(y)\to(a_k x)\right] \\ \to &G_2(x)\to G_3(x)\to \cdots \to G_r(x) \end{aligned}

设 a 为 r 个非空的环之积，环长之和为 m，则其需要 m+r+2 次操作。

其正确性容易验证。我们下面证明这个解是最优的。

证明

首先我们只保留环中的元素，那些不用换位置的元素我们忽略。

假设 m+r+2 的解不是最优，那么操作数 t<m+r+2。通过考虑置换的奇偶性（即逆序对个数的奇偶性）我们可以发现 t\neq m+r+1，于是我们有 t\leq m+r。

另一方面，对于每个元素，它的初始位置与最终位置不同，一定至少被交换过一次。因此 t\geq m。

进一步地，考虑第一个环 C_1=\begin{pmatrix} a_1,a_2,a_3,\cdots a_k\\ a_k,a_1,a_2,\cdots a_{k-1}\end{pmatrix}，我们考虑环中最后一次被操作到的元素，它一定是与 x 或 y 交换，且把位于这个元素处的、不属于 C_1 的东西扔出去；在这个交换之前，它一定与 x,y 中的一个交换过一次。其余环类似。于是对于每个环，它至少会带来一次额外的操作，于是我们有 t\geq m+r。

综上，t=m+r，且不可能出现操作 (xy)。

类似地，对于每个环，我们考虑环中第一次被操作到的元素，它同样会被交换了两次。于是对于每个环，它首次操作到的元素和最后一次被操作到的元素是同一个。

总结一下，对于环 C_1，它有以下性质：

其余环也有类似性质。

现在对于每个环 C_i，定义 N_i 为对其首次操作与最后一次操作之间（不含）的操作数。

不失一般性地，我们：

现在考虑 (a_ky) 与 (a_kx) 之间（含）的所有包含 y 的操作，记作 M。下面我们用反证法证明 M 一定包含 C_1 以外的元素。

假设 M 中只包含 C_1 中的元素。由于我们需要对于 i=1,2,\cdots k-1 把 a_{i+1} 移到 a_i，以下操作必须按照如下顺序执行：

(a_ky),(a_{k-1}y),\cdots (a_1y)

此时 a_1 到达不了 a_k，矛盾。

现在假设 (hy)\in M,h\notin C_1,h\in C_j，而 (a_my) 为 M 中紧接在 (hy) 之前的操作。显然我们的操作不能把 a_m 最终送到 h，h 应当在 (a_kx),(a_ky) 之间出现两次，于是 N_j<N_1，矛盾。证毕。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int getint(){ int x;scanf("%d",&x);return x; }
int a[N];
bool vis[N];
vector<int>r[N];int cnt=0;
vector<pair<int,int> >ans;
void swp(int x,int y){
    ans.emplace_back(min(x,y),max(x,y));
    swap(a[x],a[y]);
}

int main(){
    int n=getint();
    for(int i=1;i<=n;i++)a[i]=getint();
    a[n+1]=n+1;a[n+2]=n+2;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int u=i;
            while(!vis[u]){
                vis[u]=1;
                r[cnt].push_back(u);
                u=a[u];
            }
            // reverse(r[cnt].begin(),r[cnt].end());
            ++cnt;
        }
    }
    vector<int>cy;
    for(int i=0;i<cnt;i++)if(r[i].size()>1)cy.push_back(i);
    if(cy.empty())return puts("0 0"),0;

    for(int i=cy.size()-1;i;--i)swp(r[cy[i]].back(),n+2);
    swp(r[cy[0]].back(),n+1);
    for(int i:r[cy[0]])swp(i,n+2);
    swp(r[cy[0]].front(),n+1);
    for(int i=1;i<cy.size();i++)for(int j:r[cy[i]])swp(j,n+1);
    swp(n+1,n+2);

    printf("%d %d\n",2,(int)ans.size());
    for(auto i:ans)
        printf("%d %d\n",i.first,i.second);
    // for(int i=1;i<=n+2;i++)cerr<<"> "<<a[i];cerr<<endl;
    return 0;
}