lightoj 1229 - Treblecross 博弈论

思路：SG函数

枚举先手的每一个位置是否有必胜。

1）如果出现了XXX则必胜；

2）如果出现了XX或X.X则必败；

3）否则计算后手的sg值和。

代码如下：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #define M 201

 using namespace std;

 char str[M];

 int sg[M],len;

 vector<int>p;

 int get_sg(int m) //计算SG值

 {

     if(m<) return ;

     if(sg[m]!=-) return sg[m];

     bool vis[]={};

     for(int i=;i<=m;i++)

         vis[get_sg(i-)^get_sg(m-i-)]=;

     int i=;

     while(vis[i]) i++;

     return sg[m]=i;

 }

 bool cal(int m)

 {

     char s[M];

     strcpy(s,str);

     if(s[m]=='X') return ;

     s[m]='X';

     for(int i=;i+<len;i++) //出现XXX

         if(s[i]=='X'&&s[i+]=='X'&&s[i+]=='X') return ;

     for(int i=;i+<len;i++) //出现XX

         if(s[i]=='X'&&s[i+]=='X') return ;

     for(int i=;i+<len;i++) //出现X.X

         if(s[i]=='X'&&s[i+]=='X') return ;

     int i,j,ans=;

     bool f=;

     for(i=,j=-;i<len;i++){ //计算后手的SG值和

         if(s[i]=='X'){

             if(f) ans^=get_sg(i-j-); //当两边都出现的X时要减去4

             else{

                 ans^=get_sg(i-j-); //当只有一边出现X时要减去2

                 f=;

             }

             j=i;

         }

     }

     ans^=get_sg(len-j-);

     return ans==;

 }

 int main()

 {

     int t,ca=;

     memset(sg,-,sizeof(sg));

     scanf("%d",&t);

     while(t--){

         scanf("%s",&str);

         len=strlen(str);

         p.clear();

         for(int i=;i<len;i++)

             if(cal(i)) p.push_back(i+);

         printf("Case %d:",++ca);

         if(p.size()){

             for(int i=;i<p.size();i++)

                 printf(" %d",p[i]);

             puts("");

         }

         else printf(" 0\n");

     }

     return ;

 }