D - Chocolate（博弈论）
12分钟过题。签到。
K - Subdivision（图论、搜索）
1小时21分过题，签到。如果给定的是一棵树的话，新增的点一定位于连接叶子节点的那条边上、否则就是已有的点。然而这是一张图，所以我们可以使用 \(\tt bfs\) 将其近似的转化为一棵树：当某个点（非其父节点）被第二次遍历到的时候，其就相当于叶子节点，当前点到这个点的边就是我们需要增加节点的边。
别忘了统计对已有的点是否满足条件。
J - Roulette（概率、暴力）
3小时228分过题，签到，这道题卡这么久确实没想到。首先从这个数据范围看必然不能是直接暴力递推，于是考虑寻找关系。容易发现，无论何时赢得比赛，手里的钱均加且只加 \(1\) ，而手里的钱的数量直接决定了你能输掉多少盘，于是，考虑对手里的钱的数量进行整数分块。
举例说明，当手里的钱为 \(3,4,5,6\) 时，至多允许输掉一盘，于是组成的概率为 $[1]: $ 直接赢 \(\dfrac{1}{2}\) 、$[2]: $ 输一盘后赢 \(\dfrac{1}{2}^2\) ，随后手里的钱 \(+1\) ；当手里的钱为 \(7,8,\dots,14\) 时，至多允许输掉两盘，于是组成的概率为 $[1]: $ 直接赢 \(\dfrac{1}{2}\) 、$[2]: $ 输一盘后赢 \(\dfrac{1}{2}^2\) ，$[3]: $ 输两盘后赢 \(\dfrac{1}{2}^3\) ，随后手里的钱 \(+1\) 。
块的大小均为 \(2\) 的倍数，最终复杂度 \(\mathcal O(\log 10^9)\) 。
M - Water（数论、贪心）
题意：给定容量为 \(A\) 和 \(B\) 的两个杯子，问至少需要经过几次操作，使得一共可以喝到恰好 \(x\) 单位的水；如果喝不到，输出 \(-1\) 。
定义操作为：将杯子接满、将一个杯子中的水倒到另一个杯子里、将杯子中的水倒掉、喝掉杯子中的水。
先考虑不存在“将一个杯子中的水倒到另一个杯子里”这种情况，发现这样喝一次需要两个操作（倒入被子、喝掉），即寻找一组整数解 \(a\) 和 \(b\) 使得 \(A\cdot a+B\cdot b=x\) 且 \(2\cdot (a+b)\) 最小，这个是个典，用扩展欧几里得即可得解。
随后计算两个杯子倒来倒去的情况。
inf.
H - Matches（数据结构、贪心）
赛时队友说是二维数点。
inf.
标签：17,cdot,dfrac,手里,签到,华中科技大学,过题,节点,杯子 From： https://www.cnblogs.com/WIDA/p/17561663.html