题解：CF2081C Quaternary Matrix
CF2081C Quaternary Matrix
蒟蒻的第一篇 TJ ,有不足之处请各位 dalao 指出
题目大意
一个 $ n \times m $ 的矩阵，由 $0$ 、 $1$ 、 $2$ 、 $3$ 组成，问最少需要修改多少元素让每行、每列异或和为 $0$ ，输出一种构造方案。
$ 1 \leq n , m \leq 1000 $
思路
将每行、每列的异或和看成 $ 2 \times n $ 个点，这时注意到可以将这些点分成若干点集。
每个点集异或和为 $ 0 $ ，且至少一个点属于行，至少一个点属于列。
这些点集满足几个性质：
- 这 $ 2 \times n $ 个点异或和一定为 $ 0 $ ，证明如下：
每个点在其对应行与列分别被计算一次，所以总异或和为 $ 0 $ 。
- 每个完整点集产生的贡献为点集内元素个数 $ -1 $（我是手玩数据得出的），证明如下：
设当前点集共 $ k $ 个元素，当前 $ k-1 $ 个元素已经完成修改时，异或和刚好是第 $ k $ 个元素的值，所以它不用修改。
-
这时不难想到点集数最多时贡献最少（贪心），所以每个点集不可再分出另一个点集，即：每个点集最小。
-
一共 4 种分组情况：
- 在行中选择一个点，列中选择一个点，两个点值相等。
![]()
- 在行与列中异或和为 $ 0 $ 的 3 个点（一个 1 ，一个 2 ，一个 3 ）。
![]()
- 在行中选择相同的两个点，列中选择相同的两个点。
![]()
-
其它单个的点也分 2 种情况：
- 同在行中相同的 2 个点或同在行中异或和为 $ 0 $ 的 3 个点，因为没有列与它们匹配，所以任选一列修改，但为了不改变修改列的值，两个或三个修改点需在同一列。
![]()
![]()
- 同在列中的点同理。
最后按点集大小从小到大贪心找集合匹配即可。
Code
#include <bits/stdc++.h>
#define fre(ss, i, j, k) for (int ss = i; ss <= j; ss += k)
using namespace std;
long long T, n, m, mp[2005][2005], a[2005], b[2005], na[10], nb[10];
deque<long long> va[10], vb[10];
long long solve()
{long long an = 0;//1:fre(i, 1, 3, 1){long long cha;if (na[i] >= nb[i])cha = nb[i], an += cha, na[i] -= cha, nb[i] = 0;elsecha = na[i], an += cha, nb[i] -= cha, na[i] = 0;while (cha--){long long x = va[i].front(), y = vb[i].front();va[i].pop_front(), vb[i].pop_front();mp[x][y] ^= i;}}//2:fre(i, 1, 3, 1){long long cha = na[i];fre(j, 1, 3, 1) if (i != j) cha = min(cha, nb[j]);an += cha * 2, na[i] -= cha;fre(j, 1, 3, 1) if (i != j) nb[j] -= cha;while (cha){long long x = va[i].front(), y[10];va[i].pop_front();fre(j, 1, 3, 1) if (i != j) y[j] = vb[j].front(), vb[j].pop_front();fre(j, 1, 3, 1) if (i != j) mp[x][y[j]] ^= j;cha--;}}fre(i, 1, 3, 1){long long cha = nb[i];fre(j, 1, 3, 1) if (i != j) cha = min(cha, na[j]);an += cha * 2, nb[i] -= cha;fre(j, 1, 3, 1) if (i != j) na[j] -= cha;while (cha){long long x = vb[i].front(), y[10];vb[i].pop_front();fre(j, 1, 3, 1) if (i != j) y[j] = va[j].front(), va[j].pop_front();fre(j, 1, 3, 1) if (i != j) mp[y[j]][x] ^= j;cha--;}}//3:fre(i, 1, 3, 1) fre(j, 1, 3, 1) if (i != j){long long cha = min(na[i], nb[j]);an += cha / 2 * 3, na[i] -= cha, nb[j] -= cha;while (cha){long long x1 = va[i].front(), y1 = vb[j].front();va[i].pop_front(), vb[j].pop_front();long long x2 = va[i].front(), y2 = vb[j].front();va[i].pop_front(), vb[j].pop_front();mp[x2][y2] ^= j, mp[x2][y1] ^= i ^ j, mp[x1][y1] ^= i, cha -= 2;}}//4(1):fre(i, 1, 3, 1){an += na[i] / 2 * 2 + nb[i] / 2 * 2;while (na[i] > 1){long long x1 = va[i].front();va[i].pop_front();long long x2 = va[i].front();va[i].pop_front();mp[x1][1] ^= i, mp[x2][1] ^= i, na[i] -= 2;}while (nb[i] > 1){long long y1 = vb[i].front();vb[i].pop_front();long long y2 = vb[i].front();vb[i].pop_front();mp[1][y1] ^= i, mp[1][y2] ^= i, nb[i] -= 2;}}//4(2):an += na[1] + na[2] + na[3] + nb[1] + nb[2] + nb[3];while (na[1]){long long y[10];fre(j, 1, 3, 1) y[j] = va[j].front(), va[j].pop_front();fre(j, 1, 3, 1) mp[y[j]][1] ^= j;na[1]--;}while (nb[1]){long long y[10];fre(j, 1, 3, 1) y[j] = vb[j].front(), vb[j].pop_front();fre(j, 1, 3, 1) mp[1][y[j]] ^= j;nb[1]--;}return an;
}
main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> T;while (T--){memset(a, 0, sizeof a), memset(b, 0, sizeof b);memset(na, 0, sizeof na), memset(nb, 0, sizeof nb);fre(i, 0, 3, 1) va[i].clear(), vb[i].clear();cin >> n >> m;fre(i, 1, n, 1) fre(j, 1, m, 1){char x;cin >> x;mp[i][j] = x - '0';}long long an = 0;fre(i, 1, n, 1) fre(j, 1, m, 1) a[i] ^= mp[i][j], b[j] ^= mp[i][j];fre(i, 1, n, 1) na[a[i]]++, va[a[i]].push_back(i);fre(j, 1, m, 1) nb[b[j]]++, vb[b[j]].push_back(j);fre(i, 1, 3, 1) sort(va[i].begin(), va[i].end()), sort(vb[i].begin(), vb[i].end());an = solve();cout << an << "\n";fre(i, 1, n, 1){fre(j, 1, m, 1) cout << mp[i][j];cout << "\n";}}
}