题目

https://gmoj.net/senior/#main/show/6826

题解

这是一道很好的欺诈题…… 乍一看，哇噻！状态那么多，又那么难记录。 然而并不用管这些，只要从特殊情况入手即可。 这可能就是这些博弈题的套路吧……

考虑没有合法正方形的情况，显然后手胜；考虑只有一个合法正方形或所有的合法正方形都至少有一个共用的格子的情况，只要在那个格子上放一个棋子就赢了，先手胜；如果有两个不相交的正方形，后手胜；那么剩下的情况就是把原图变成只有两个不相交的正方形，其它格子上全都有棋子的图形，然后下一个操作的人输（因为谁先动了这两个正方形中的其中一个格子谁就肯定输），因此判断其它格子的个数的奇偶性就好了。

记得前缀和优化……

CODE

#include<cstdio> using namespace std; #define N 1005 char c[N][N]; int a[N][N],b[N][N],list[1000005][2]; inline int abs(int x){return x>0?x:-x;} int main() { freopen("lcyrcx.in","r",stdin); freopen("lcyrcx.out","w",stdout); int k,n,i,j,s=0,ans=0,x,y; scanf("%d%d",&n,&k); for(i=1;i<=n;++i) scanf("%s",c[i]+1); for(i=1;i<=n;++i) for(j=1;j<=n;++j) a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+c[i][j]-'0'; for(i=k;i<=n;++i) for(j=k;j<=n;++j) if(a[i][j]+a[i-k][j-k]-a[i-k][j]-a[i][j-k]==0) b[i][j]=1,list[++s][0]=i,list[s][1]=j; if(!s) return puts("yc"),0; for(i=1;i<=n;++i) for(j=1;j<=n;++j) b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; for(i=1;i<=s;++i) { x=list[i][0],y=list[i][1]; if(b[x-k][y]||b[x][y-k]) goto out; } return puts("rx"),0; out: for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(c[i][j]=='0') ans^=1; puts(ans?"rx":"yc"); return 0; }