2023.12.03

压线圈到了 MXOI 的奖学金。

最近 whk 太忙了，还得准备月考，没太多时间整理很多东西，但是这个还是得整理一下。

感觉这场比赛还是挺赚的，见识了一下 lxl 最近的命题思路，只能说物超所值了。

A.avatar

先二分，转判断问题。然后发现转成 wll 就是所有 \(|x_i-x_j|<v(t_i-t_j)\) 的连边。想贪，好像是错的，但是能过大样例。

考虑拆掉绝对值，发现两个式子都是在绝对值的另一个条件下更容易满足，所以直接变成 \(x_i-vt_i>x_j-vt_j\) 且 \(x_i+vt_i<x_j+vt_j\)，转二维偏序，再转最长反链问题即可。复杂度 \(O(n\log n\log V)\)。

B.rec

按照部分分入手。只有 \(()\) 好做，直接转成 nim 游戏。那么再考虑只有 \((())\) 和 \(()\) 的情况。

考虑到 \((())\) 可以变成任意多个 \(()()\dotsc ()\)，且打表发现 \(()\) 和 \((())\) 可以分开作为 \(2\) 个单独的 nim 游戏处理，我们考虑证明这个结论。

用 \((a,b)\) 代表当前 \(()\) 的异或和为 \(a\)，\((())\) 的异或和为 \(b\) 的胜者。我们证明只有当 \((0,0)\) 时后手获胜。

考虑归纳法，已知最后直接使后手获胜的局面是 \((0,0)\)。若当前 \(b\neq 0\)，我们选择一个可以使 \(b=0\) 的串，并且把 \((())\) 删到 \(b=0\)。此时我们可以任意修改 \(()\) 的数量，把 \(()\) 的数量修改到恰好使 \(a=0\) 即可。若 \(b=0,a\neq 0\)，则选择一个可以使 \(a=0\) 的串删 \(()\) 即可。而 \((0,0)\) 则一定会使下一次的 \((a,b)\neq (0,0)\)。

然后就好做了，任意多种串时就是把 \((a,b)\) 改成 \((a_1,a_2,\dotsc,a_x)\)。后手获胜条件还是 \(\forall a_i= 0\)。

C.array

lxl 的老本行，但是说实话这题看到题解之后还是有点 disappointing，感觉没有想象的那么 nb，更多是对基本功的考察。

离线，维护时间轴，转成区间取 min，历史版本和问题，用 segment-beat+历史问题 解决。