HDU 5794 - A Simple Nim

题意：
    n堆石子，先拿光就赢，操作分为两种：
        1.任意一堆中拿走任意颗石子
        2.将任意一堆分成三小堆 ( 每堆至少一颗 )

分析：
    答案为每一堆的SG函数值异或和.
    故先打表寻找单堆SG函数规律.
    其中，若 x 可分为三堆 a,b,c ，则 SG[x] 可转移至子状态 SG[a] ^ SG[b] ^ SG[c] （三堆SG值异或和）

    打表后发现:
        SG[ 8*k - 1 ] = 8*k
        SG[ 8*k ] = 8*k - 1
        其余 SG[x] = x;

    则可直接得出答案

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int MAXN = ;

 int T, n;

 int main()

 {

     scanf("%d", &T);

     while ( T-- )

     {

         scanf("%d", &n);

         int sg = ;

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

         {

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

             if (x %  == ) sg ^= (x - ) ;

             else if ( (x + ) %  == ) sg ^= (x + ) ;

             else sg ^= x;

         }

         if(sg) puts("First player wins.");

         else puts("Second player wins.");

     }

 }

 /*

 SG打表

 */

 #include <iostream>

 #include <cstring>

 using namespace std;

 int sg[];

 int GetSG(int x)

 {

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

     int vis[];

     memset(vis, , sizeof(vis));

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

         vis[GetSG(i) ] = ;

     int a,b,c;

     for(a = ; a <= x; a++)

         for(b = a; b <= x - a; b++)

             for(c = b; c <= x - a - b; c++)

                 if(a+b+c == x)

                 vis[GetSG(a) ^ GetSG(b) ^ GetSG(c)] = ;

     for(int i = ;; i++)

         if(!vis[i])  return sg[x] = i;

 }

 int main()

 {

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

     sg[] = ;

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

         if(sg[i] == -) GetSG(i);

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

         cout<<i<<" "<<sg[i]<<endl;

 }

巴特西

HDU 5794 - A Simple Nim

最新文章

热门文章