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
");
            for(int i=1;i<tot;i++)
                printf("%d ",v[i]+1);
            printf("%d
",v[tot]+1);
        }
        else printf("LOSING

");
    }
    return 0;
}