CF1672F2 题解

· · 题解

CF1672F2 题解

思路分析

先考虑如何计算一个 \{a_i\} 的排列 \{b_i\} 的权值：对于个 i，建立有向边 a_i\to b_i，得到一张有向图 \mathbf G。

定义 \operatorname{cyc}(\mathbf G) 表示 \mathbf G 的最大环拆分的大小，即把 \mathbf G 拆成尽可能多的环使得每条边都恰好在一个环中时拆分成环的数量。

注意到如下的观察：

观察一：

那么 \{b_i\} 的权值等于 n-\operatorname{cyc}(\mathbf G)。

证明如下：

注意到交换 (b_i,b_j) 等价于交换 a_i\to b_i 和 a_i\to b_j 的终点，我们的目标就是使得 \mathbf G 中产生 n 个环。

而一次操作可以根据 b_i,b_j 在 \operatorname{cyc(\mathbf G)} 对应的分解中分成是否在同一个环中的两种情况。

由上图可得，只要 b_i,b_j 在同一个环中，无论如何 \mathbf G 中的环数会 +1，而如果 b_i,b_j 不在同一个环中，那么 \mathbf G 中的环数一定会 -1。

因此对于任意的大小为 k 的环分解，至少需要操作 n-k 次，而不断操作两个相邻的 b_i,b_j 给了我们一种操作 n-k 次的方法。

综上所述，将 \{b_i\} 还原至少需要 n-\operatorname{cyc}(\mathbf G) 次操作。

那么原问题就转化为了最小化 \operatorname{cyc}(\mathbf G) 的问题。

记 cnt_x 为 x 在 \{a_i\} 中的出现次数。

注意到如下的观察：

观察二：

对于所有 \mathbf G 和正整数 x\in [1,n]，\operatorname{cyc}(\mathbf G)\ge cnt_{x}。

事实上 cnt_x 等于 \mathbf G 中 x 的入度和出度，那么原命题可以等价于证明：

对于每个 \mathbf G 的最大环拆分，不存在一个环经过某个 x 两次。

而根据最大环拆分的定义，经过 x 两次的环会在最大环拆分中拆成两个环，因此原命题得证。

我们假设 \{a_i\} 中的众数 m 出现了 c 次，根据观察二，那么答案 \ge n-c。

猜测答案 =n-c，即我们需要构造一个 \mathbf G 使得 \operatorname{cyc}(\mathbf G)=c。

考虑什么时候 \operatorname{cyc}(\mathbf G)=c，注意到如下的观察：

观察三：

证明如下： 1. 证 $\operatorname{cyc}(\mathbf G)=c \implies \operatorname{cycle}(\mathbf G-\mathbf G_m)=0$： 考虑逆否命题 $\operatorname{cycle}(\mathbf G-\mathbf G_m)>0\implies \operatorname{cyc}(\mathbf G)>c $。 那么考虑 $\operatorname{cycle}(\mathbf G-\mathbf G_m)$ 中的一个环 $\mathbf C$：在子图 $\mathbf G-\mathbf C$ 中，最大的度（等价于众数的出现个数）依然是 $c$，根据观察二，得到 $\operatorname{cyc}(\mathbf G-\mathbf C)\ge c$。 所以 $\operatorname{cyc}(\mathbf G)=\operatorname{cyc}(\mathbf G-\mathbf C)+1\ge c+1>c$。 2. 证 $\operatorname{cycle}(\mathbf G-\mathbf G_m)=0\implies \operatorname{cyc}(\mathbf G)=c$。 考虑逆否命题 $\operatorname{cyc}(\mathbf G)>c \implies \operatorname{cycle}(\mathbf G-\mathbf G_m)>0$。 由于抽屉原理，在 $\operatorname{cyc}(\mathbf G)$ 个环中必然至少有一个不经过 $m$，那么这个环的存在会使得 $\operatorname{cycle}(\mathbf G-\mathbf G_m)>0$。

运用观察三即可解决本题：对 \mathbf G-\mathbf G_m 进行拓扑排序，如果存在环说明不是最优解，否则是最优解。

时间复杂度 \Theta(n)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
int a[MAXN],b[MAXN],cnt[MAXN],deg[MAXN];
vector <int> G[MAXN];
inline void solve() {
    int n,u=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) deg[i]=0,cnt[i]=0,G[i].clear();
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),++cnt[a[i]];
    for(int i=1;i<=n;++i) scanf("%d",&b[i]);
    for(int i=1;i<=n;++i) if(cnt[a[i]]>cnt[a[u]]) u=i;
    for(int i=1;i<=n;++i) {
        if(a[i]==a[u]||b[i]==a[u]) continue;
        G[a[i]].push_back(b[i]);
        ++deg[b[i]];
    }
    queue <int> q;
    for(int i=1;i<=n;++i) if(!deg[i]) q.push(i);
    while(!q.empty()) {
        int p=q.front(); q.pop();
        for(int v:G[p]) {
            --deg[v];
            if(!deg[v]) q.push(v);
        }
    }
    for(int i=1;i<=n;++i) {
        if(deg[i]) {
            puts("WA");
            return ;
        }
    }
    puts("AC");
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}