省流
被 C 题气晕，又提前好久下班，\(3t\) 表现分 \(1649\) 掉大分。
10.21
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
看到这场比赛之前爆零了，引起了一些不好的回忆。同时决定看看不和咖啡早上爬起来战斗力如何。
赛时
A 题要求每三个相连的数之间 \(\mathrm{mex}(a, b, c) = \max(a, b, c) - \min(a, b, c)\)。因为只有三个数，所以 \(\mathrm{mex}\) 只有 \(0,1,2\) 三种可能。当 \(mex\) 为 \(0\) 时这三个数为相等的不为零的数，\(\mathrm{mex}\) 不为零的情况不存在。所以判断整个序列是否都相等且不为零即可。\(6min\) 通过。
B 题给了一行格子，有些格子内有墙，有些没有墙，有一个点在某个初始位置。两个人轮流移动，第一个人在一个空地上建一个墙，第二个人操控点向左侧或右侧移动到最近的墙处并摧毁这个墙，如果没有墙则结束。第一个人希望尽量晚结束，第二个人希望尽量早，问会进行几轮。
发现如果确定往某个方向走，要走的轮数就是这个方向第一个墙距离边界的距离，而且第二个人永远只朝一个方向走。所以后面的步数都确定，为较少的一侧。那么考虑第一个人第一步放到左侧和右侧哪个，肯定优先放到步数较少的一侧的点边上，然后把更新后的两侧比较哪个步数少即可。
因为没有在找到最近的点后退出找点的循环挂了一发，在 \(20min\) 以一发罚时通过。
C 题给了两个长度为 \(n \leq 1e5\) 的序列，要求两个人轮流操作 \(k\) 次。第一个人选择两个下标，第二个人任意交换这两个序列中对应下标四个数的位置。第一个人想要两个序列对应下标上的值之差的绝对值之和最小，第二个人想要这个数最大。问最后这个值是多少。
首先容易想到第二个人的交换操作只会让这个数变大，所以第一个人永远只会选择相同的一些下标以让第二个人对整体答案影响最小，所以相当于只会进行一轮。
那么考虑交换的四个数对答案的影响。显然我们不关心上下两个序列的差别，所以可以无妨设 \(a_i \geq b_i\)。对于选择 \(i\) 和 \(j\)，原来的贡献是 \(a_i - b_i + a_j - b_j\)，更新后应该是较大的两个减去较小的两个，不考虑当前就是最好状态，那么显然是将较大的 \(b\) 换上来，也就是 \(a_{big} + b_{big} - a_{small} - b_{small}\)。将两式相减可得：
考虑固定 \(a_{small}\)，那么我们只要考虑在当前 \(a\) 较小时能取到的最大 \(b_{big}\)，将两个序列按照 \(a\) 从大到小排序并处理前缀最大 \(b\) 即可 \(O(1)\) 得到一个 \(a_{small}\) 的最大修改贡献。第一个人只要选择最大修改贡献最小的即可。
我一开始忘记排序吃了一发罚时，修改后 \(62min\) 通过，感觉远比 \(1376\) 的评分难。
D 题给了 \(n \leq 2e5\) 个点，\(m\) 条边，保证图联通，要求把点排到两侧，要求相连的点必须在不同的两侧，且点之间的连线不重叠，问有多少种排列。
容易想到只有树可以把整个图分成两侧，于是先判断是否是树，然后试着任意建一棵树，相同子树层内的点任意排序，结果发现根节点不同的结果不同。于是考虑进行拓扑排序，把最后的点作为树的起点，然后做 dp。但是精力涣散了，这场比赛就这样灰溜溜的结束了。
赛后
先看了一下前面的题目的题解，结果发现题解的做法感觉比我推式子还要难以理解和复杂，不知道为什么大家都这么轻松的做出来了。
接着我们继续看 D，还是先考虑他是一棵树，那么对于一个点，画出和它相连的点，发现只有两侧的点可以有除了它以外的点相连，而中间的点如果再和其他节点相连必然与初始点和两侧点的边相交。所以这棵树必须是一颗毛毛虫树，即除了一条主要路径外，别的点都是叶子节点附着在主要路径上，像毛毛虫和它的腿（究竟哪个神人想的毛毛虫树，这个名字仅优于珂朵莉树）。那么对于这个毛毛虫树的可能，只需要先找到它的主干，主干肯定是确定的，两边反过来放的情况只需要对一边的情况乘二。那么一边的情况就同样有两种，分别是毛毛虫的头尾交换一下，所以总答案是一个毛毛虫乘四。考虑一个毛毛虫的答案数，其实就是每一段腿任意排序即可，最后全部乘起来就行了。
需要注意的是毛毛虫的主干如果只有一个点，那么头尾无法交换，答案是一个毛毛虫乘二。
2025年10月21日