首页 > 代码库 > Treblecross(uva 10561)

Treblecross(uva 10561)

题意:一个 1 × n 的棋盘,有 X :,当棋盘上出现三个连续的X 时游戏结束,两人轮流操作,每次能把一个 : 变成 X,问先手必胜方案数以及先手可以放的位置。

/*
    对于先手,当有一个‘X‘时,它周围的两个格子就都不能放‘X‘了,所以这样游戏就被分成了几个部分,据此设定SG函数。 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 210
using namespace std;
int SG[N],len,v[N];
char s[N],tmp[N];
int calc(int x){
    if(x<0) return 0;
    if(SG[x]!=-1) return SG[x];
    int vis[N];
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=x;i++)
        vis[calc(i-3)^calc(x-i-2)]=1;
    for(int i=0;;i++)
        if(!vis[i])
            return SG[x]=i;
}
bool judge(int pos){
    if(s[pos]==X) return false;
    for(int i=0;i<len;i++) tmp[i]=s[i];
    tmp[pos]=X;
    for(int i=0;i+2<len;i++)//不知道为什么写i<len就不对,明明数组没有越界啊,奇了怪了。。。 
        if(tmp[i]==X&&tmp[i+1]==X&&tmp[i+2]==X) return true;
    for(int i=0;i+1<len;i++)
        if(tmp[i]==X&&tmp[i+1]==X) return false;
    for(int i=0;i+2<len;i++)
        if(tmp[i]==X&&tmp[i+2]==X) return false;
    int ans=0,flag=0,w=2,last=-1;
    for(int i=len-1;i>=0;i--)
        if(tmp[i]==X){
            last=i;break;
        }
    for(int i=0,j;i<len;i++){
        if(i>last) w=0;
        if(tmp[i]==X){
            flag=2;continue;
        }
        for(j=i;j<len&&tmp[j]==.;j++);
        ans^=calc(j-i-w-flag);
        i=j-1;
    }
    return ans==0;
}
int main(){
    memset(SG,-1,sizeof(SG));
    int T;scanf("%d",&T);
    while(T--){
        int tot=0;
        scanf("%s",s);len=strlen(s);
        for(int i=0;i<len;i++)
            if(judge(i))
                v[++tot]=i;
        if(tot){
            printf("WINNING\n");
            for(int i=1;i<tot;i++)
                printf("%d ",v[i]+1);
            printf("%d\n",v[tot]+1);
        }
        else printf("LOSING\n\n");
    }
    return 0;
}

 

Treblecross(uva 10561)