Description

Input

Output

Sample Input

【样例 1 输入】 1 1 0 【样例 2 输入】 1 1 1   

Sample Output

【样例 1 输出】 rx  【样例 2 输出】 yc  

Data Constraint

Solution

首先可以分为三种情况 :

1.不存在大小为 k×k 的空正方形, 先手必败 2.只存在一个大小为 k×k 的空正方形(相交只算一个), 先手必胜 3.存在至少两个不相交的大小为 k×k 的空正方形

对于第三种情况, 再进行讨论 :

如果一次操作过后, 只剩下一个正方形(所有正方形相交), 那么对手必胜 如果一次操作过后, 只剩下两个不相交的正方形, 那么下一次操作的人必败 所以最优策略一定是轮流选知道最后只剩下两个不相交的正方形(其余点全被选)

判断除两个 k*k 的空正方形之外空点的奇偶性即可.

Code 

#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define I int #define ll long long #define F(i,a,b) for(I i=a;i<=b;i++) #define Fd(i,a,b) for(I i=a;i>=b;i--) #define mem(a,b) memset(a,b,sizeof a) #define N 1004 using namespace std; I n,k,a[N][N],bz[N][N],s; char c; void R(I &x){ I w=1;x=0;c=getchar(); while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=w; } void o(I x){printf(x?"rx\n":"yc\n");} I main(){ freopen("lcyrcx.in","r",stdin); freopen("lcyrcx.out","w",stdout); R(n),R(k); F(i,1,n){ F(j,1,n){ c=getchar(); while(c!='0'&&c!='1') c=getchar(); a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]; if(c=='1') a[i][j]++; } } F(i,1,n-k+1){ F(j,1,n-k+1) if(!bz[i][j]){ if(!(a[i+k-1][j+k-1]-a[i-1][j+k-1]-a[i+k-1][j-1]+a[i-1][j-1])){ ++s; F(x,i,i+k-1){ F(y,j,j+k-1) bz[x][y]=1; } } } } if(!s) o(0); else{ if(s==1) o(1); else{ s=n*n-a[n][n]-2*k*k; if(s&1) o(1); else o(0); } } return 0; }