51nod 俄罗斯方块(找规律（构造）)

算法马拉松24   已注册   比赛已经结束 俄罗斯方块 NanoApe  (命题人) 基准时间限制：1 秒 空间限制：131072 KB 分值: 80 玩过俄罗斯方块？那你知道俄罗斯方块共有七种吧（其实只有五种） 给一个黑白图，每次能将某些区域的格子黑白反转，至于某些区域的意思嘛，就是俄罗斯方块形状的区域咯（可水平翻转、上下翻转、旋转） 求能否将图变成全白 Input 多组数据，第一行一个正整数 T，表示数据组数 每组数据中第一行两个正整数 n,m，表示图的长和宽 接下来 n 行，每行 m 个数字，表示第 i 行第 j 列的格子的颜色，0为白，1为黑 T<=1000，∑n*m<=10000000 Output 对于每组数据，若能将图变成全白，则输出一行字符串"Yes"，否则输出"No"（不包含双引号） Input示例 1 4 4 0110 0110 1111 1111 Output示例

Yes

#include<cstdio> #include<iostream> using namespace std; const int maxn=1e7+10; int a[maxn],n,m; inline int read(){ char ch=getchar(); while(ch!='0'&&ch!='1') ch=getchar(); return ch-'0'; } int main(){ int T; scanf("%d",&T); while(T--){ int k=0,cnt=0;//cnt记录1的个数 scanf("%d%d",&n,&m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cnt+=(a[k++]=read()); if(cnt%2) puts("No"); else { if(n==1||m==1) { //此时手动模拟即可 //在这里要注意k<3的情况 if(k<3) if(cnt) puts("No"); else puts("Yes"); else { for(int i=0;i<k-3;i++) if(a[i]) { a[i+1]^=1; a[i+2]^=1; a[i+3]^=1; } if(a[k-1]||a[k-2]||a[k-3]) puts("No"); else puts("Yes"); } } else if(n==2&&m==2) { a[0]=a[0]+a[1]+a[2]+a[3]; if(a[0]==0||a[0]==4) puts("Yes"); else puts("No"); } else puts("Yes"); } } return 0; }

首先这题要求  O(nm)  的复杂度，这是读入复杂度，所以这启发我们去找规律，而不是去搜索

我们可以通过某些方块的奇怪组合来组成一些简单的操作 操作1： + = 操作2： + = 操作3： + = 当然，上面并没有把所有情况拼出，只是说明在2*3时可以拼出两块任意位置。 上述操作都可以认为是将某个黑格平移，或者是两两抵消 但是有条件限制：需要一个 2*3 的空间 所以当棋盘上能创造一个 2*3 的空间时，只需要判断黑格个数的奇偶性即可，奇数为 No，偶数为 Yes 那么假如棋盘小于 2*3 呢？ 两种情况：2*2 和 1*? 2*2 只需要考虑2*2的正方形方块即可 1*? 的情况我们只能用 1*4 的方块，所以我们可以用贪心的解法，就每次选取最左端的黑格，以此作为 1*4 方块的左侧进行黑白反转，重复进行直到无法将 1*4 放置在棋盘上，这时候再判断棋盘是否为全白即可