[学习笔记]Nim游戏

社团招新题 附加题T1

好吧我忘干净了

题目描述

	有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）

思路解析

首先考虑简单情况

只有两堆石头

一堆x 一堆y

记为（x,y）

可以得到二维表格

先确定几条定理：

1. 无法操作 必败
2. 对于无论所有操作都会到达必胜局面的 必败
3. 可以到达必败局面的 必胜

必胜为1 必败为0

如图可知 两堆石子相等时为必败局面

推广到三堆

只要把其中两堆视作一个整体

就变为两堆问题

初步结论

每次操作尽可能使两堆石子数量相等

关于进阶

Nim值：当前规则下的石子数，等效于普通规则下的石子数

Nim值的计算:所有操作能到达局面的从未出现过的最小非负整数

这个我还不会

最终结论

每堆石子的异或和为0则 必败

反之 必胜