首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。