UVA1378 A Funny Stone Game —— SG博弈

题目链接：https://vjudge.net/problem/UVA-1378

题意：

两个人玩游戏，有n堆石子，两人轮流操作：于第i堆石子中取走一块石子，然后再往第j、k堆中各添加一块石子。其中 i<j, j<=k。最后一次操作的为赢家，问先手能否必胜，如果能，请输出第一步操作。

题解：

1.把每个石子都看成是一个子游戏，所以在第i堆的其中一个石子，它的下一步为第j堆和第k堆；即这个子游戏又可以分解为两个子游戏。

2.由于在同一堆里的石子状态完全相同，所以当这堆石子的个数为偶数时，他们的SG值异或和为0；当个数为奇数时，他们的SG值异或和即为单独一个石子的SG值。

3.那么怎么求在第i堆里一个石子的SG值呢？一般情况下子游戏的下标是较小的，而处于第i堆的石子游戏又可以分解为处于第j、k石子的子游戏，然后i是小于j、k的，所以我们就把下标翻过来，这样就满足的SG的求值过程。初始状态为SG[0] = 0，即位于第0堆时，无法操作，即无后续状态，所以 SG[0] = mex{} = 0。

4.至于输出第一步，枚举ijk，得到一个必败状态即可。为何是必败状态？因为先手是处于必胜状态，当先手操作了一轮之后，轮到后手，而后手就处于必败状态。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = +;

 int a[MAXN], SG[MAXN], vis[];

 void getSG()

 {

     SG[] = ;

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

     {

         memset(vis, , sizeof(vis));

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

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

                 vis[SG[j]^SG[k]] = ;   //下一个状态，由两个子游戏组成，故异或。

         for(int j = ;;j++) if(!vis[j]) {

             SG[i] = j;

             break;

         }

     }

 }

 int main()

 {

     getSG();

     int n, kase = ;

     loop:

     while(scanf("%d",&n) && n)

     {

         int val = ;

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

         {

             scanf("%d", &a[i]);

             if(a[i]%) val ^= SG[n--i];    //当个数为奇数时，才有效

         }

         printf("Game %d: ", ++kase);

         for(int i = ; i<n-; i++)  //枚举、模拟第一步操作

         {

             if(a[i]==) continue;   //如果这堆没有石子，那就不能取了。

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

             for(int k = j; k<n; k++)   //取走i堆一块石子，往j、k堆中各加一个石子，即撤销i堆中一个子游戏

                 if((val^SG[n-i-]^SG[n--j]^SG[n--k])==){ //j、k堆中增加一个游戏。异或的作用是：有则去之无则添之。

                     printf("%d %d %d\n", i, j, k);

                     goto loop;

                 }

         }

         printf("-1 -1 -1\n");

     }

     return ;

 }