2022 CCPC 绵阳站
A. Ban or Pick, What’s the Trick
倒着DP，设进行了 $i$ 轮，$A$ 还剩 $j$ 个可以选，$B$ 还有 $k$ 个可以选。
记忆化即可。时间复杂度 $O(nk^2)$。
C. Catch You Catch Me
答案即为根节点所有子树的深度之和。
D. Gambler’s Ruin
首先要将 $p_i$ 相同的进行合并。
强制要求 $s_x\times x \geq s_y\times y$。第二种情况考虑将 $p_i$ 变为 $1-p_i$ 再进行处理。
按照 $p_i$ 从小到大排序，那么枚举一个 $p_i$，表示比 $p_i$ 高的都归为 $s_x$，那么 $x$ 越小越好， $x = \frac{1}{p_i}$。
接下来找到 $y$ 所在位置 $j$，需要满足 $\frac{s_y(j)}{1-p_j}\le s_x\times x$。随着 $j$ 增加，$s_y(j),\frac{1}{1-p_j}$ 单调增，于是可以二分。
二分过程可能会因为精度出问题，于是我用了__int128。
可能还需要注意一下 $x,y=0,1$ 之类的情况。
时间复杂度 $O(n\log n)$。
E. Hammer to Fall
将询问倒过来，每次对于点 $u$ 找到与其直接相连的，点权+边权最小的点，并将点 $u$ 的权值设置为这个权值。
然后正过来模拟即可。
那么每 $B$ 个分一个块，每隔 $B$ 次重构每个点直接相连的最小权值。
对于每一块，可能会使得 $B$ 个点的点权改变。
那么根号重构时，直接不考虑这 $B$ 个点，然后每次查询时暴力看看这 $B$ 个点是否在里面即可。
时间是根号的。
G. Let Them Eat Cake
每次操作会使得序列长度至少减半。
暴力即可。
H. Life is Hard and Undecidable, but…
构造一个长度为 $2k$ 的对角线即可。
J. Middle Race
假的交互题。
只要离平均数最接近，那么就一定是OK的。
枚举 $A$ 选了多少次，$O(1)$ 算出最优的 $B,C$ 次数即可。
L. Por Una Cabeza
对于一个机器，只有最晚的那个点决定这个点是什么，其他的位置恰好一半。
那么将这个最晚的点直接移到这个机器上，这样就变成了互相没有关系的。
对于 $2n$ 个点，我们可以直接贪心，将大于一半的那个部分选出最小的几个就可以了。
赛场上写了个 Treap 去做。
293min 的时候一发过了，很爽。
M. Rock-Paper-Scissors Pyramid
将赢的人向输的人连边，表示赢的人比输的人的势能高 $1$。
答案即为势能最高的人。
原因是：
- 连续相同的可以变成一个。
- 一次操作，谷底（势能最低）的人将消失。