BZOJ4347 [POI2016]Nim z utrudnieniem
BZOJ分析后手必胜当且仅当每堆石子个数异或和为 $0$。设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorname{h...
标签 博弈论 下的文章
- 首页
- 博弈论
AGC010F Tree Game
AtCoderLuogu分析考虑 $u$ 是必胜点的条件是什么。显然，应该存在一个相连的节点 $v$ ，满足 $a_v<a_u$ 且 $v$ 是必败点。这样子的话，先后手就会在 $(u,v)$ 上反复横跳，然后后手就输了。正确性应该比较显然...？代码// =================================== // author: M_sea // websi...
UVA12163 Addition-Subtraction Game
UVaLuoguVjudge分析SG 函数好题。我们把一个石头当做一个游戏，那么终态就是在一个没有出边的点上。考虑如何计算 SG 函数。注意到有些点可能会重复选，而选 $2$ 次对 SG 函数不会有影响（ $a\oplus a=0$ ），于是只需要枚举 $2^{deg}$ 种状态，算出 SG 函数然后取 $\operatorname{mex}$ 即可。注意这里选的点数和选的次数的奇偶性要相同...
UVA12293 Box Game
UVaLuoguVjudge分析设 $SG(i,j)$ 表示一堆是 $i$ ，另一堆是 $j$ 的 SG 函数值。打个表看下有没有规律：0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 9 19 2 20 10 21 5 22 11 23 1 24 12 25 6 26 13 27...
CF98E Help Shrek and Donkey
CodeforcesLuogu分析博弈论好题。首先可以发现，不到最后是不会选择猜的。假设你问了一张牌，对手没有，那么对手就会怀疑这张牌是桌上那张。考虑这样一种神奇的操作：询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的，然后如果他问了他就输了。我们把这种操作称为欺骗。考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时，先手的获胜概率。我们列一个表格...
Codeforces Global Round 1 题解
之前好像写过一篇，结果被我误删了...所以重新补一下。比赛地址Parity简单分类讨论。如果$b$是奇数显然此时$b^{k-i}$全部为奇数。于是$a_i\cdot b^{k-i}$是奇数当且仅当$a_i$是奇数。于是统计$a$中奇数的个数$s$。如果$s$为奇数，则整个式子为奇数；否则整个式子为偶数。如果$b$是偶数显然仅有$b^0$为奇数，其它的$b_i(0)$都为偶数。于是整个式子的奇...
CF1110G Tree-Tac-Toe
CodeForcesLuogu分析不会做.jpg以下所有图片均来自官方题解。首先初始就为白色的点不太好搞，考虑怎么样把它当成无色点。假设 $A$ 是一个白色点，我们在它上面挂 $3$ 个新点：可以发现这样子对游戏胜负没有影响。可以这么考虑：如果白方把 $A$ 涂白了，那么黑方只能把 $B$ 涂黑。所以这就相当于多用一轮回到了给定的状态。现在是一个没有颜色的树，考虑这上面的胜负情况。显然黑色不...
AGC010E Rearranging
AtCoderLuogu分析好神啊...先考虑如果先手已经给出了序列，后手怎么做才能让字典序最大。容易发现，两个不互质的数的相对位置一定不会改变。对于每个数，向后面的与它不互质的数连边，然后在做一遍字典序最大的拓扑排序即可。考虑先手怎么做。我们把不互质的数间连双向边，那么先手的任务就相当于给每条边定向。手玩一下发现，先手从每个连通块中最小的点出发给所有边定向即可。正确性证明不会，感性理解一下...
洛谷4363 [九省联考2018]一双木棋
LuoguBZOJ分析显然，合法的状态数不会太多。于是可以状压一下轮廓线 （其实就是记录一下每行填到了哪一列） ，然后写一发对抗搜索。然后如果用 $\mathrm{map}$ 记状态的话可能会T，于是用 $\mathrm{unordered\_map}$ 就行了。具体实现及细节见代码。代码//It is made by M_sea #include <unordered_map>...
洛谷3185 [HNOI2007]分裂游戏
LuoguBZOJ分析很神仙的一道博弈论题。首先发现必败态一定是所有的豆子都装在最后一个瓶子里。然后，每次的转移一定是拿出一颗豆子，放入两颗豆子。于是我们可以把每颗豆子看做一个单独的游戏了。继续观察发现，如果有两个在同一个瓶子里的豆子，那么可以直接忽略掉这两个，因为后手可以模仿先手。于是所有位置的豆子等价于$\text{这个位置上的豆子数}\%2$。现在问题成功简化为，有一颗在$i$位置的豆...