这道题是对SG函数的考查
#include <iostream> #include <stdio.h> #include <string> #include <string.h> #include <algorithm> #include <math.h> #include <vector> #include <map> #include <queue> #include <stack> #include <stdlib.h> using namespace std; const int maxn=10005; int sg[maxn]; int s[maxn]; int k,m; int mex(int v){ if(sg[v]!=-1)return sg[v]; bool vis[100+10];//千万不要定义全局变量,怎么找也找不到错。DFS次数比较多值会改变 memset(vis,0,sizeof(vis)); for(int i = 0;i < k;i++){ if(v-s[i]>=0){ int tmp=mex(v-s[i]); //sg[v-s[i]]=tmp ; vis[tmp]=1; } } for(int i=0;;i++){ if(vis[i]==0){ sg[v]=i; break; } } return sg[v]; } int main(){ int x ; while(scanf("%d",&k)&&k){ for(int i = 0;i < k;i++) scanf("%d",s+i); sort(s,s+k); memset(sg,-1,sizeof(sg)); sg[0]=0; scanf("%d",&m); while(m--){ int l; scanf("%d",&l); int ans = 0; for(int i = 0;i < l;i++){ scanf("%d",&x); if(sg[x]==-1) sg[x]=mex(x) ; ans ^= sg[x]; } if(ans) printf("W"); else printf("L"); } printf("\n"); } return 0; }