icontofig | 发布于 2019-08-29 22:27:27 | 阅读量 416 | 博弈论 记忆化搜索
发布于 2019-08-29 22:27:27 | 博弈论 记忆化搜索
DescriptionIn a world where ordinary people cannot reach, a boy named "Koutarou" and a girl named "Sena" are playing a video game. The game system of this video game is quite unique: in the process of playing this game, you need to constantly face the choice, each time you choose the game will provi
继续阅读
icontofig | 发布于 2019-08-13 00:35:49 | 阅读量 427 | 博弈论 贪心 思维题
发布于 2019-08-13 00:35:49 | 博弈论 贪心 思维题
2019 Multi-University Training Contest 7 1010 Just Repeat
题目大意先手有n张牌,后手有m张牌,如果某人打出了某种颜色的牌,那么另一个人就不能打这种颜色的牌,最后不能出牌的人输。求问是先手胜还是后手胜。 题解两人都是按最优策略取的博弈,不过和SG函数并没有什么关系。 两个人肯定每回合都是贪心的取对自己最有利的方案。 首先我们将两人都有的颜色的牌抽出来,剩下的就是两人各自独立的牌集,不会受对方出牌的影响。 然后我们考虑被抽出来的牌,怎样取能使得局面变得对自己有利。 如果对于某种颜色,两人共有的这种颜色的牌比较大,那么当前的出牌者选择出这种颜色的牌的优先级肯定就更高。 然后当前的人出一种颜色的牌,就可以看成是把自己原有的这种颜色的牌全部收回,把对方原有的这
继续阅读
icontofig | 发布于 2019-07-30 12:14:20 | 阅读量 273 | 莫队 博弈论 NIM博弈
发布于 2019-07-30 12:14:20 | 莫队 博弈论 NIM博弈
2019 Multi-University Training Contest 3 Game 经典NIM博弈SG函数 + 带修改莫队
题目大意先手选出区间L-R的连续的石子堆,后手可以交换第pos 和 pos+1堆石子,然后再从L-R选出区间l-r的石子两人进行取石子博弈。 问在L-R中有多少种后手取l-r的方案能够使得先手必胜。 题解这题是一个经典的NIM博弈。我们需要用SG函数来解决。 我们考虑前缀SG函数异或和,区间L-R内有多少选择l-r的方案使得先手必胜这一点我们可以转化为有都少方案使得先手必败(SG函数异或和为0) l-r的SG函数异或和为0,即前缀异或和ssg满足ssg[r] = ssg[l-1],问题转化为统计区间中有多少ssg相等的点对数。 然后我们使用区间点对总数减去区间中ssg相等的点对数就是当前询问的
继续阅读
icontofig | 发布于 2017-01-27 08:58:23 | 阅读量 640 | 博弈论
发布于 2017-01-27 08:58:23 | 博弈论
博弈论相关(组合游戏) 基本条件 游戏由两方参与且双方均知道对方策略(三国杀1v1就不是博弈游戏,因为双方并不知道对方手牌)且均采取最优策略。 特点 1.有很多歌独立的子游戏。 2.每次操作可以选取某个子游戏进行 3.所有的子游戏结束,全局游戏便结束 例1:取石子 有n堆石子,双方进行博弈游戏,每次可以从某一堆中取出任意多的石子(不大于这堆石子数)每堆中有Ai" role="presentation" style="position: relative;">AiAiA_i个石子 我们设先手必败态为0,先手必胜态为1,那么这个必胜态和必败态
继续阅读