AcWing 891：Nim游戏 ← SG函数 + Nim博弈

【题目来源】https://www.acwing.com/problem/content/893/【题目描述】给定 n 堆石子两位玩家轮流操作每次操作可以从任意一堆石子中拿走任意数量的石子可以拿完但不能不拿最后无法进行操作的人视为失败。问如果两人都采用最优策略先手是否必胜。【输入格式】第一行包含整数 n。第二行包含 n 个数字其中第 i 个数字表示第 i 堆石子的数量。【输出格式】如果先手方必胜则输出 Yes。否则输出 No。【输入样例】22 3【输出样例】Yes【数据范围】1≤n≤10^51≤每堆石子数≤10^9【算法分析】●Nim 博弈定理对于任意的 {a1, a2, a3, …, an}若Sa1⊕a2⊕a3⊕⋯⊕an的值不等于 0先手必胜记为 N-position先手必胜态。若 Sa1⊕a2⊕a3⊕⋯⊕an 的值等于 0先手必败记为 P-position先手必败态。● 标准 Nim 堆的 SG 函数值对于标准 Nim 的单堆石子状态 x 表示堆内有 x 枚石子。取走任意非零1~x枚石子可得状态 x 的后继集合为 {0, 1, …, x-1}。故sg(x)mex{sg(0), sg(1), …, sg(x-1)}。x1后继为 1-10后继 SG 集合为 {SG(0)}{0}则得 SG(1)mex{0}1 x2后继为 2-112-20后继 SG 集合为 {SG(1),SG(0)}{1,0}则得 SG(2)mex{0,1}2 x3后继为 3-123-213-30后继 SG 集合为 {SG(2),SG(1),SG(0)}{2,1,0}则得 SG(3)mex{0,1,2}3 x4后继为 4-134-224-314-40后继 SG 集合为 {SG(3),SG(2),SG(1),SG(0)}{3,2,1,0}则得 SG(4)mex{0,1,2,3}4 …… 猜想一般式SG(x)x。故数学归纳可得标准 Nim 堆的 SG 函数为sg(x)x。【算法代码一SG函数写法】#include bits/stdc.h using namespace std; int SG(int x) { return x; } int main() { int n,t0; cinn; while(n--) { int x; cinx; t^SG(x); } if(t0) coutNo; else coutYes; return 0; } /* in: 2 2 3 out: Yes */【算法代码二非SG函数写法】#include bits/stdc.h using namespace std; int main() { int n,t0; cinn; while(n--) { int x; cinx; t^x; } if(t0) coutNo; else coutYes; return 0; } /* in: 2 2 3 out: Yes */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/158704426https://www.acwing.com/file_system/file/content/whole/index/content/12084580/