HDU 1536 求解SG函数

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<set>
 5 using namespace std;
 6 
 7 const int K=101;
 8 const int H=10001;
 9 int s[K],sg[H];
10 int k,m,h,n;
11 bool vis[K];
12 
13 
14 
15 //用set求SG的时候就会TLE。。。。好无语，改用vis就46ms/64ms.................有这么慢么。
16 void solve(){
17     int i,j;
18     sg[0]=0;
19     for(i=1;i<H;i++){
20     memset(vis,false,sizeof(vis));
21     for(j=0;j<k&&i>=s[j];j++){
22         vis[sg[i-s[j]]]=true;
23     }
24     j=0;
25     while(vis[j]){
26         j++;
27     }
28     sg[i]=j;
29     }
30 }
31 
32 int main(){
33     int i,j,x;
34     while(~scanf("%d",&k),k){
35         for(i=0;i<k;i++){
36             scanf("%d",&s[i]);
37         }
38         sort(s,s+k);
39         solve();
40         scanf("%d",&m);
41         for(i=0;i<m;i++){
42             x=0;
43             scanf("%d",&n);
44             for(j=0;j<n;j++){
45                 scanf("%d",&h);
46                 x=x^sg[h];
47             }
48             if(x){
49                 printf("W");
50             }
51             else{
52                 printf("L");
53             }
54         }
55         puts("");
56     }
57     return 0;
58 }