0X00 一个关于「异或」的前置知识
假设有：
那么一定存在一个 使
减去一个大于 0 的数字得到
证明过程如下（构造法）：
假设 s 的最高位是 m， 那么 中一定有一个
使得
的第 m 位一定是 1（反证法，如果所有都不是 1 那么 s 的 m 位一定是 0）。且
。
如果这里不好理解，我再举个例子
假设
, 也就是 m 位变成了 0 更高位不变所以一定变小
因此，只要我们让 变成
（减少一部分）等式左边变为
证毕
0X01 切一些简单题
掌握了这么一个前置知识以后，我们用这个前置知识来切题。
博弈论的题目，我们一般都得分析出来，如何才能够获胜。先看这一道题 Nim游戏
首先分析出「必胜态」和「必败态」游戏的最后一定是有一个人拿走一个石子后，就没有石子了。此时 n 堆石子异或为
我们现在有 就一定能够让对方处于
这一前置知识，所以只要当前
先手必胜！
接着我们来看一道变化的题目：
题目描述如下：
现在，有一个级台阶的楼梯，每级台阶上都有若干个石子，其中第i个石子(i≥1)两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。
这个题有一个小的变形
- 胜负与偶数台阶无关，因为如果先手移动偶数阶的石子到奇数阶，那么后手一定能够移动相同的石子到偶数阶。所以先手必败
将所有奇数阶的石子异或起来，如果不为 0。那么先手必胜，原因是先手一定能够使石子，使异或为 0。
0X02 sg 函数
首先我们来描述这样一个基础问题：
有 n 个石子，假设 A、B 可以轮流拿 1 或 2 颗石子，谁最后没有石子拿谁就输。问如果 A 先拿，A 是不是能够必胜。
这里我取 n = 5 并画出 n = 5 时的所有可能行
我们求出每个点的 sg 函数，一个节点的 sg 值是它所有子节点的 sg 值所不能到达的最小自然数。可能很抽象，我们举个例子（按照上这张图写出每个节点的 sg 值）：
- 0 谁也不能到达。所以 sg(0) = 0
- 1 能到达 0。sg(0) = 1 所以 sg(1) = 1
- 2 能到达 1 和 0。sg(0) = 0 sg(1) = 1所以 sg(2) = 2
- 3 能到达 2 和 1。sg(1) = 1 sg(2) = 2 所以 sg(3) = 0
- 4 能到达 2 和 3。sg(2) = 2 sg(3) = 0 所以 sg(4) = 1
- 5 能到达 4 和 3。sg(3) = 0 sg(4) = 1 所以 sg(5) = 2
下面给出这道题的结论，只要是 那么此节点一定是必败态。
这里可以用反证法证明：
如果 那么 i 这个节点一定能转移到 sg 等于 0 上的节点。而 sg 等于 0 的点要么可以转移到不为 0 的点（后手还是可以转移到另外一个 sg 不等于 0 的点上去），要么就是最后输了的状态。
sg 函数的一些简单拓展问题
- n 堆石子和 s 种拿法
代码如下：
from sys import stdin
def read():
return list(map(int, stdin.readline().split()))
def sg(n):
if f[n] != -1: return f[n]
t = set()
for c in cs:
if c <= n:
t.add(sg(n-c))
i = 0
while i in t:
i += 1
f[n] = i
return i
N = 10010
cn, cs = read()[0], read()
n, nums = read()[0], read()
f = [-1] * N
res = 0
for v in nums:
res ^= sg(v)
if res: print("Yes")
else: print("No")
- 拆分
代码如下：
from sys import stdin
def read(n = 2):
if n == 1:
return int(stdin.readline())
return map(int, stdin.readline().split())
N = 110
n = read(1)
nums = read()
f = [-1] * N
def sg(x):
if f[x] != -1: return f[x]
t = set()
for i in range(x):
for j in range(i+1):
t.add(sg(i) ^ sg(j))
i = 0
while i in t:
i += 1
f[x] = i
return i
res = 0
for v in nums:
res ^= sg(v)
if not res:
print("No")
else:
print("Yes")
网友评论