盒子

[hdu1536]S-Nim_博弈(SG函数)

题目:HDU1536
题意:有k种取石头的方法,m次查询,问你每次给定l堆,判断先手是赢是输。
思路:好坑啊,这道题不能提前预处理出所有的sg函数值,否则会TLE,因此只能通过递归+记忆化来求取SG值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//800 KB	125 ms
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[105];
int g[10005];
int k;
int sg(int n) {
int has[101]={0};
int i;
for(i=0;i<k;i++){
if(n<a[i])break;
if(g[n-a[i]]==-1)g[n-a[i]]=sg(n-a[i]);
has[g[n-a[i]]]=1;
}
for(i=0;;i++)
if(has[i]==0)return i;
}
int main() {
int cnt,n,m,i,l;
while(scanf("%d",&k)!=EOF&&k) {
memset(g,-1,sizeof(g));
for(i=0; i<k; i++)
scanf("%d",&a[i]);
sort(a,a+k);
scanf("%d",&m);
while(m--) {
cnt=0;
scanf("%d",&l);
for(i=0; i<l; i++) {
scanf("%d",&n);
if(g[n]==-1)g[n]=sg(n);
cnt^=g[n];
}
if(cnt)printf("W");
else printf("L");
if(m==0)printf("\n");
}
}
return 0;
}