Meow ===== A ===== toby: 设给定 01 序列的长度为 n，1 的个数为 k。我的思路是进行如下几步：
  1. 将给定字符串所有 0 位置排序（冒泡）: 消耗次数 $\frac{(n-k)(n-k-1)}{2}$
  2. 剔除最后一个 0 的位置，将其他位置排序（把 1 的位置插入排序）: 消耗次数 $k(n-k-1)$
  3. 将末尾 k 位排序（把上一位锁定的 0 插入排序）: 消耗次数 $(k-1)$
合计次数最多 119 次。 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： 线段树写错了（我是笨蛋） ===== J ===== red: 简单期望题，推两下得到式子，交给 toby 但他不愿意写，然后就自己写一发过了 Dirty: 这怎么会有 dirty 呢（x) ===== K ===== red: 图论题，构建出最短路的生成树后最大化延长所有非树边，然后对叶节点特殊讨论即可。 Dirty: 太弱智了。边数开少了 t 了两次，距离 1 未特判 wa 了两次。 ===== M ===== red: 开局看到感觉可做，发现是解不定方程后发现忘了怎么解，于是交给 yuki 了。 yuki: exgcd解方程，再凑一凑答案。 Dirty： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋） ====== 场上没过的题 ====== ===== L ===== red: 发现置换 3k 次是个环，剩下就只需要解同余方程组。因为模数不一定互质，所以不能直接用中国剩余定理。想到可以对模数分解后再用，但 toby 已经硬解出来了，然后就基本正确了。 场上没过的原因似乎是 exgcd 过程爆 ll 了，改成 int128 就对了，太气人了。