【UVA10561】Treblecross（SG函数）

题意：有n个格子排成一行，其中一些格子里面有字符X。两个游戏者轮流操作，每次可以选一个空格，在里面放上字符X。

如果此时有3个连续的X出现，则该游戏者赢得比赛。初始条件下不会有3个X连续出现。

判断先手胜负情况，若必胜则升序输出先手第一步的所有可选必胜策略

n<=200

思路：如果有XX或者X.X出现则一定先手胜

一个结论：X的旁边和旁边的旁边不能放X

于是整个游戏被不能放X的区域分成了若干个独立的片段，每次都可以选择一个片段进行游戏，就是若干个游戏的和

由于每个棋盘片段都是连续的，想到用一个正整数（即长度）来表示状态，g(x)表示由连续的x个格子组成的棋盘所对应的SG函数值

则有递推方程g(x)=mex(g(x-3),g(x-4),g(x-5),g(1)^g(x-6),g(2)^(x-7)……)

有了g函数，很容易算出初始局面的SG函数，所有使得后继专题SG值为0的决策即为所求

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 typedef long long ll;

 using namespace std;

 #define N   21000

 #define oo  10000000

 #define MOD 1000000007

 int g[N],flag[N],b[N],c[N],d[N],n;

 char a[N];

 int isok(int x)

 {

     int k=;

     a[x]='X';

     for(int i=;i<=n-;i++)

     {

         if(a[i]=='X'&&a[i+]=='X'&&a[i-]=='.'){k=i-; break;}

         if(a[i]=='X'&&a[i-]=='X'&&a[i+]=='.'){k=i+; break;}

         if(a[i]=='.'&&a[i-]=='X'&&a[i+]=='X'){k=i; break;}

     }

     if(k)

     {

         a[x]='.';

         return ;

     }

     for(int i=;i<=n;i++) b[i]=;

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

      if(a[i]=='X')

       for(int j=-;j<=;j++)

        if(i+j>&&i+j<=n) b[i+j]=;

     int ans=;

     int s=;

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

      if(b[i]==) s++;

       else if(s)

       {

          ans^=g[s];

         s=;

       }

      if(s) ans^=g[s];

      a[x]='.';

      if(ans) return ;

      return ;

 }

 int main()

 {

     //freopen("uva10561.in","r",stdin);

     //freopen("uva10561.out","w",stdout);

     g[]=;

     g[]=g[]=g[]=;

     g[]=g[]=;

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

     {

         memset(flag,,sizeof(flag));

         for(int j=;j<=;j++) flag[g[i-j]]=;

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

          if(i-j>=) flag[g[j-]^g[i-j]]=;

         int j=;

         while(flag[j]) j++;

         g[i]=j;

     }

     //for(int i=1;i<=200;i++) printf("%d %d\n",i,g[i]);

     int cas;

     scanf("%d",&cas);

     while(cas--)

     {

         scanf("%s",a+);

         n=strlen(a+);

         for(int i=;i<=n;i++) d[i]=;

         for(int i=;i<=n-;i++)

         {

              if(a[i]=='X'&&a[i+]=='X'&&a[i-]=='.') d[i-]=;

              if(a[i]=='X'&&a[i-]=='X'&&a[i+]=='.') d[i+]=;

              if(a[i]=='.'&&a[i-]=='X'&&a[i+]=='X') d[i]=;

         }

         for(int i=;i<=n;i++) b[i]=;

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

          if(a[i]=='X')

           for(int j=-;j<=;j++)

            if(i+j>&&i+j<=n) b[i+j]=;

         int ans=;

         int s=;

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

          if(b[i]==) s++;

           else if(s)

           {

               ans^=g[s];

               s=;

           }

         if(s) ans^=g[s];

         s=;

         for(int i=;i<=n;i++) s+=d[i];

         if(ans||s)

         {

             printf("WINNING\n");

             int m=;

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

              if(a[i]=='.'&&isok(i)) d[i]=;

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

              if(d[i]) c[++m]=i;

             for(int i=;i<=m-;i++) printf("%d ",c[i]);

             printf("%d\n",c[m]);

         }

          else

          {

              printf("LOSING\n");

              printf("\n");

          }

     }

     return ;

 }