自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:59:48，当前版本为作者最后更新于2024-09-04 21:38:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

---

• 原题数据过水，建议通过本题后可以用我出的加强版测试代码强度。具体的，将 $n$ 的范围扩大到了 $1\times 10^4$。

理解 1（数学做法）：

感觉目前已有题解写的都难以看懂，所以写一篇自认为比较好理解的，同时与目前题解的做法均不大相同。

下文中，$A_{i,j}$ 表示在 $(i,j)$ 处原本的状态，$C_{i,j}$ 表示是否在 $(i,j)$ 处执行整行整列的修改，$A_{i,j}\in\{0,1\},C_{i,j}\in\{0,1\}$。

考虑到一个位置如果被翻转两次那么结果会不变，很容易想到异或。更进一步思考：如果想将 $(x,y)$ 翻转为 $0$，那么 $\displaystyle A_{x,y}\oplus\left(\bigoplus_{i=1}^nC_{i,y}\right)\oplus\left(\bigoplus_{i=1}^{n}C_{x,i}\right)\oplus C_{x,y}=0$。两边同时异或 $A_{x,y}$ 得 $\displaystyle A_{x,y}=\left(\bigoplus_{i=1}^nC_{i,y}\right)\oplus\left(\bigoplus_{i=1}^{n}C_{x,i}\right)\oplus C_{x,y}$。

那么又可以得出：

$$\begin{aligned} & \displaystyle\left(\bigoplus_{i=1}^nA_{i,y}\right)\oplus\left(\bigoplus_{i=1}^{n}A_{x,i}\right)\oplus A_{x,y}\\ =& \bigoplus_{i=1}^n\left[\left(\bigoplus_{j=1}^nC_{j,y}\right)\oplus\left(\bigoplus_{j=1}^{n}C_{i,j}\right)\oplus C_{i,y}\right] \oplus \bigoplus_{i=1}^{n}\left[\left(\bigoplus_{j=1}^nC_{j,i}\right)\oplus\left(\bigoplus_{j=1}^{n}C_{x,j}\right)\oplus C_{x,i}\right] \oplus \left[\left(\bigoplus_{i=1}^nC_{i,y}\right)\oplus\left(\bigoplus_{i=1}^{n}C_{x,i}\right)\oplus C_{x,y}\right]\\ =& \bigoplus_{i=1}^n\left[\left(\bigoplus_{j=1}^nC_{j,y}\right)\oplus\left(\bigoplus_{j=1}^{n}C_{i,j}\right)\right] \oplus \bigoplus_{i=1}^{n}\left[\left(\bigoplus_{j=1}^nC_{j,i}\right)\oplus\left(\bigoplus_{j=1}^{n}C_{x,j}\right)\right] \oplus C_{x,y}\\ =&C_{x,y},n\equiv 0(\bmod 2) \end{aligned} $$

也就是说，我们可以通过输入的 $A$ 数组推导出 $C$ 数组。如果知道了 $C$ 数组，也就是知道了每个位置是否需要执行行列修改操作。

那么如果要将所有的数均变为 $1$，那么只需要在统计时再异或 $1$ 即可。又考虑到异或的性质，均变为 $0$ 和均变为 $1$ 的答案之和恰好为统计 $1$ 时异或 $1$ 的个数（即 $n^2$）。在输出时用均变为 $0$ 的答案 $n^2$ 减去均变为 $0$ 的答案的最小值即可。

如果直接这么做时间复杂度为 $\Theta(n^4)$，但是考虑到 $\displaystyle\bigoplus_{i=1}^nA_{i,y}$ 和 $\displaystyle\bigoplus_{i=1}^{n}A_{x,i}$ 是可以用异或前缀和预处理出来的，那么时间复杂度就可以优化到 $\Theta(n^2)$。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 9;
int n, ans, a[maxn][maxn], line[maxn], column[maxn];
string s;
signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s;
		for (int j = 1; j <= n; j++)
			a[i][j] = s[j - 1] - '0', line[i] ^= a[i][j], column[j] ^= a[i][j];
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			ans += line[i] ^ column[j] ^ a[i][j];
	cout << min(ans, n * n - ans);
}

理解 2：

考虑到对于每一个点，想当且仅当修改这一个点 $P$ 而不修改其它点，可以将它的横行数列的十字共计 $2n-1$ 个点全部修改（因为 $n$ 是偶数，所以其他所有点一定只会被修改偶数次，当然这也可以用来简便理解计算出上面做法的那个大算式）。

具体地讲：对于整个矩阵的点 $Q$ 分为如下三种情况：

1. 不在十字上：那么这个点一定会他水平方向和竖直方向的点修改两次，它的值并不会发生变化。
2. 在十字上但不是 $P$ 点：那么一定会被同一行或同一列的所有点修改 $n$ 次，由于 $n$ 是偶数，所以它的值也不会发生变化。
3. $P$ 点：被它同一行和同一列共计 $2n-1$ 个点修改，$2n-1$ 一定是奇数，所以可以成功取反。

如果两个点都要修改，这两个点一定会造成最少两个交点，那么这些交点显然不需要修改（即异或两次）。用一个数组统计每个点是否修改即可。

用 $\Theta(n^2)$ 枚举每个点，如果需要修改掉，再用 $\Theta(n)$ 修改所有要修改的点。共计时间复杂度为 $\Theta(n^3)$，但是因为位运算的较低常数复杂度，可以稳定通过本题（经多次测试，最慢的点也不会超过 400ms）。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 9;
int n, ans, a[maxn][maxn], f[maxn][maxn];
string s;
signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s;
		for (int j = 1; j <= n; j++)
			a[i][j] = s[j - 1] - '0';
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (a[i][j])
			{
				for (int k = 1; k <= n; k++)
					f[i][k] ^= 1, f[k][j] ^= 1;
				f[i][j] ^= 1;
			}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			ans += f[i][j];
	cout << min(ans, n * n - ans);
}

但是还是可以考虑优化，注意到这个算法的复杂度瓶颈在于枚举 f 数组需要修改的位置，那么能否省略掉这个循环呢？答案是可以的，因为对于任意的 $(x,y)$，只有这一行和这一列的所有 $1$ 会对答案产生影响。且因为异或的性质，我们可以通过 $1$ 的个数直接快速地算出每一个 $f_{x,y}$ 的变量值，这就可以将时间复杂度优化为 $\Theta(n^2)$。

代码暂时省略，交给读者自行完成。

---

公式又多又长，写了好久，我要亖了，如果有错烦请请评论区交流。

• 鸣谢：

1. @wangbinfeng 耗时 3h 完成本题解的创作。
2. @NATO_Fan_Club 首先质疑本题已有题解并启发本人想到第二种理解，具体见这个帖子。
3. @a1co0av5ce5az1cz0ap_ 的题解，让本人借鉴了部分的证明（即修改十字的准确证明，本人之前写法过于主观难以理解）。
4. 难以理解的现有题解（所有在本题解完成前的 luogu 题解）激励本人完成本题解的创作。