hdoj 5257 翻转游戏

其实我在一年多前就在老刘的专题训练做过这个题了，队友问起这个题又复习了一下，还是有很多收获。唉唉，转眼都要退役了，时间过得真快

题意

度度熊最近迷上一个小游戏：Flip it。游戏的规则很简单，在一个N*M的格子上，有一些格子是黑色，有一些是白色。每选择一个格子按一次，格子以及周围边相邻的格子都会翻转颜色（边相邻指至少与该格子有一条公共边的格子），黑变白，白变黑。

度度熊希望把所有格子都变成白色的。不幸的是，有一些格子坏掉了，无法被按下。这时，它可以完成游戏吗？

题解

首先可以发现，如果确定了第一行或者第一列的每一个开关是否按下，那么其他所有开关是否被按就是确定的。

不妨设第一行的每个开关的状态为 \(x_i\)，显然按两次以上开关没有意义，所以 \(x_i \in \{0, 1\}\)。设 \(f(i, j)\) 表示开关 \((i,j)\) 的状态, \(f\) 是一个关于 \(x_1,x_2,x_3\dots x_m,x_{m+1}\) 的 \(m+1\) 元一次函数，且系数为 \(0\) 或者 \(1\)。这里多了一个变量 \(x_{m+1}\)，之后会解释。

对于第一行 \(f(1,j)=x_i\)。考虑一行一行的转移 \(f\)，因为 \((i, j)\) 开关恰好会影响 \((i-1,j)\) 的格子颜色，而影响那个格子颜色的其他四个开关的状态 \(f(i-1,j)\), \(f(i-1,j-1)\), \(f(i-1,j+1)\), \(f(i-2,j)\) 已经算出，再结合 \((i-1,j)\) 本来的颜色就可以递推出 \(f(i,j)\)，这也解释了为什么要多设一个 \(x_{m+1}\)，实际上 \(x_{m+1}\) 是一个恒 \(1\) 的变量，作用是考虑格子本来的颜色带来的影响。

可能有人会疑惑，递推 \(f\) 的时候为什么不考虑相邻两列互相影响。这是因为 \(f\) 表示的是开关是否按下，而不是格子的颜色状态。

实际上这样做之后，保证了当前这一行无论是什么颜色，下一行的开关始终能让它们变成白色。但是最后一行就需要自身保证操作完之后是白色的，这也是约束条件。

另外还有一个限制条件是有一些开关坏了不能按，只需要加入新的约束条件对应的 \(f(i,j)=0\) 即可。

最后高斯消元判断是否有解，就可以用 \(O(\frac{nm^2}{\omega})\) 的时间复杂度解决此题！

代码

//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 257 + 5;

bitset<258> bot[N][N];
int n, m, k, a[N][N];

namespace Gauss {
    bitset<258> a[256 + 256 + 5];
    int n;
    void push(const bitset<258>& x) {
        a[++n] = x;
    }
    bool solve(int m) {
        int k = 1;
        for (int i = 1; i <= m; i++) {
            if (k > n) break;
            for (int j = k + 1; j <= n; j++) if (a[j][i] > 0) {
                swap(a[k], a[j]);
                break;
            }
            if (a[k][i] == 0) break;
            for (int j = 1; j <= n; j++) if (j != k && a[j][i]) {
                a[j] ^= a[k];
            }
            ++k;
        }
        for (int i = k; i <= n; i++) if (a[i][m + 1]) return false;
        return true;
    }
}

void MAIN() {
    string s;
    Gauss::n = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bot[i][j].reset();
        }
    }
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= m; j++) {
            a[i][j] = (s[j - 1] == 'B');
        }
    }
    for (int i = 1; i <= m; i++) bot[1][i].set(i);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bot[i][j] = bot[i - 1][j] ^ bot[i - 1][j - 1] ^ bot[i - 1][j + 1] ^ bot[i - 2][j];
            bot[i][j][m + 1] = bot[i][j][m + 1] ^ a[i - 1][j];
        }
    }
    while (k--) {
        int x, y; cin >> x >> y;
        Gauss::push(bot[x][y]);
    }
    for (int i = 1; i <= m; i++) {
        bitset<258> x = bot[n][i] ^ bot[n][i + 1] ^ bot[n][i - 1] ^ bot[n - 1][i];
        x[m + 1] = x[m + 1] ^ a[n][i];
        Gauss::push(x);
    }
    static int Case = 0;
    cout << "Case #" << ++Case << ":\n";
    if (Gauss::solve(m)) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
#ifdef LOCAL
    auto start = chrono::steady_clock::now();
    freopen("miku.in", "r", stdin);
    freopen("miku.out", "w", stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) MAIN();
#ifdef LOCAL
    auto end = chrono::steady_clock::now();
    cout << "\nqwq: " <<  chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
#endif
    return 0;
}