893. 集合-Nim游戏
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 k，表示数字集合 S 中数字的个数。
第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
输入样例：
2 2 5 3 2 4 7 讯享网
输出样例：
讯享网Yes
公式推导：
将每一个h[i]h[i]的所有方案看做是一张有向图，例
若S=[2,5],h=10,则有如下展开形式：
mex()：设集合S是一个非负整数集合，定义mex(S)为求出不属于S的最小非负整数的运算，即：mes(S)=min[x],其中x属于自然数，且x不属于S（用人话说就是不存在S集合中的数中，最小的那个数）
SG()：在有向图中，对于每个节点x，设从x出发共有k条有向边，分别达到节点y1，y2……yk，定义SG(x)为x的后继节点的SG值构成的集合执行mex()运算后的值
即：SG(x)=mex(SG(y1),SG(y2)…SG(yk))；（用人话说就是比后继节点的SG都小的值）
特别的整个图G的SG值被定义为起点s的SG值，即SG(G)=SG(s)
上图标红的值就是每一个节点的SG值
性质：1.SG(i)=k，则i最大能到达的点的SG值为k−1。
2.非0可以走向0
3.0只能走向非0
定理：
对于一个图G，如果SG(G)!=0，则先手必胜，反之必败
证明：
若SG(G)=!0，
1.根据性质2，先手必可以走向0，
2.因此留给后手的是0，根据性质3，后手只能走向非0
3.以此类推，后手始终无法走向0，后手永远处于非0，当先手到达终点的0时，先手获胜
（由此我们可以知道，有些事是命中注定的~~~）
反之同理，必败
定理：
对于n个图，如果SG(G1) ^ SG(G2) ^ … SG(Gn)!=0,则先手必胜，反之必败
证明（类似与Nim游戏）：
①当SG(Gi)=0 时 ，xor=0 ， 显然先手必败
（PS：结束状态必是状态①，但状态①不一定是结束状态）
③当xor=0时，当移动任何一个节点时，对应的SG值必然减小，可以证明：xor!=0
下证：xor!=0
假设xor=0,则说明移动的那个节点的值并没有变化，即从SG(k)变成了k，但是这与SG函数的性质1相矛盾，因此不成立
代码：
#include <bits/stdc++.h> using namespace std; const int N = 110, M = 1e4 + 10; typedef long long LL; int n, k; int s[N], f[M]; int sg(int x) { if (f[x] != -1) return f[x]; unordered_set<int> S; for (int i = 0; i < k; i++) { int temp = s[i]; if (x >= temp) S.insert(sg(x - temp)); } for (int i = 0;; i++) { if (!S.count(i)) return f[x] = i; } } int main() { cin >> k; for (int i = 0; i < k; i++) cin >> s[i]; cin >> n; memset(f, -1, sizeof f); int res = 0; for (int i = 0; i < n; i++) { int temp; cin >> temp; res ^= sg(temp); } if (res) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/63105.html