【BZOJ1434】[ZJOI2009]染色游戏（博弈论）

题面

BZOJ

洛谷

题解

翻硬币的游戏我似乎原来在博客里面提到过，对于这类问题，当前局面的\(SG\)函数就是所有反面朝上的硬币单一存在时的\(SG\)函数的异或和。现在要考虑的是如何求解单一硬币存在于场上时的\(SG\)函数，这种东西。。。。打表吧。。。

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int lowbit(int x){return x&(-x);}

int getSG(int i,int j)

{

	if(i&&j)return i+j;

	return log2(lowbit(i+j+1));

}

int n,m,SG;char g[500];bool vis[500];

int main()

{

	int T=read();

	while(T--)

	{

		n=read();m=read();SG=0;

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

		{

			scanf("%s",g);

			for(int j=0;j<m;++j)

				if(g[j]=='T')

					vis[getSG(i,j)]^=1;

		}

		for(int i=0;i<n+m-1;++i)if(vis[i])SG=1;

		puts(SG?"-_-":"=_=");

		for(int i=0;i<n+m-1;++i)vis[i]=0;

	}

	return 0;

}