此文章可以使用目录功能哟↑(点击上方[+])
51Nod Problem 1605 棋盘问题
Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 131072 KB
Problem Description
上帝创造了一个n*m棋盘，每一个格子都只有可能是黑色或者白色的。
亚当和夏娃在玩一个游戏，每次寻找边长为x的正方形，其中每个格子必须为黑色，然后将这些格子染白。
如果谁不能操作了，那么那个人就输了。
亚当喜欢质数。
夏娃喜欢1，但讨厌2。
因此他们规定，x只有可能是非2质数或者是1。
现在他们想知道，如果他们都用最优策略进行游戏，谁会赢。
上帝规定亚当先手。
样例解释：
这里x只有可能是1，因此经过3次操作后，夏娃无法操作，亚当胜。
Input
第一行输入一个T，表示有几组测试数据(1<=T<=10)
接下来每一个数据第一行有两个整数n,m（1<=n,m<=100）
接下来n行每行m个数，若这个数是1，则表示该位置是黑色，否则为白色。
Output
对于每一组数据输出“yadang”或者“xiawa”（不含引号，表示那个人会赢）。
Sample Input
2 3
1 1 0
0 0 1
Sample Output
Hint
Problem Idea
解题思路:
【题意】
n*m个格子的棋盘,亚当和夏娃轮流取边长为x,其中格子全为黑色格子的正方形进行染白
亚当先手,谁不能操作谁输
x为1或非2质数
问最终谁会赢
【类型】
博弈(分类讨论奇偶性)
【分析】
在解决此题之前,我们要知道的是:
①奇数×奇数=奇数
②奇数+奇数=偶数
那么当x=1时,若此时有k个边长为1的正方形,两人轮流取,显然k为奇数时,先手必胜;否则,后手必胜
理由很简单,因为有奇数个正方形,亚当先取走1个,导致剩下偶数个正方形,那么夏娃取一个,亚当跟着取一个,这就导致最后一个必定是亚当能够取到
再来考虑x为非2质数时,边长为x的正方形中有x*x个格子,由于非2质数均为奇数,这就说明x*x是奇数
所以对于有奇数个格子的状态,不管你取边长为多少的正方形,都会取走奇数个格子,这也就是说留下的是偶数个格子的必败态
综上所述,我们只需要判断黑色格子的数量是奇数个还是偶数个就可以了
【时间复杂度&&优化】
O(nm)
题目链接→51Nod Problem 1605 棋盘问题
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 2005;
const int M = 120;
const int inf = 1600000000;
const int mod = 2009;
int main()
{int t,n,m,x,c,i,j;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(c=i=0;i<n;i++)for(j=0;j<m;j++){scanf("%d",&x);if(x&1)c++;}if(c&1)puts("yadang");elseputs("xiawa");}return 0;
}