SG 定理用来解决有向图游戏:在有向图上一次走一步,不能继续走的玩家获胜。定义 SG 函数为
则先手获胜当且仅当所有起点 的 SG 函数的异或和非 ,即
这里实际上是说,如果有两个独立的有向图,并且每个玩家每次都可以随意选择一张图上走一步,那么整张图的 SG 函数值等于这两个子图的函数值的异或。
TIPS
这类题目应当积极打表,很可能发现规律。
SG 定理用来解决有向图游戏:在有向图上一次走一步,不能继续走的玩家获胜。定义 SG 函数为
则先手获胜当且仅当所有起点 的 SG 函数的异或和非 ,即
这里实际上是说,如果有两个独立的有向图,并且每个玩家每次都可以随意选择一张图上走一步,那么整张图的 SG 函数值等于这两个子图的函数值的异或。
TIPS
这类题目应当积极打表,很可能发现规律。