s-nim(博弈sg).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int k,s[110];
int m,h,n;
int sg[11000];

int dfs(int pos)
{
	int i,j;
	if (pos ==0 || pos < s[0]) {
		sg[pos] = 0;
		return 0;
	}
	if (sg[pos] != -1) {
		return sg[pos];
	}
	bool v[110];//晕倒,这题的SG值原来这么小
	memset(v,0,sizeof(v));
	for (i=0;i<k;i++) {
		if (s[i] > pos) {
			break;
		}
		v[ dfs(pos - s[i]) ] = true;
	}
	for (i=0;i<=100;i++) {
		if (!v[i]) {
			break;
		}
	}
	sg[pos] = i;
	return i;
}

int main()
{
	int i,j,hmax,xor;
	while (scanf("%d",&k),k) {
		memset(sg,-1,sizeof(sg));
		for (i=0;i<k;i++) {
			scanf("%d",&s[i]);
		}
		sort(s,s+k);
		scanf("%d",&m);
		for (i=0;i<m;i++) {
			scanf("%d",&n);
			xor = 0;
			for (j=0;j<n;j++) {
				scanf("%d",&h);
				dfs(h);
				xor ^= sg[ h ];
			}
			if (xor == 0) {
				printf("L");
			}
			else {
				printf("W");
			}
		}
		printf("\n");
	}
}