uva 10561 treblecross

NIM游戏的变形题：uva10561

需要理解NIM游戏的精髓，然后知道应该怎么建模，才能搞这个题

题意：从1到n总共有n个格子，初始状态有的格子中有棋子，有的没有；要求出现连续三个格子中都有棋子为胜利状态

问先手是否可胜，如果可胜，按照升序的顺序输出所有的可胜的第一步走法

如果是不可胜，输出LOSING

这个题为什么和NIM有关，就是可以将初始状态分解成多个子状态

如：。。。。。。。。。。 X  。。。。。。。。。

前面的状态与后面的状态无关的，所以前面的可以用sg函数算出来，后面也可以

然后把所有的都异或起来，就可以知道是不是先手可胜

所以，只需要处理先手第一步必胜，或者先手走完之后给后手留下了必胜状态，剩下的用sg函数处理所有的空白格子就好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

const int maxn=210;
int t,res[maxn],way,len,sg[maxn];
char str[maxn];

bool judge(){
	for(int i=0;i<len-2;i++)
		if (str[i]=='X'&&str[i+1]=='X'&&str[i+2]=='X')
			return true;
	return false;
}

int getsg(int x){
	if (sg[x]!=-1) return sg[x];
	if (x==0) return sg[x]=0;
	int vis[maxn],t;
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=x;i++){
		int t=getsg(max(0,i-3))^getsg(max(0,x-i-2));
		vis[t]=true;
	}
	for(int i=0;;i++){
		if (vis[i]) continue;
		return sg[x]=i;
	}
}

int getres(){
	for(int i=0;i<len;i++)
		if (str[i]=='.'){
			str[i]='X';
			if (judge()){
				str[i]='.';
				return false;
			}
			str[i]='.';
		}
	int ans=0,num=0;
	for(int i=0;i<len;i++)
		if (str[i]=='X'||(i>=1&&str[i-1]=='X')||(i>=2&&str[i-2]=='X')||(i+1<len&&str[i+1]=='X')||(i+2<len&&str[i+2]=='X')){
			ans^=getsg(num);
			num=0;
		}
		else num++;
	ans^=getsg(num);
	return ans==0;
}

void solve(){
	way=0;
	len=strlen(str);
	for(int i=0;i<len;i++){
		if (str[i]!='.') continue;
		str[i]='X';
		if (judge()||getres())
			res[++way]=i+1; 
		str[i]='.';
	} 
}

int main(){
	//freopen("input.txt","r",stdin);
	memset(sg,-1,sizeof(sg));
	scanf("%d",&t);
	while(t--){
		scanf("%s",str);
		solve();
		if (way==0) puts("LOSING\n");
		else{
			puts("WINNING");
			for(int i=1;i<=way;i++)
				printf("%d%c",res[i],i==way?'\n':' ');
		}
	}
	return 0;
}