Meow
A
toby:
设给定 01 序列的长度为 n，1 的个数为 k。我的思路是进行如下几步：
- 将给定字符串所有 0 位置排序（冒泡）: 消耗次数 $\frac{(n-k)(n-k-1)}{2}$
- 剔除最后一个 0 的位置，将其他位置排序（把 1 的位置插入排序）: 消耗次数 $k(n-k-1)$
- 将末尾 k 位排序（把上一位锁定的 0 插入排序）: 消耗次数 $(k-1)$
Dirty: 没考虑到最后一个位置可能不是 0，直接锁了最后一位。改了之后又太慌，忘记改第三步的排序了。（我是笨蛋）
D
toby:
这是一个经典的数学问题（许多书上有提到）。当然不知道结论也可以猜。下面给出一个证明：
首先可以发现 (n, m) 格肯定是最后拿到的，拿到的人就输了。
当 n==1 && m==1 时，由于只有一个拿取的方案，所以先手必败。
其他情况，假设先手必败，则先手取 (1, 1)，后手必有必胜方案，不妨设为取 (a, b)，那么先手只需要在第一手取 (a, b) 就可以得到一致的必胜局面，导出矛盾。故先手必胜。
Dirty: 无。考场花了 5 min 重导这个结论。
H
yuki:
考虑到如果交换了 $b_x$ 和 $b_y$（交换 $a$ 是等价的），答案将从 $|a_x - b_x| + |a_y - b_y|$ 变为 $|a_x - b_y| + |a_y - b_x|$ 那么 $a_x$ 和 $b_x$ 的大小关系和 $a_y$ 和 $b_y$ 的大小关系一定是相反的，否则交换后的结果要么不变，要么变大。因此把输入分为两类 $a \leq b$ 的和 $a > b$ 的。
假设：$a_x \geq b_x$ 那么可能交换的 $a_y < b_y$，按 $b_y$ 从小到大遍历所有的第二类元组，不断把第一类元组加入线段树，保持线段树中 $a_x \leq b_y$，再以 $a_y$ 作为分界在线段树上分别查询 $b_x < a_y$和 $b_x \geq a_y$ 两种情况的最优解。
Dirty： 线段树写错了（我是笨蛋）
M
yuki:
exgcd解方程，再凑一凑答案。
Dirty： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋）
