题解：CF2081C Quaternary Matrix

· · 题解

Pre-story

看题解前 2700，看完题解 3700。

非人类脑电波题目，强烈推荐。

Solution

考虑维护 r_i 表示第 i 行所有元素的异或和， c_j 表示第 j 行所有元素的异或和。

则容易得到：r_1 \oplus r_2 \cdots \oplus r_n = c_1 \oplus c_2 \cdots \oplus c_m。

那么，分析一次修改的本质。若对于一个元素 a_{i, j}，将此元素改为 v 就等价于将 a_{i, j} 异或上 x = a_{i, j} \oplus v。

显然修改也会影响行列异或和。具体的，r_i \to r_i \oplus x，c_j \to c_j \oplus x。

观察到一次修改不会同时影响 2 行或者 2 列。

所以，考虑进行图论建模（但实现是用不到的）。不妨创造一个二分图，左部点为行 i，右部点位列 j。

当执行一次修改时，可以将左部点 i 向右部点 j 连上一条边权为 x。

手玩一下可以得到，若干次操作会把二分图的 n + m 个点划分成若干个联通块。根据二分图的性质，容易得到一个包含 R 行 C 列的连通块，边数是 R + C - 1，即操作次数是 R + C - 1。

考虑维护异或和为 x 的行数 \text{crow}_x，异或和为 y 的列数 \text{cline}_{y}（此处变量名可能存在歧义，见谅），则令 k 为连通块个数，易得答案即为 \sum_{x} \text{crow}_x + \sum_{y} \text{cline}_{y} - k。

显然，k 越大越好。也就是说，我们尽量要多划分连通块。

考虑分析哪一些操作可以使连通块的个数尽可能大。

接下来，就是 Super 分类讨论 Time（下文统称异或和为“值”）！

Case 1

若存在左部行的值为 x，右部列的值也为 x，那么在它们的交界处的 a_{i, j} 异或一个 x 即可。

连通块大小（操作次数）为 1。

Case 2

Case 1 处理完之后，可能会出现这种情况：1, 2, 3 三种值有一个值落在一侧，另两个值落在另一侧。

证明极其容易。那为什么没有 0？因为它已经符合题目要求了。

钦定左部行有一个值 x，右部列有两个值 y, z，则可以这样操作：

为什么？注意到题目中只有 1, 2, 3 三种正整数值，而容易证明这三个数必定有 x = y \oplus z。所以 x 被消成 0 了，y, z 显然也会消成 0。

连通块大小（操作次数）为 2。

Case 3

但是，有可能 y 或者 z 的其中一个已经没有了。

考虑钦定剩下的是 y，则 2 个 x 和 2 个 y 可以这样用 3 次操作消除：

计算一下每一个点和所有与它相连的边的边权的异或和的异或和，可以发现每一个点（行/列）都恰好被消掉了！

连通块大小（操作次数）为 3。

Case 4

只剩下一种情况，就是只有一侧是有值的，那么可以借助任意一个其他的点（行/列）p 进行这样的操作：

连通块大小（操作次数）为 1。

Code

在实际的代码实现中，我们不需要建图，直接维护哪一些点（行/列）的异或和是 x \in \{0, 1, 2, 3\} 并存进一个桶。然后，暴力去模拟操作即可。

代码难度堪比一只成年大象。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 1010;

int n, m, a[kMaxN][kMaxN], xline[kMaxN], xrow[kMaxN], ans;
vector<int> line[4], row[4];

// xrow 维护行的异或和，xline 维护列的异或和，vector 就是桶 

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n >> m, ans = 0;
    fill(xrow + 1, xrow + n + 1, 0);
    fill(xline + 1, xline + m + 1, 0);
    string s;
    for (int i = 1; i <= n; ++ i) {
      cin >> s;
      for (int j = 1; j <= m; ++ j) {
        a[i][j] = s[j - 1] - '0';
        xrow[i] ^= a[i][j], xline[j] ^= a[i][j];
      }
    }
    for (int i = 1; i <= n; ++ i) {
      if (xrow[i]) {
        row[xrow[i]].push_back(i);
      }
    }
    for (int i = 1; i <= m; ++ i) {
      if (xline[i]) {
        line[xline[i]].push_back(i);
      }
    }
    // Case 1：1 次操作消除不同侧的 x 
    for (int x = 1, r, c; x <= 3; ++ x) {
      for (; row[x].size() && line[x].size(); row[x].pop_back(), line[x].pop_back()) {
        r = row[x].back(), c = line[x].back();
        a[r][c] ^= x;
        ++ ans; 
      }
    }
    // Case 2：2 次操作消除 x 和 y, z 
    for (int x = 1, r1, r2, c1, c2, y, z; x <= 3; ++ x) {
      y = (x % 3) + 1, z = ((x + 1) % 3) + 1;
      for (; row[x].size() && line[y].size() && line[z].size(); row[x].pop_back(), line[y].pop_back(), line[z].pop_back()) {
        r1 = row[x].back(), c1 = line[y].back(), c2 = line[z].back();
        a[r1][c1] ^= y, a[r1][c2] ^= z;
        ans += 2;
      }
      for (; line[x].size() && row[y].size() && row[z].size(); line[x].pop_back(), row[y].pop_back(), row[z].pop_back()) {
        c1 = line[x].back(), r1 = row[y].back(), r2 = row[z].back();
        a[r1][c1] ^= y, a[r2][c1] ^= z;
        ans += 2;
      }
    }
    // Case 3：3 次操作消除 2 个 x 和 2 个 y
    for (int x = 1, r1, c1, r2, c2; x <= 3; ++ x) {
      for (int y = 1; y <= 3; ++ y) {
        for (; row[x].size() >= 2 && line[y].size() >= 2; row[x].pop_back(), line[y].pop_back()) {
          r1 = row[x].back(), c1 = line[y].back();
          row[x].pop_back(), line[y].pop_back();
          r2 = row[x].back(), c2 = line[y].back();
          a[r1][c1] ^= x, a[r2][c1] ^= (x ^ y), a[r2][c2] ^= y;
          ans += 3;
        }
      }
    }
    // Case 4：2 次操作消除 2 个 x 
    for (int x = 1, r, c; x <= 3; ++ x) {
      for (; row[x].size(); row[x].pop_back()) {
        r = row[x].back();
        a[r][1] ^= x;
        ++ ans;
      }
      for (; line[x].size(); line[x].pop_back()) {
        c = line[x].back();
        a[1][c] ^= x;
        ++ ans;
      }
    }
    cout << ans << '\n';
    for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= m; ++ j) {
        cout << a[i][j];
      }
      cout << '\n';
    }
  }
  return 0;
}