0X00 一個關(guān)于「異或」的前置知識
假設(shè)有：
那么一定存在一個 使
減去一個大于 0 的數(shù)字得到
證明過程如下（構(gòu)造法）：
假設(shè) s 的最高位是 m波势， 那么 中一定有一個
使得
的第 m 位一定是 1（反證法橄教，如果所有都不是 1 那么 s 的 m 位一定是 0）。且
载佳。
如果這里不好理解，我再舉個例子
假設(shè)
, 也就是 m 位變成了 0 更高位不變所以一定變小
因此臀栈，只要我們讓 變成
（減少一部分）等式左邊變?yōu)?/p>
證畢
0X01 切一些簡單題
掌握了這么一個前置知識以后，我們用這個前置知識來切題挠乳。
博弈論的題目权薯，我們一般都得分析出來，如何才能夠獲勝睡扬。先看這一道題 Nim游戲
首先分析出「必勝態(tài)」和「必敗態(tài)」游戲的最后一定是有一個人拿走一個石子后盟蚣，就沒有石子了。此時 n 堆石子異或?yàn)?/p>
我們現(xiàn)在有 就一定能夠讓對方處于
這一前置知識卖怜，所以只要當(dāng)前
先手必勝屎开！
接著我們來看一道變化的題目：
題目描述如下：
現(xiàn)在，有一個級臺階的樓梯马靠，每級臺階上都有若干個石子奄抽，其中第i個石子(i≥1)兩位玩家輪流操作，每次操作可以從任意一級臺階上拿若干個石子放到下一級臺階中（不能不拿）甩鳄。已經(jīng)拿到地面上的石子不能再拿逞度，最后無法進(jìn)行操作的人視為失敗。問如果兩人都采用最優(yōu)策略妙啃，先手是否必勝档泽。
這個題有一個小的變形
- 勝負(fù)與偶數(shù)臺階無關(guān)，因?yàn)槿绻仁忠苿优紨?shù)階的石子到奇數(shù)階揖赴，那么后手一定能夠移動相同的石子到偶數(shù)階馆匿。所以先手必敗
將所有奇數(shù)階的石子異或起來，如果不為 0燥滑。那么先手必勝渐北，原因是先手一定能夠使石子，使異或?yàn)?0突倍。
0X02 sg 函數(shù)
首先我們來描述這樣一個基礎(chǔ)問題：
有 n 個石子腔稀，假設(shè) A、B 可以輪流拿 1 或 2 顆石子羽历，誰最后沒有石子拿誰就輸焊虏。問如果 A 先拿，A 是不是能夠必勝秕磷。
這里我取 n = 5 并畫出 n = 5 時的所有可能行
我們求出每個點(diǎn)的 sg 函數(shù)诵闭，一個節(jié)點(diǎn)的 sg 值是它所有子節(jié)點(diǎn)的 sg 值所不能到達(dá)的最小自然數(shù)。可能很抽象疏尿，我們舉個例子（按照上這張圖寫出每個節(jié)點(diǎn)的 sg 值）：
- 0 誰也不能到達(dá)瘟芝。所以 sg(0) = 0
- 1 能到達(dá) 0。sg(0) = 1 所以 sg(1) = 1
- 2 能到達(dá) 1 和 0褥琐。sg(0) = 0 sg(1) = 1所以 sg(2) = 2
- 3 能到達(dá) 2 和 1锌俱。sg(1) = 1 sg(2) = 2 所以 sg(3) = 0
- 4 能到達(dá) 2 和 3。sg(2) = 2 sg(3) = 0 所以 sg(4) = 1
- 5 能到達(dá) 4 和 3敌呈。sg(3) = 0 sg(4) = 1 所以 sg(5) = 2
下面給出這道題的結(jié)論贸宏，只要是 那么此節(jié)點(diǎn)一定是必敗態(tài)。
這里可以用反證法證明：
如果 那么 i 這個節(jié)點(diǎn)一定能轉(zhuǎn)移到 sg 等于 0 上的節(jié)點(diǎn)磕洪。而 sg 等于 0 的點(diǎn)要么可以轉(zhuǎn)移到不為 0 的點(diǎn)（后手還是可以轉(zhuǎn)移到另外一個 sg 不等于 0 的點(diǎn)上去）吭练，要么就是最后輸了的狀態(tài)。
sg 函數(shù)的一些簡單拓展問題
- 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")
