記憶化検索sg関数HDU 1536
1045 ワード
//
// sg , sg http://blog.sina.com.cn/s/blog_83d1d5c70100y9yd.html
//sg[x]=mex{sg[x-p[i]]}
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#define Maxn 110
int A[Maxn],SG[10005];
int n;
void dfs(int x){
if(SG[x]!=-1) return ;
bool v[105];
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++){
int tmp=x-A[i];
if(tmp>=0){
if(SG[tmp]==-1)
dfs(tmp);
v[SG[tmp]]=1;
}
}
for(int i=0;i<105;i++)
if(!v[i]){
SG[x]=i;
return ;
}
return ;
}
int main()
{
int m,k,i,j;
while(~scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
memset(SG,-1,sizeof(SG));
scanf("%d",&m);
while(m--){
int ans=0;
int t;
scanf("%d",&t);
while(t--){
int x;
scanf("%d",&x);
if(SG[x]==-1)
dfs(x);
ans^=SG[x];
}
if(ans==0) putchar('L');
else putchar('W');
}
puts("");
}
return 0;
}