简单图上博弈博弈树其实就是记录你每一步决策的状态。比如5 个石子Alice 和 Bob 轮流取每次取 1 到 2 颗取到最后一颗的入人胜Alice 先手问她的必胜决策。5 Start | \ 4 3 Alice | \ \ \ 3 2- 2- 1 Bob | \ \ \ \ \ \ 2 1 1 0 1 0 0 Alice |\ \ \ \ 1 0 0 0 0 Bob | 0 A其中旁边的字母代表现在轮到了谁数字表示当前还剩几颗这就差不多是博弈树。然后求答案就从出边为 0 的开始计算有点类似 Topo 排序。题目P4096P7135这里我认为第二道题不那么像模板题第一道题就是模板题因此我讲第二道P7135这是我做的第一道交互题只不过它也不是很难。如果你发现的仔细的话你就可以填出一个幻方这里不展示包含这几个数字每一行、每一列、每一条对角线都是 15因此我们发现这不就是井字棋吗于是直接建出博弈树就做完了。如果你玩过井字棋的的话你也可以直接写程序暴力和交互库下棋。code不好意思的是我是直接和他下棋并没有建博弈树。提示先手下角网上有说为什么后手堵桥就把交互库第一步下的位置直接提前每个出一套对策直接干。有向图博弈这玩意很好做博弈方式直接建出树只不过有可能有两个父节点同时拥有同一个子节点继父只不过这问题也不大父母离异问题还不大孩子心理会有问题。划掉的部分是我同学说的但我想回一句你是不知道红黑树是吧孙子的孙子秒变爷爷的爷爷这是数据结构和家谱没有问题。但是DAG只存在于有向无环图有环怎么办啥孙子结婚生了爷爷见过基环树吗也有环没关系我们可以发现只要这种情况出现了肯定平局不然跳出这个环外的人就输了题目CF786AP6560P9169都是模板题没必要讲。公平组合游戏Nim 游戏博弈论部分由于以思维为主很少作为一个知识点用来考察。但以nim 游戏为代表的公平组合游戏是一个很容易考场的知识点。公平博弈impartial game指满足如下条件的组合博弈在任意确定状态下所有参与者可选择的行动完全相同仅取决于当前状态与身份无关博弈中的同一个状态不可能多次抵达博弈以参与者无法行动为结束且博弈一定会在有限步后以非平局结束。nim 游戏有堆石子第堆石子有颗石头先后手轮流操作每次可以选择一堆石子然后从中选大于 0 个石头扔掉。谁在操作后场上所有石头清空谁获胜。所有的公平组合游戏都可以转化 为nim 游戏。我们直接给出结论一个状态为先手必败当且仅当所有石子的异或和为 0。证明是这样的不妨把上述状态称为必败。显然当时这就是一个必败态。现在对于任意一个非必败态可以证明一定存在一种操作方案使得一次操作之后转化为必败态且对于一个必败态操作一次必然成为一个非必败态因此证明完毕。于是我们可以线性复杂度判断一局 nim 游戏的状态了。这个理论可以把所有的公平组合游戏转化为nim 游戏。首先公平组合游戏有很多不同的“局”比如nim 游戏中就有局游戏每一局游戏都是一堆石子虽然单堆石子很简单但是它也可以看做一张有向无环图博弈连边为必败点。而所有的“局”都是一张有向无环图。我们定义图上一个点的函数值为所有它可以到达的点的值的 mex。且必败态的值为 0。把所有游戏起点的异或起来不为 0 则为必胜态。knim 游戏与 nim 游戏的区别在于每次可以至多拿堆石子。阶梯nim每次可以在一堆里面选出大于 0 个石子然后放到下一堆特殊的对于第一堆选出来的石子会直接扔掉。树上nim选出来的石子放到父节点上根上的直接扔掉。树上博弈给你若干个有根森林每次删掉一颗子树根不能删谁不能操作谁输。题目听懂了就会做因为都是模板题P2148P2575P6639P13114此处不讲题如果实在要我讲我会另出一篇文章讲要讲在评论区说。后记反正你在考场上遇到这类题要不是思维题要不是模板题都不是就想想其他做法吧。如果你想再做点这类题的话可以尝试做这道题。这道题和 P7135 一样也是比较有意思的题目可以好好想一想也提升了能力你水了一道黑题巨佬爆切黑题巨~~~膜拜~~~。对了你们想不想看 DEVC 的神秘用法想看在评论区里说。