UVA 10561 Treblecross（博弈论）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=32209

【思路】

博弈论。

根据X分布划分禁区，每个可以放置的块为单独一个游戏。按长度定义状态，构造sg函数。依次试验每一种放法。

【代码】

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = +;

 int g[N],n;

 int mex(vector<int>& s) {

     if(s.empty()) return ;

     sort(s.begin(),s.end());

     if(s[]) return ;

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

         if(s[i]>s[i-]+) return s[i-]+;

     return s[s.size()-]+;

 }

 void get_g() {

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

     for(int i=;i<=N-;i++) {

         vector<int> s;

         s.push_back(g[i-]);

         s.push_back(g[i-]);

         if(i>=) s.push_back(g[i-]);

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

             s.push_back(g[j-] ^ g[i-j-]);

         g[i]=mex(s);

     }

 }

 bool winning(char *s) {

     int n=strlen(s);

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

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

     int no[N];

     memset(no,,sizeof(no));

     no[n]=;

     for(int i=;i<n;i++) if(s[i]=='X') {

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

             if(i+d>= && i+d<n) {

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

                 no[i+d]=;

             }

     }

     int sg=;

     int start=-;

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

         if(start< && !no[i]) start=i;

         if(no[i] && start>=) sg^=g[i-start];

         if(no[i]) start=-;

     }

     return sg!=;

 }

 int main() {

     get_g();

     int T; scanf("%d",&T);

     while(T--) {

         char s[N];

         scanf("%s",s);

         int n=strlen(s);

         if(!winning(s)) puts("LOSING\n");

         else {

             puts("WINNING");

             bool first=;

             for(int i=;i<n;i++) if(s[i]=='.') {

                 s[i]='X';

                 if(!winning(s))

                     if(first) printf("%d",i+) , first=;

                     else printf(" %d",i+);

                  s[i]='.';

             }

             putchar('\n');

         }

     }

     return ;

 }