hdu 3980 Paint Chain sg函数

题目链接

给一个长度为n的环， 两个人轮流涂色， 每次涂m个连续的， 无法继续涂了就输。

 #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[], m;

 int mex(int x) {

     if(~sg[x])

         return sg[x];

     if(x<m)

         return sg[x] = ;

     int vis[];

     mem(vis);

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

         vis[mex(i)^mex(x-m-i)] = ;         //相当于把一堆个数为x的石子分成两堆， 一堆个数为i， 另一堆为x-m-i

     }

     int i = ;

     while() {

         if(!vis[i])

             return sg[x] = i;

         i++;

     }

 }

 int main()

 {

     int t, n, cnt = ;

     cin>>t;

     while(t--) {

         mem1(sg);

         scanf("%d%d", &n, &m);

         printf("Case #%d: ", cnt++);

         if(n<m) {

             puts("abcdxyzk");

             continue;

         }

         sg[n-m] = mex(n-m);

         if(!sg[n-m]) {

             puts("aekdycoin");

         } else {

             puts("abcdxyzk");

         }

     }

     return ;

 }