SG函数

SG函数模板：

 1 void getSG(int *s,int t){
 2     int i,j;
 3     memset(sg,0,sizeof(sg));
 4     for(i=1; i<maxn; i++){
 5         memset(Hash,0,sizeof(Hash));
 6         for(j=0; j<t; j++)
 7             if(i - s[j] >= 0)
 8                 Hash[sg[i-s[j]]] = 1;
 9         for(j=0; j<maxn; j++)
10             if(!Hash[j])
11                 break;
12         sg[i] = j;
13     }
14 }

例子：HDU1536

这题有个小坑，一直时间超限，只要是Hash()类型定义为int了，改问bool速度就快多了。。。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1536

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 const int maxn = 10005;
 6 int a[105],sg[maxn];
 7 bool Hash[maxn];
 8 using namespace std;
 9 
10 void getSG(int *s,int t){
11     int i,j;
12     memset(sg,0,sizeof(sg));
13     for(i=1; i<maxn; i++){
14         memset(Hash,0,sizeof(Hash));
15         for(j=0; j<t; j++)
16             if(i - s[j] >= 0)
17                 Hash[sg[i-s[j]]] = 1;
18         for(j=0; j<maxn; j++)
19             if(!Hash[j])
20                 break;
21         sg[i] = j;
22     }
23 }
24 int main(){
25     int n;
26     while(scanf("%d",&n)!=EOF,n){
27         for(int i = 0; i < n; i++){
28             scanf("%d",&a[i]);
29         }
30         sort(a, a+n);
31         getSG(a,n);
32         int m;
33         scanf("%d",&m);
34         while(m--){
35             int sum = 0, h;
36             scanf("%d",&h);
37             for(int i = 1; i <= h; i++){
38                 int v;
39                 scanf("%d",&v);
40                 sum ^= sg[v];
41             }
42             if(sum) printf("W");
43             else printf("L");
44         }
45         printf("
");
46     }
47     return 0;
48 }