笔记参考:emofunc-牛客博弈论课程课件 博弈的基本概念 组合游戏 两个玩家 一个状态集合 游戏规则是指明玩家在一个状态下可以移动到哪些其它状态 玩家轮流进行移动 如果当前处于某个状态,玩家根据规则无法移动,则游戏结束 (大部分时候)无论玩家如何选择,游戏会在有限步以内结束 组合游戏是非常常见的博弈模型 经典模型 Bash 游戏:一堆石子,轮流…
题意 题目链接 树上的棋子博弈,每个点有权值。你可以添加一条边以试图反败为胜,不同的加边方法根据权值有一个代价,需要最小化这个代价。 解析 我们首先定义一个结点先手必败是 lose,先手必胜是 win,容易发现,叶子结点一定是 lose,然后对于每一个非叶子结点,只要它有一个儿子是 lose,它就是 win,否则,该结点也是 lose。一遍 d…