测试地址：S-Nim 题目大意：有 L 堆珠子，每堆珠子数量可能不同（最大可能为N=10000），双方轮流行动，每次行动从一堆珠子中取出若干颗，取出的珠子数量必须是一个正整数集合 S 中的一个数，若轮到某一方时不能按照规则行动，那么这一方判负，给出初始状态和集合S，问先手必胜还是先手必败。 1≤L,|S|≤100 。 做法：这一题需要用到SG函数的知识。 具体做法请参看我写的文章：我对SG函数的理解。我在这篇文章的最后讲到了如何使用SG函数解决这一道题。 以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int n,m,s[110],srt[10010]={0},sg[10010]; bool cmp(int a,int b) {return a<b;} void calc_sg() { sg[0]=0; for(int i=1;i<=10000;i++) { for(int j=1;j<=n;j++) if (i>=s[j]) srt[sg[i-s[j]]]++; for(int j=0;j<=n;j++) if (!srt[j]) {sg[i]=j;break;} for(int j=1;j<=n;j++) if (i>=s[j]) srt[sg[i-s[j]]]--; } } int main() { while(scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) scanf("%d",&s[i]); calc_sg(); scanf("%d",&m); for(int i=1;i<=m;i++) { int l,sum=0; scanf("%d",&l); for(int j=1,a;j<=l;j++) { scanf("%d",&a); sum^=sg[a]; } if (!sum) printf("L"); else printf("W"); } printf("\n"); } return 0; }