CF1385G Columns Swaps-题解

skyx · 2026-10-22 16:33:04 · 题解

CF1385G Columns Swaps-题解

题目分析

对于某个数：

• 在同侧出现了两次，出现的两列必须一个换、一个不换；
• 在两侧分别出现一次，出现的两列必须都换或者都不换；
• 其他情况无解。

那这个条件事实上是啥？类似 P9869 [NOIP2023] 三值逻辑（这个题用扩展状态表示某个位置取反），因为每个列要么被交换，要么不被交换，自然这里把每个列分成两个状态，用扩展域并查集实现。

做完上面，我们得到了若干两两配对的连通块，对每一对互补块（g[i] 和 g[i+n]）：

• 两块里的列互补地覆盖了这组约束涉及的所有列；
• 两种方案都能让最终两行成为排列（这是并查集约束保证的），唯一要优化的就是操作次数，所以选元素少的那个块！

  代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=2e5+10;
int a[N];
int b[N];
int fa[N+N];
vector<int> w1[N];
vector<int> w2[N];

vector<int> g[N+N];

int find(int x)
{
    if(fa[x]==x) return fa[x];
    else return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    fa[x]=y;
}
signed main()
{
    int sti=clock();

//  system("fc d.out e.out");
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=2*n;i++)
        {
            fa[i]=i;
            g[i].clear();

        }
        for(int i=1;i<=n;i++)
        {
            w1[i].clear();
            w2[i].clear();
        }
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            w1[a[i]].push_back(i);
        }
        for(int i=1;i<=n;i++)
        {
            cin>>b[i];
            w2[b[i]].push_back(i);
        }

        bool fl=1;
        for(int i=1;i<=n;i++)
        {
            if(w1[i].size()==2)
            {
                int xx=w1[i][0];
                int yy=w1[i][1];
                merge(xx,yy+n);
                merge(xx+n,yy);
            }
            else if(w1[i].size()==1 && w2[i].size()==1)
            {
                int xx=w1[i][0];
                int yy=w2[i][0];
                merge(xx+n,yy+n);
                merge(xx,yy);
            }
            else if(w2[i].size()==2)
            {
                int xx=w2[i][0];
                int yy=w2[i][1];
                merge(xx,yy+n);
                merge(xx+n,yy);                 
            }
            else
            {
                cout<<-1<<"\n";
                fl=0;break;
            }
        }
        if(fl==0) continue;
        for(int i=1;i<=n;i++)
        {                   
            g[find(i)].push_back(i);
        }
        vector<int> ans;

        for(int i=1;i<=n;i++)
        {                                                                     
            if(g[i].size()<=g[i+n].size())
            {
                for(int v : g[i])
                {
                    ans.push_back(v);
                }                                                                                                                             
            }
            else
            {
                for(int v : g[i+n])
                {
                    ans.push_back(v);
                }                   
            }
        }
        cout<<ans.size()<<"\n";
        for(int i : ans)
        {
            cout<<i<<" ";
        }
        cout<<"\n";
    }
//  cerr<<1.0*(clock()-sti)/CLOCKS_PER_SEC<<endl;
    return 0;
}