AGC010F Tree Game
AtCoderLuogu分析考虑一个菊花、一开始在中心的情况。显然先手只会往一个 $a_i$ 小的方向走才能胜利，因为双方会在这条边上反复横跳，然后后手先跳完。考虑加上一层。假设一开始在 $u$，$v$ 子树先手必胜，则先手一定不会往 $v$ 走；假设一开始在 $u$，$v$ 子树先手必败，则先手可以往 $v$ 走，且后手一定回到 $u$，故当 $a_u<a_v$ 时先手胜利。因此只需...
标签 博弈论 下的文章
- 首页
- 博弈论
AtCoder Grand Contest 005 简要题解
比赛地址STring和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下：若 $d$ 为奇数，则应有 考虑计算 $f_i$。容易发现一...
AtCoder Grand Contest 002 简要题解
比赛地址Range Product简单讨论一下即可。代码Box and Ball简单模拟一下即可。注意盒子里仅有一个球的情况。代码Knot Puzzle能全部解开当且仅当存在两条相邻的绳子满足长度之和 $\geq L$。正确性显然。代码Stamp Rally先考虑怎么算从 $x,y$ 出发最多能到达的点数。显然，如果 $x,y$ 连通，则为 $sz_x$，否则为 $sz_x+sz_y$。这里...
BZOJ4347 [POI2016]Nim z utrudnieniem
BZOJ分析后手必胜当且仅当每堆石子个数异或和为 $0$。设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorname{h...
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分析好神啊...先考虑如果先手已经给出了序列，后手怎么做才能让字典序最大。容易发现，两个不互质的数的相对位置一定不会改变。对于每个数，向后面的与它不互质的数连边，然后在做一遍字典序最大的拓扑排序即可。考虑先手怎么做。我们把不互质的数间连双向边，那么先手的任务就相当于给每条边定向。手玩一下发现，先手从每个连通块中最小的点出发给所有边定向即可。正确性证明不会，感性理解一下...