【poj2960】 S-Nim
http://poj.org/problem?id=2960 (题目链接)
题意
经典Nim游戏，只是给出了一个集合S，每次只能取S[i]个石子。
Solution
${g(x)=mex{SG(x-s[1]),SG(x-s[2])……}}$
数据范围很小，可以暴力求SG，顺便记忆化一下。不知道为什么用map就TLE了。。。只好开数组了。
代码
// poj2960
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
LL x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=10010;
int k,n,m,sg[maxn],s[maxn];
void calsg(int x) {
if (sg[x]!=-1) return;
//map<int,bool> mark;
bool mark[10010];
memset(mark,0,sizeof(mark));
int temp;
for (int i=1;i<=k;i++) {
temp=x-s[i];
if (temp>=0) {
if (sg[temp]==-1) calsg(temp);
mark[sg[temp]]=1;
}
}
for (int i=0;;i++) if (!mark[i]) {sg[x]=i;return;}
}
int main() {
while (scanf("%d",&k)!=EOF && k) {
for (int i=1;i<=k;i++) scanf("%d",&s[i]);
sg[0]=0;
for (int i=1;i<=maxn;i++)
sg[i]=-1;
scanf("%d",&m);
while (m--) {
scanf("%d",&n);
int ans=0;
while (n--) {
int x;scanf("%d",&x);
if (sg[x]==-1) calsg(x);
ans^=sg[x];
}
if (ans) printf("W");
else printf("L");
}
printf("
");
}
return 0;
}