洛谷5363 [SDOI2019]移动金币
Luogu LOJ 分析 一次移动后会让左边的空位减少若干，右边的空位增加若干，从而可以转化为一个阶梯博弈。 不妨把左右反过来，那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。 再转化问题，相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中，使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。 这个不为 $0$ 不好处理，可以容斥一下，变成算为 $0$ 的。那...
标签 博弈论 下的文章
- 首页
- 博弈论
洛谷6665 [清华集训2016] Alice 和 Bob 又在玩游戏
Luogu UOJ 分析 考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。 于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。 如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。 如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG ...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
BZOJ4347 [POI2016]Nim z utrudnieniem
BZOJ 分析 后手必胜当且仅当每堆石子个数异或和为 $0$。 设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。 考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorna...
CF98E Help Shrek and Donkey
Codeforces 分析 首先可以发现，不到最后是不会选择猜的。 假设你问了一张牌，对手没有，那么对手就会怀疑这张牌是桌上那张。 考虑这样一种神奇的操作：询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的，然后如果他问了他就输了。我们把这种操作称为欺骗。 考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时，先手的获胜概率。 我们列一个表格，表示在先...
CF1110G Tree-Tac-Toe
CodeForces 分析 以下所有图片均来自官方题解。 首先初始就为白色的点不太好搞，考虑怎么样把它当成无色点。 假设 $A$ 是一个白色点，我们在它上面挂 $3$ 个新点： 可以发现这样子对游戏胜负没有影响。 可以这么考虑：如果白方把 $A$ 涂白了，那么黑方只能把 $B$ 涂黑。所以这就相当于多用一轮回到了给定的状态。 现在是一个没有颜色的树，考虑这上面的胜负情况。 显然黑色不可...
洛谷3235 [HNOI2014]江南乐
Luogu 分析 首先发现这是个 Multi-SG 游戏，那么可以考虑使用 SG 函数。 先考虑怎么暴力求 $SG(x)$ 。 大力枚举分成的堆数。如果将 $x$ 分成了 $i$ 堆，那么这 $i$ 堆中有 $x\bmod i$ 堆 $\left\lceil\frac{x}{i}\right\rceil$，有 $i-x\bmod i$ 堆 $\left\lfloor\frac{x}{i}\r...