hdu 3032 Nim or not Nim? 打sg表

题目链接

给出n堆石子， 每次可以取一堆中的任意x个（x>=1), 或者将一堆石子拆成两堆， 取到最后一堆的胜。

这个题需要打sg表找规律， 打表程序看代码。

 #include<bits/stdc++.h>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, a, n) for(int i = a; i<n; i++)

 #define ull unsigned long long

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {-, }, {, }, {, -}, {, } };

 int sg[];

 int mex(int x) {

     if(~sg[x])

         return sg[x];

     int vis[];

     mem(vis);

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

         sg[i] = mex(i);

         vis[sg[i]] = ;

     }

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

         int ans = ;

         ans ^= sg[i];

         ans ^= sg[x-i];

         vis[ans] = ;

     }

     for(int i = ; ; i++)

         if(!vis[i])

             return i;

 }

 int main()

 {

     int t, n, x;

     cin>>t;

     while(t--) {

         scanf("%d", &n);

         int ans = ;

         while(n--) {

             scanf("%d", &x);

             if(x%==)

                 x--;

             else if(x%==)

                 x++;

             ans ^= x;

         }

         if(ans)

             cout<<"Alice"<<endl;

         else

             cout<<"Bob"<<endl;

     }

     return ;

 }