poj -2960 S-Nim（SG模板）

S-Nim

题意 :有$l$堆石子，两个人轮流从其中一堆石子中取一定数量的石子，能取的数量有$k$种，问先手是否能赢。 题解 :$SG$裸模板。注意他给你的$k$种数量可能不是按照升序给你的，所以要先$sort$一下。

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10007; int k, m, l, h; int f[120]; int SG[maxn],S[maxn]; void getSG(){ memset(SG,0,sizeof(SG)); for(int i = 1; i <= 10000; i++){ //因为SG[0]始终等于0，所以i从1开始 memset(S,0,sizeof(S)); //每一次都要将上一状态 的 后继集合 重置 for(int j = 0; f[j] <= i && j < k; j++) S[SG[i-f[j]]] = 1; //将后继状态的SG函数值进行标记 for(int j = 0;; j++) if(!S[j]){ //查询当前后继状态SG值中最小的非零值 SG[i] = j; break; } } } void gao() { scanf("%d", &l); int res = 0; while (l--) { scanf("%d", &h); res ^= SG[h]; } if (res == 0) printf("L"); else printf("W"); } void solve() { for (int i = 0; i < k; ++i) scanf("%d", &f[i]); sort(f, f + k); getSG(); scanf("%d", &m); while (m--) gao(); puts(""); } int main() { // freopen("in.txt", "r", stdin); while (~scanf("%d", &k), k) solve(); return 0; }