题解：CF1385G Columns Swaps

· · 题解

题意转化

给你一个 2 \times n 的数组，你可以交换任意列上面和下面的数，问能否使其变成两个排列。

显然，对于某个数 x，它一定出现恰好 2 次，否则无解。假设它出现在 r_p 行 p 列和 r_q 行 q 列，f_p、f_q 表示它是否交换，那么最后 r_p \oplus f_p \oplus r_q \oplus f_q = 1。整理得 1 \oplus r_q \oplus r_p = f_q \oplus f_p。可以将每一列视作一个点，在 p 列和 q 列间连一条长为 1 \oplus r_q \oplus r_p 的边。这样，就转换为了一个图论问题。

思路

从一个连通分量的任一节点处开始 bfs 遍历，如果 1 \oplus r_u \oplus r_v \neq f_u \oplus f_v 就将 f_v 取反。如果已经到过了但需要取反就说明无解。

要求最小操作次数，可以将求出的 ans 改变成 e - ans。

易错点

参考代码


#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<ll,ll>;
ll T,n,a[210000],b[210000],cnt[210000],vis[210000],f[210000];
vector<pii> h[210000],o[210000];
vector<int> ans,c;
queue<int> q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;

        ans.clear();
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++)o[i].clear(),h[i].clear(),cnt[i]=vis[i]=0;//多测清空

        for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++;
        for(int i=1;i<=n;i++)cin>>b[i],cnt[b[i]]++;
        bool ok=1;
        for(int i=1;i<=n;i++)if(cnt[i]!=2)ok=0;
        if(!ok){
            cout<<-1<<'\n';
            continue;
        }
        for(int i=1;i<=n;i++){
            o[a[i]].push_back({i,0});
            o[b[i]].push_back({i,1});
        }
        for(int i=1;i<=n;i++){
            pii p=o[i][0],q=o[i][1];
            ll w=1^p.second^q.second;
            h[p.first].push_back({q.first,w});
            h[q.first].push_back({p.first,w});//转换为一条双向边
        }
        for(int s=1;s<=n&&ok;s++){
            if(vis[s])continue;
            c.clear();
            vis[s]=1;f[s]=0;
            q.push(s);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                c.push_back(u);
                for(auto [v,w]:h[u]){
                    int x=f[u]^w;
                    if(!vis[v]){
                        vis[v]=1;f[v]=x;
                        q.push(v);
                    }else if(f[v]!=x){
                        ok=false;//判无解
                    }
                }
            }
            if(!ok)break;
            ll ca=0;
            for(int e:c)ca+=f[e];
            ll cb=(ll)c.size()-ca;
            if(cb<ca)for(int e:c)f[e]^=1;//可以整体取反来最小化答案
            for(int e:c)if(f[e])ans.push_back(e);
        }
        if(!ok){cout<<-1<<'\n';continue;}
        cout<<ans.size()<<'\n';
        for(int x:ans)cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}