AtCoder Regular Contest 078 简要题解
比赛地址Splitting Pile枚举即可。代码Fennec VS. Snuke双方显然是先把对方到自己这边来的路堵上。于是我们只要找到分界点，看看哪边的点多即可。需要注意的是，如果两边的点一样多，那么是后手胜。代码Awkward Response首先可以把 $N$ 的位数确定出来：依次问 $1,10,100,\cdots$ 直到回答是 N，则前一个数和 $N$ 的位数相同。那么可以考虑二...
标签 博弈论 下的文章
- 首页
- 博弈论
AtCoder Regular Contest 072 简要题解
比赛地址Sequence枚举第一个是正的还是负的，那么后面的符号都确定了。那么如果有一个前缀和不满足的话直接改成 -1 或 1 即可。可以证明这是最优的。代码Alice&Brown如果 $(n,m)$ 是先手必胜的，则存在一个 $(n-2x,m+x)$ 或一个 $(n+x,m-2x)$ 是先手必败的。于是手动打一个表可以发现 $(n,m)$ 必败当且仅当 $\lvert n-m\rvert ...
AtCoder Regular Contest 064 简要题解
比赛地址Boxes and Candies从左往右扫一遍，尽量先拿走靠右的即可。正确性显然。代码An Ordinary Game这个 D 怎么比 E 难啊设 $s$ 为原串，$n$ 为串长。给出结论：当 $s_1=s_n$ 时，如果 $n$ 为奇数则后手必胜，否则先手必胜；当 $s_1\neq s_n$ 时，如果 $n$ 为奇数则先手必胜，否则后手必胜。先证明 $s_1=s_n$ 时的情况。...
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)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...
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...