洛谷5363 [SDOI2019]移动金币
LuoguLOJ分析一次移动后会让左边的空位减少若干，右边的空位增加若干，从而可以转化为一个阶梯博弈。不妨把左右反过来，那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。再转化问题，相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中，使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。这个不为 $0$ 不好处理，可以容斥一下，变成算为 $0$ 的。那么就是每一位...
标签 博弈论 下的文章
- 首页
- 博弈论
洛谷6665 [清华集训2016] Alice 和 Bob 又在玩游戏
LuoguUOJ分析考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG 函数值的异或...
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$。这里...