Alice和Bob最近又在寻找一些好玩的游戏,直到有一天他们发现了一颗有根树,树的根节点为 111,树上每个点有333种类型,分别对应 1,2,31,2,31,2,3,类型 1,21 ,21,2分别表示向上跳111格,跳 222格,类型 333表示向上跳 111格或 222格,Alice提议她随便选一个叶子节点开始向上跳,谁先不能跳谁就输,Bob觉得非常的不公平,所以他试图破坏这个树,来获得胜利,Alice,Bob想要知道破坏第 iii条边后谁能获得胜利,两人都按照最优策略进行游戏。
Alice和Bob最近又在寻找一些好玩的游戏,直到有一天他们发现了一颗有根树。 树的根节点为 111 ,树上每个点有 333 种类型,分别对应 1,2,31,2,31,2,3 。 类型 1,21 ,21,2 分别表示向上跳 111 格,跳 222 格。类型 333 表示向上跳 111 格或 222 格。 Alice提议她随便选一个叶子节点(不包括根节点)开始向上跳,谁先不能跳谁就输。 Bob觉得非常的不公平,所以他试图破坏这个树,来获得胜利。 Bob能破坏有根树的一条边,从而使得跳跃无法越过该边。 Alice,Bob想要知道破坏第 iii 条边后谁能获得胜利,两人都按照最优策略进行游戏。 注:此处破坏第 iii 条边并不会改变树的形态,并且每次破坏操作独立。
(图片来源网络,侵删)