hdu 1536/1944 / POJ 2960 / ZOJ 3084 S-Nim 博弈论

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<vector>
 8 using namespace std;
 9 int sg[10001],k,a[101];
10 int getsg(int x)
11 {
12     if(sg[x]!=-1) return sg[x];
13     if(x-a[0]<0) return sg[x]=0;
14     bool vis[101];
15     memset(vis,0,sizeof(vis));
16     for(int i=0;i<k&&x-a[i]>=0;i++){
17         vis[getsg(x-a[i])]=1;
18     }
19     for(int i=0;;i++)
20         if(!vis[i])
21             return sg[x]=i;
22 }
23 int main(){
24     int i,j,n,m,ans,s;
25     while(scanf("%d",&k)&&k){
26         memset(sg,-1,sizeof(sg));
27         sg[0]=0;
28         for(i=0;i<k;i++) scanf("%d",&a[i]);
29         sort(a,a+k);
30         scanf("%d",&n);
31         for(i=0;i<n;i++){
32             scanf("%d",&m);
33             ans=0;
34             for(j=0;j<m;j++){
35                 scanf("%d",&s);
36                 ans^=getsg(s);
37             }
38             if(!ans) cout<<"L";
39             else cout<<"W";
40         }
41         cout<<endl;
42     }
43     return 0;
44 }