284
HDU 1536 SG函數
這題也是一道sg函數的模板題，沒有任何變形，明確了允許移動的數目範圍後可以用SG函數直接解決，記住SG要將S數組中的數從小到大排序。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int k,num[120],f[10002];
int mex1(int p)
{
int i,t;
bool g[101]= {0};
for(i=0; i<k; i++)
{
t=p-num[i];
if(t<0)
break;
if(f[t]==-1)
f[t]=mex1(t);
g[f[t]]=1;
}
for(i=0;; i++)
if(!g[i])
return i;
}
int main()
{
while(~scanf("%d",&k),k)
{
memset(f,-1,sizeof(f));
f[0]=0;
for(int i=0; i<k; i++)
scanf("%d",&num[i]);
sort(num,num+k);
int n,m,s;
for(int i=1; i<=10000; i++)
f[i]=mex1(i);
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
s=0;
int x;
for(int i=0; i<m; i++)
scanf("%d",&x),s^=f[x];
if(s)
printf("W");
else
printf("L");
}
printf("\n");
}
return 0;
}
最後更新：2017-04-04 07:03:54