题解 | 2023 年牛客多校第三场 D 题 Ama no Jaku

题意：给定一 $n\times nn\backslash times\; n$ 的 01 矩阵，每次可以翻转一行或一列，执行若干次操作。若将操作完成后的矩阵的每一行从做到右视为一个二进制数 $\{r{\}}_{i=1}^n\backslash \{r\backslash \}\_\{i=1\}^n$，每一列从上到下视为 $\{c{\}}_{i=1}^n\backslash \{c\backslash \}\_\{i=1\}^n$，要求 $\min (r_i)\ge \max (c_i)\backslash min(r\_i)\; \backslash ge\; \backslash max(c\_i)$，问是否可以实现，可以实现求最小操作次数。$1\le n\le 3001\; \backslash le\; n\; \backslash le\; 300$。

解法：假设第一行有一个 $11$，则 $\max (c_i)\ge 2^{n-1}\backslash max(c\_i)\; \backslash ge\; 2^\{n-1\}$，此时 $\min (r_i)\ge 2^{n-1}\backslash min(r\_i)\; \backslash ge\; 2^\{n-1\}$，即第一列每个数字都是 $11$，则此时 $\max (c_i)=2^n-1\backslash max(c\_i)=2^n-1$，则要求整个矩阵都是 $11$。因而全 $11$ 矩阵是合理的。

如果第一行全 $00$，则 $\min (r_i)=0\backslash min(r\_i)=0$，则 $\max (c_i)=0\backslash max(c\_i)=0$，整个矩阵全 $00$。

因而整个矩阵必须所有数字都相同。

考虑维护方程 $\{c_i\}\backslash \{c\_i\backslash \}$ 和 $\{r_j\}\backslash \{r\_j\backslash \}$。如果最后是全 $00$，如果当前 $a_{i,j}=1a\_\{i,j\}=1$，则 $c_i\mathrm{\ne }{r}_{j}c\_i\; \backslash ne\; r\_j$，反之相等。因而维护一个 01 种类并查集即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
char a[N + 5][N + 5];
// [1, n] row0; [n+1,2n] row1
// [2*n+1,3*n] col0
int father[4 * N + 5], n;
int getfather(int x)
{
    return father[x] == x ? x : father[x] = getfather(father[x]);
}
int getid(int id, int flag, int col)
{
    int ans = id;
    if (flag)
        ans += 2 * n;
    if (col)
        ans += n;
    return ans;
}
void merge(int x, int y)
{
    x = getfather(x);
    y = getfather(y);
    if (x != y)
        father[x] = y;
}
bool check(int x, int y)
{
    return getfather(x) == getfather(y);
}
int solve(int op)
{
    int m = n * 2;
    for (int i = 1; i <= 2 * m; i++)
        father[i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] == ('1' ^ op))
            {
                merge(getid(i, 0, 0), getid(j, 1, 1));
                merge(getid(i, 0, 1), getid(j, 1, 0));
            }
            else
            {
                merge(getid(i, 0, 0), getid(j, 1, 0));
                merge(getid(i, 0, 1), getid(j, 1, 1));
            }
    for (int i = 1; i <= n; i++)
        if (check(i, i + n))
            return -1;
    for (int i = 1; i <= n; i++)
        if (check(i + 2 * n, i + 3 * n))
            return -1;
    map<int, int> siz;
    for (int i = 1; i <= n; i++)
        siz[getfather(i)]++;
    for (int i = 2 * n + 1; i <= 3 * n; i++)
        siz[getfather(i)]++;
    int ans = 2 * n;
    for (auto [x, y] : siz)
        ans = min(ans, y);
    return min(ans, 2 * n - ans);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%s", a[i] + 1);
    if (solve(0) == -1)
    {
        printf("-1");
        return 0;
    }
    printf("%d", min(solve(0), solve(1)));
    return 0;
}