[学习笔记]2018/2/24

  1. 1. [学习笔记]2018/2/14学习笔记
    1. 1.1. prufer编码
    2. 1.2. 博弈论
      1. 1.2.1. Nim游戏
        1. 1.2.1.1. nim游戏:n个石子,每次可以取走(1..k)颗石子 最后不能取的人输
        2. 1.2.1.2. anti-nim游戏:不能取的人赢
      2. 1.2.2. SG定理

[学习笔记]2018/2/14学习笔记

kririae

prufer编码

树hash
prufer编码,对树的编码

博弈论

“必败局面” -> 字面意思
“必胜局面” -> 走一步之后可以使对手必败局面
或到达的所有局面都是win,那么当前先手使必败

Nim游戏

nim游戏:n个石子,每次可以取走(1..k)颗石子 最后不能取的人输

anti-nim游戏:不能取的人赢

总共有n个状态,有k个转移,倒推可以知道是必胜还是必败局面。

SG定理

有两堆石子,a, b。每个人可以取任意多个。
只要个数不一样,先手必胜。
个数一样,先手必胜。
没有出现过的最小的非负整数。
你有k个博弈游戏,对于每一个博弈游戏。
同时下围棋和象棋,每次可以决定哪一局棋走一步。
推出每个游戏开始时候的SG值。
整个大号的游戏的SG值=所有子游戏的异或
SG的定义:如果最终的答案$ans = a \;xor\; b \;xor\; c$
如果$ans = 0$当前的sg不能转移到一个sg相同的。不是0就是一个必胜局面。
假设当时是必败局面$b \rightarrow d$ 考虑$b \;xor\; d$
听不懂了听不懂了.jpg