bzoj 4171: Rhl的游戏

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4171

十分经典的一个模型啊。。
一定要记住

首先，比较显然的做法就是暴力高斯消元
但是直接做是$n^2$个未知数，$n^2$个方程，过不去
但是如果仔细观察，你会发现，如果确定了第一行每个未知数的状态，就可以推导出后面所有位置数的状态了
哦，忘了说了，未知数就是一个点选不选，方程就是若干个异或方程组
具体来说$f_{i,j}=f_{i?1,j}\text{ xor }{f}_{i?1,j?1}\text{ xor }{f}_{i?1,j+1}\text{ xor }{f}_{i?2,j}\text{ xor }{a}_{i?1,j}$
因此，我们只用设$m$个未知数，就是第一行的状态
表示完以后，根据第$n$行列出方程组看是否有解即可，因为$n?1$行的限制都包含在里面了

至于不能填的格子，就额外开多几个方程来表示即可
也就是暴力让$f_{i,j}=0$

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int N=260;
char ss[N];
int a[N][N];
bitset<N> f[N][N],t[N*2];
int n,m,k,tot;
bool solve ()
{
    int j=1;for (int u=1;u<=m;u++){
    int now=0;for (int i=j;i<=tot;i++) if (t[i][u]!=0)	{
    now=i;break;}if (now==0) break;swap(t[j],t[now]);for (int i=j+1;i<=tot;i++) 	if (t[i][u])t[i]=t[i]^t[j];j++;}	for (int u=1;u<=tot;u++){
    bool tf=true;for (int i=1;i<=m;i++)	if (t[u][i]){
    tf=false;break;}if (tf&&t[u][m+1]==1) return false;}return true;
}
int main()
{
    int T;scanf("%d",&T);for (int TT=1;TT<=T;TT++){
    scanf("%d%d%d",&n,&m,&k);for (int u=1;u<=n;u++){
    scanf("%s",ss+1);for (int i=1;i<=m;i++)if (ss[i]=='B')	a[u][i]=1;else a[u][i]=0;}for (int u=1;u<=m;u++){
    for (int i=1;i<=m;i++) f[1][u][i]=0;f[1][u][u]=1;}for (int u=2;u<=n;u++)for (int i=1;i<=m;i++){
    f[u][i]=f[u-1][i]^f[u-1][i-1]^f[u-1][i+1]^f[u-2][i];f[u][i][m+1]=f[u][i][m+1]^a[u-1][i];}tot=0;for (int u=1;u<=k;u++){
    int x,y;scanf("%d%d",&x,&y);t[++tot]=f[x][y];}for (int u=1;u<=m;u++){
    t[++tot]=f[n][u]^f[n][u-1]^f[n][u+1]^f[n-1][u];t[tot][m+1]=t[tot][m+1]^a[n][u];}if (solve()) printf("Case #%d:\nYES\n",TT);else printf("Case #%d:\nNO\n",TT);}return 0;
}