首页 > 代码库 > UVA - 10561 Treblecross

UVA - 10561 Treblecross

题意:

技术分享

 

分析:

一行格子可被X分为两部分,一部分为X及其禁区(左右半径两格内),另一部分为安全区域可进行子游戏,根据SG定理,可通过计算若干个游戏的和来得到最终结果。

 Select Code


#include<cstdio>#include<cstring>using namespace std;const int N=205;int T,cnt,n,len,SG[N],ans[N];bool vis[N];char s[N];void GetSG(int n){	SG[0]=0;	SG[1]=SG[2]=SG[3]=1;	for(int i=4;i<=n;i++){		memset(vis,0,sizeof vis);		for(int j=1;j+2<=i;j++) if(j<=3) vis[SG[i-j-2]]=1;else vis[SG[j-3]^SG[i-j-2]]=1;		for(int j=0;j<=i;j++) if(!vis[j]){SG[i]=j;break;}	}}bool check(int x){//是否到达目标状态 	if(x>2) if(s[x-2]==‘X‘&&s[x-1]==‘X‘&&s[x]==‘X‘) return 1;	if(x>1) if(s[x-1]==‘X‘&&s[x]==‘X‘&&s[x+1]==‘X‘) return 1;	if(s[x]==‘X‘&&s[x+1]==‘X‘&&s[x+2]==‘X‘) return 1;	return 0;}bool GetRest(){//后手操作 	for(int i=1;i<=len;i++){		if(s[i]==‘.‘){			s[i]=‘X‘;			if(check(i)){				s[i]=‘.‘;				return 0;			}			s[i]=‘.‘;		}	}	int res=0,num=0;	for(int i=1;i<=len;i++){		if(s[i]==‘X‘||(i>1&&s[i-1]==‘X‘)||(i>2&&s[i-2]==‘X‘)||(i<len&&s[i+1]==‘X‘)||(i+2<=len&&s[i+2]==‘X‘)){			res^=SG[num];num=0;		}		else num++;	}	res^=SG[num];	return !res;}void solve(){	scanf("%s",s+1);len=strlen(s+1);cnt=0;	for(int i=1;i<=len;i++){//巧妙的处理,避免特判"XX","X.X" 		if(s[i]==‘.‘){			s[i]=‘X‘;			if(check(i)) ans[++cnt]=i;			else if(GetRest()) ans[++cnt]=i;			s[i]=‘.‘;		}	}	if(!cnt) puts("LOSING\n");	else{		puts("WINNING");		for(int i=1;i<=cnt;i++) printf("%s%d",i==1?"":" ",ans[i]);		putchar(‘\n‘);	}}int main(){	GetSG(200);	for(scanf("%d",&T);T--;) solve();	return 0;}

UVA - 10561 Treblecross