题解：P10635 BZOJ3517 翻硬币

· · 题解

理解 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 是偶数，所以它的值也不会发生变化。

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

用 \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)。

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

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