Nim游戏入门+SG函数

09
七月
2021

 对于经典的Nim游戏,只需要把每一堆初始状态都异或起来,最后得到的结果非0的为必胜状态,结果为0的为必败状态。

 

原理:异或的结果非0的状态总能通过一次取物品操作,将此状态转化为结果为0的状态;而异或结果为0的状态如果不是最终状态(所有堆都是0)经过一次取物品操作,总会变为异或结果非0的状态。

 例:891. Nim游戏 - AcWing题库

SG函数

 

SG函数的自变量为有向图游戏中能达到的一种状态,因变量为一个数。

定义某个状态的SG值为其不能到达的SG值的最小值,举个栗子:

 对于单个的有向图游戏,初始条件的SG值非0时为必胜状态,否则为必败状态。对于每个非0的状态一定能直接到达0状态。

对于多个同时进行的有向图游戏,就可以看成Nim游戏,把所有初始条件异或起来得到结果。

例:893. 集合-Nim游戏 - AcWing题库

 

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员