bzoj4171 or 省队集训day3 chess: Rhl的游戏

【题目描述】

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

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

【输入格式】

第一行一个整数T，表示T组数据。

每组数据开始于三个整数n,m,k，分别表示格子的高度和宽度、坏掉格子的个数。接下来的n行，每行一个长度m的字符串，表示格子状态为’B’或‘W’。最后k行，每行两个整数Xi,Yi(1≤Xi≤n,1≤Yi≤m)，表示坏掉的格子。

【输出格式】

对于每组数据，先输出一行Case #i: (1≤i≤T)

如果可以成功，输出YES，否则输出NO。

【样例输入】

3 3 0

WBW

BBB

WBW

3 3 2

WBW

BBB

WBW

2 2

3 2

【样例输出】

Case #1:

YES

Case #2:

【数据范围】

30%,n,m,k<=10

100%,n,m,k<=256,T<=10

http://www.cnblogs.com/chenyushuo/p/4685182.html

和这个类似的设个xor方程组，对于不能按的方块，直接将它定为0即可

code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 260

 using namespace std;

 char ch,s[maxn];

 int T,n,m,N,M,k,x,y;

 unsigned int c[maxn][maxn][maxn>>],a[maxn<<][maxn>>];

 bool col[maxn][maxn],ok,d[maxn][maxn],b[maxn<<];

 inline void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 bool gauss(){

     int i,j,k,p,q;

     for (i=,k=;i<N;i++){

         for (p=(<<(i&)),j=k;j<=M&&!(a[j][i>>]&p);j++);

         if (j<=M){

             for (q=(i>>);q<=((N-)>>);q++) swap(a[k][q],a[j][q]);

             swap(b[k],b[j]);

             for (j=j+;j<=M;j++)

                 if (a[j][i>>]&p){

                     for (q=(i>>);q<=((N-)>>);q++) a[j][q]^=a[k][q];

                     b[j]^=b[k];

                 }

             k++;

         }

     }

     for (;k<=M;k++) if (b[k]) return false;

     return true;

 }

 int main(){

     read(T);

     for (int t=;t<=T;t++){

         read(m),read(n),read(k),N=n,M=n;

         for (int i=;i<=m;i++){

             scanf("%s",s+);

             for (int j=;j<=n;j++) col[i][j]=(s[j]=='B');

         }

         for (int i=;i<=n;i++) c[][i][(i-)>>]=(<<((i-)&));

         for (int i=;i<=m;i++)

             for (int j=;j<=n;j++){

                 for (int k=;k<=((n-)>>);k++)

                     c[i][j][k]=c[i-][j-][k]^c[i-][j][k]^c[i-][j+][k]^c[i-][j][k];

                 d[i][j]=d[i-][j-]^d[i-][j]^d[i-][j+]^d[i-][j]^col[i-][j];

             }

         for (int i=;i<=n;i++){

             for (int j=;j<=((n-)>>);j++)

                 a[i][j]=c[m][i][j]^c[m][i-][j]^c[m][i+][j]^c[m-][i][j];

             b[i]=col[m][i]^d[m][i-]^d[m][i]^d[m][i+]^d[m-][i];

         }

         while (k--){

             read(x),read(y),++M;

             for (int i=;i<=((n-)>>);i++) a[M][i]=c[x][y][i];

             b[M]=d[x][y];

         }

         printf("Case #%d:\n",t);

         if (gauss()) puts("YES");

         else puts("NO");

     }

     return ;

 }

巴特西

bzoj4171 or 省队集训day3 chess: Rhl的游戏

最新文章

热门文章