OI里面考的一般是完全信息博弈,也就是谁都知道问题的全部信息.
sg函数
必输状态的sg值为0.
其他状态的sg值为mex(所有可到达的子状态).
上面是一个独立游戏的sg函数值,对于多个独立游戏(比如多个石堆彼此取石子是独立的),sg函数为xor(所有子游戏的sg)
nim游戏
每次可以从一堆石子拿走任意个数,不能不拿,谁拿不了就输.
结论:所有石子xor为0必输,其余情况必赢.
证明:假设当前xor不为0,前手必定能构造一个方案满足拿走之后剩余的xor为0,然后效仿后手拿即可.
反nim游戏
典题
- 小质数棋盘硬币游戏
首先硬币的两维是独立的,考虑分开.
打表出硬币的sg序列为0,0,1,1,2,2,3,3,4,硬币的sg可以用维度mex起来.
所有的独立硬币xor起来.