CF1385G Columns Swaps

_InRedBrother_QWQ_ · 2026-10-21 17:00:36 · 题解

CF1385G Columns Swaps

题意

给定 2 \times n 的表格，每格中有一个值域 [1, n] 的整数。每一列都可以交换，交换第 i 列即意味着，将第 i 列上下两个值交换。问最少交换多少列，使得该表格的第一行与第二行，均构成 [1, n] 的排列。

转化

上下两行均构成排列，即 [1, n] 中每个整数，最终出现两次，上行一次，下行一次。\ 因此，如果有值的出现次数不为 2，判断无解。\ 上下两行均构成排列，即 [1, n] 中每个整数，同一行内不得重复出现，那么有以下情况：

1. 原表格中，x 的两次出现分属不同行。

   x . . . . . .
   . . . . . . x

   这意味着第一个 x 所在的 i 列，与第二个所在的 j 列，要么都不翻转，要么同时翻转，否则只翻转一列的话，同一行一定会出现重复的 x。\ 这启示我们，可以将满足这样关系的列 i 与列 j，放进同一个并查集，最终将“列”的翻转视作翻转整个并查集内的“列”。

2. 原表格中，x 的两次出现属于同一行。

   x . . . . . x
   . . . . . . .

   这意味着第一个 x 所在的 i 列，与第二个所在的 j 列，只能且必须翻转其中一个，否则都翻转，或都不翻转的话，同一行一定会出现重复的 x。\ 这启示我们，如果有多组满足这样关系的列 i 与列 j，将列 i 与列 j 看作点，这种关系看作边，构成一张不联通图，每一个联通块一定可以双染色（联通块为链，或联通块为偶环）。 :::info[证明联通块为链，或联通块为偶环] 首先，一个点连出去最多两条边，这是肯定的。因为一个点所代表的一列，只有两行。\ 其次，设该联通块是一个奇环（i_1, i_2, \dots i_k, i_1)，手模下去可以发现，i_1 与 i_k 相同的值 x，一定不在同一行。 ::: 当然，如果按照第一种情况缩了点，那么实际上就是每个联通块内的并查集可以双染色。判断双染色后两个颜色，构成的两个集合，孰的点数更少，即需要翻转的列更少。

综上，我们将该问题转化为了图论问题（其实是很 basic 的图论操作）。

实现

首先，判断是否有解。 :::success[code]

int apr[N];
void PREPAR()
{
    for(int i = 1; i <= n; i ++)
    {
        apr[i] = 0;
    }
    for(int i = 1; i <= n; i ++)
    {
        apr[A[0][i]] ++;
        apr[A[1][i]] ++;
    }
}

::: 接着，关系一采用并查集维护。 :::success[code]

int las[2][N];
int F[N];
vector <int> own[N];
int find(int x)
{
    return (F[x] == x ? F[x] : F[x] = find(F[x]));
}
void join(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx == fy)
    {
        return;
    }
    F[fx] = fy;
}
void PREPAR()
{
    for(int i = 1; i <= n; i ++)
    {
        las[0][i] = las[1][i] = -1;
        F[i] = i;
    }
    E.clear();
    for(int i = 1; i <= n; i ++)
    {
        int a0 = A[0][i];
        if(-1 != las[1][a0])
        {
            join(i, las[1][a0]);
        }
        if(-1 == las[0][a0])
        {
            las[0][a0] = i;
        }
        else
        {
            E.push_back({i, las[0][a0]});
        }

        int a1 = A[1][i];
        if(-1 != las[0][a1])
        {
            join(i, las[0][a1]);
        }
        if(-1 == las[1][a1])
        {
            las[1][a1] = i;
        }
        else
        {
            E.push_back({i, las[1][a1]});
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        own[i].clear();
    }
    for(int i = 1; i <= n; i ++)
    {
        own[find(i)].push_back(i);
    }
}

::: 接下来按照关系二，建图，对每个联通块双染色求出答案。 :::success[code]

int las[2][N];
vector <pair <int, int> > E;
vector <int> H[N];
void PREPAR()
{
    for(int i = 1; i <= n; i ++)
    {
        las[0][i] = las[1][i] = -1;
    }
    E.clear();
    for(int i = 1; i <= n; i ++)
    {
        int a0 = A[0][i];
        if(-1 == las[0][a0])
        {
            las[0][a0] = i;
        }
        else
        {
            E.push_back({i, las[0][a0]});
        }

        int a1 = A[1][i];
        if(-1 == las[1][a1])
        {
            las[1][a1] = i;
        }
        else
        {
            E.push_back({i, las[1][a1]});
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        H[i].clear();
    }
    for(auto e : E)
    {
        H[find(e.first)].push_back(find(e.second));
        H[find(e.second)].push_back(find(e.first));
    }
}

int Ans;
vector <int> chg;
int vis[N];
void dfs(int u, int fm, int col, vector <int> &r)
{
    vis[u] ++;
    if(1 == col)
    {
        for(auto i : own[u])
        {
            r.push_back(i);
        }
    }

    for(auto v : H[u])
    {
        if(fm == v)
        {
            continue;
        }
        if(vis[v] == vis[u])
        {
            continue;
        }
        dfs(v, u, 1 - col, r);
    }
}
void GETANS()
{
    chg.clear();
    for(int i = 1; i <= n; i ++)
    {
        vis[i] = 0;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(vis[i])
        {
            continue;
        }
        vector <int> r[2];
        dfs(i, 0, 0, r[0]);
        dfs(i, 0, 1, r[1]);
        if(r[0].size() < r[1].size())
        {
            for(auto u : r[0])
            {
                chg.push_back(u);
            }
        }
        else
        {
            for(auto u : r[1])
            {
                chg.push_back(u);
            }
        }
    }
    Ans = chg.size();
}

::: 输出答案。\ 由于多测，记得清空。 :::success[CODE]

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

const int N = 2e5 + 10;
int n;
int A[2][N];
void INPUT()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> A[0][i];
    }
    for(int i = 1; i <= n; i ++)
    {
        cin >> A[1][i];
    }
}

int apr[N];
int las[2][N];
int F[N];
vector <int> own[N];
int find(int x)
{
    return (F[x] == x ? F[x] : F[x] = find(F[x]));
}
void join(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx == fy)
    {
        return;
    }
    F[fx] = fy;
}
vector <pair <int, int> > E;
vector <int> H[N];
void PREPAR()
{
    for(int i = 1; i <= n; i ++)
    {
        apr[i] = 0;
    }
    for(int i = 1; i <= n; i ++)
    {
        apr[A[0][i]] ++;
        apr[A[1][i]] ++;
    }

    for(int i = 1; i <= n; i ++)
    {
        las[0][i] = las[1][i] = -1;
        F[i] = i;
    }
    E.clear();
    for(int i = 1; i <= n; i ++)
    {
        int a0 = A[0][i];
        if(-1 != las[1][a0])
        {
            join(i, las[1][a0]);
        }
        if(-1 == las[0][a0])
        {
            las[0][a0] = i;
        }
        else
        {
            E.push_back({i, las[0][a0]});
        }

        int a1 = A[1][i];
        if(-1 != las[0][a1])
        {
            join(i, las[0][a1]);
        }
        if(-1 == las[1][a1])
        {
            las[1][a1] = i;
        }
        else
        {
            E.push_back({i, las[1][a1]});
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        own[i].clear();
    }
    for(int i = 1; i <= n; i ++)
    {
        own[find(i)].push_back(i);
    }
    for(int i = 1; i <= n; i ++)
    {
        H[i].clear();
    }
    for(auto e : E)
    {
        H[find(e.first)].push_back(find(e.second));
        H[find(e.second)].push_back(find(e.first));
    }
}

int Ans;
vector <int> chg;
int vis[N];
void dfs(int u, int fm, int col, vector <int> &r)
{
    vis[u] ++;
    if(1 == col)
    {
        for(auto i : own[u])
        {
            r.push_back(i);
        }
    }

    for(auto v : H[u])
    {
        if(fm == v)
        {
            continue;
        }
        if(vis[v] == vis[u])
        {
            continue;
        }
        dfs(v, u, 1 - col, r);
    }
}
void GETANS()
{
    for(int i = 1; i <= n; i ++)
    {
        if(2 != apr[i])
        {
            Ans = -1;
            return;
        }
    }

    chg.clear();
    for(int i = 1; i <= n; i ++)
    {
        vis[i] = 0;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(find(i) != i)
        {
            continue;
        }
        if(vis[i])
        {
            continue;
        }
        vector <int> r[2];
        dfs(i, 0, 0, r[0]);
        dfs(i, 0, 1, r[1]);
        if(r[0].size() < r[1].size())
        {
            for(auto u : r[0])
            {
                chg.push_back(u);
            }
        }
        else
        {
            for(auto u : r[1])
            {
                chg.push_back(u);
            }
        }
    }
    Ans = chg.size();
}

void OUTPUT()
{
    cout << Ans << "\n";
    if(-1 != Ans)
    {
        for(auto u : chg)
        {
            cout << u << " ";
        }
        cout << "\n";
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;
    while(t --)
    {
        INPUT();
        PREPAR();
        GETANS();
        OUTPUT();
    }

    return 0;
}

::: 时间复杂度 O(\alpha(n))。