标签 博弈论 下的文章
- 首页
- 博弈论
CF98E Help Shrek and Donkey
CodeforcesLuogu分析博弈论好题。首先可以发现，不到最后是不会选择猜的。假设你问了一张牌，对手没有，那么对手就会怀疑这张牌是桌上那张。考虑这样一种神奇的操作：询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的，然后如果他问了他就输了。我们把这种操作称为欺骗。考虑 DP 。设 ...
Codeforces Global Round 1 题解
之前好像写过一篇，结果被我误删了...所以重新补一下。比赛地址Parity简单分类讨论。如果$b$是奇数显然此时$b^{k-i}$全部为奇数。于是$a_i\cdot b^{k-i}$是奇数当且仅当$a_i$是奇数。于是统计$a$中奇数的个数$s$。如果$s$为奇数，则整个式子为奇数；否则整个式...
CF1110G Tree-Tac-Toe
CodeForcesLuogu分析不会做.jpg以下所有图片均来自官方题解。首先初始就为白色的点不太好搞，考虑怎么样把它当成无色点。假设 $A$ 是一个白色点，我们在它上面挂 $3$ 个新点：可以发现这样子对游戏胜负没有影响。可以这么考虑：如果白方把 $A$ 涂白了，那么黑方只能把 $B$ 涂...
洛谷4363 [九省联考2018]一双木棋
LuoguBZOJ分析显然，合法的状态数不会太多。于是可以状压一下轮廓线 （其实就是记录一下每行填到了哪一列） ，然后写一发对抗搜索。然后如果用 $\mathrm{map}$ 记状态的话可能会T，于是用 $\mathrm{unordered\_map}$ 就行了。具体实现及细节见代码。代码//...
洛谷3185 [HNOI2007]分裂游戏
LuoguBZOJ分析很神仙的一道博弈论题。首先发现必败态一定是所有的豆子都装在最后一个瓶子里。然后，每次的转移一定是拿出一颗豆子，放入两颗豆子。于是我们可以把每颗豆子看做一个单独的游戏了。继续观察发现，如果有两个在同一个瓶子里的豆子，那么可以直接忽略掉这两个，因为后手可以模仿先手。于是所有位...
洛谷3235 [HNOI2014]江南乐
LuoguBZOJ分析0首先发现这是个$\mathrm{Multi-SG}$游戏，然后发现可以用 $SG$ 函数来做。显然的，对于任意的$x<F$，$SG(x)=0$。1先考虑怎么暴力求 $SG(x)$ 。大力枚举分成的堆数。如果将 $x$ 分成了$i$ 堆，那么这 $i$ 堆中有 $x...
洛谷2148 [SDOI2009]E&D
LuoguBZOJ分析打表后发现 $SG(i)=i-1\text{的二进制表示}$。于是每一对数 $(i,j)$ 的 $SG$ 值就是 $\mathrm{mex}(i-1,j-1)$ 。然后每一对数的 $SG$ 值都异或起来就行了。代码//It is made by M_sea #includ...
洛谷4279 [SHOI2008]小约翰的游戏
LuoguBZOJ分析显然这是一个$\mathrm{Anti-SG}$游戏。关于$\mathrm{Anti-SG}$游戏然后，没有了呀qwq代码//It is made by M_sea #include <algorithm> #include <iostream> ...