学步园

题意：有L堆得珠子，Arthur 和 Caroll两个人轮流取，但每次取的个数是在集合S中选择，假如S={2，5}，那就只能选择拿2个或者5个。判断起始位置是winning position 打印 'W'，是losing position 打印 'L'。

思路：简单，求SG值

代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


int f[101];//记录S的值
int sg[10001];
int k;
char str[101];//记录打印的值

int cmp(const int *a,const int *b)
{
	return *a-*b;
}

int mex(int b)
{
	int a[101]={0};
    int i;
    for(i=0;i<k;i++)
    {
        if(b-f[i]<0)//b-f无后继点
            break;
        if(sg[b-f[i]]==-1)
        {
            sg[b-f[i]]=mex(b-f[i]);
        }
        a[sg[b-f[i]]]=1;
    }
    for(i=0;i<=k;i++)//总共只有K个数，所以sg值不会超过K
        if(!a[i])
        {
            return i;
        }
}

int main()
{
    int i,t,n,s,bead,num;
    while(scanf("%d",&k),k)
    {
        for(i=0;i<k;i++)//输入S值
        {
            scanf("%d",&f[i]);
        }
        memset(sg,-1,sizeof(sg));
	    
		//puts("adsad");
  
		qsort(f,k,sizeof(int),cmp);
       
		//puts("adsa");

        sg[0]=0;
		num=0;
        scanf("%d",&t);//测试个数
        while(t--)
        {
            scanf("%d",&n);//堆数
            s=0;
            while(n--)
            {
                scanf("%d",&bead);//该堆的成员个数
                if(sg[bead]==-1)
                    sg[bead]=mex(bead);
                s=s^sg[bead];
            }
            if(s==0)
                str[num]='L';
            else
                str[num]='W';
			num++;
        }
		str[num]=0;
		puts(str);
    }
    return 0;
}