sg 函数模版

 1 #define MAXN 1005
 2 
 3 using namespace std;
 4 
 5 int s[MAXN], ns;    //取值集合
 6 int sg[10005];
 7 
 8 int mex(int x)
 9 {
10     if(sg[x] != -1)
11         return sg[x];    
12     bool v[MAXN];        //x的后继集合
13     memset(v, 0, sizeof(v));
14     for(int i=0; i<ns; i++){    //求后继集合
15         int t = x-s[i];
16         if(t < 0)
17             continue;
18         sg[t] = mex(t);
19         v[sg[t]] = true;
20     }    
21     for(int i=0; i<MAXN; i++)    //从后继集合中找mex(x)
22         if(!v[i])
23             return (sg[x] = i);
24 }
25 
26 int main()
27 {    
28     memset(sg, -1, sizeof(sg));    
29     
30     return 0;
31 }

View Code

可以做一下 EOJ 1230 S-NIM

http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=1230