比赛链接

组装

Solution 1

本题是二次函数（我还没学qwq），但是容易知道最小值 $x = \frac{\sum_{i=1}^nx_i}{n}$，

如果直接计算，需要枚举每个零件的生产车间，指数级。

考虑贪心，有 $x_{i,j} + x_{i,j+1}$ 为关键字排序，这可以用反证法证明，

然后我们可以通过差值进行生产车间的替换。

虽然我们有很多状态没有枚举，但是贪心维护了所有可能的答案。

Solution 2

当然，还有一种方法是模拟退火（相当玄学，我就第一次提交对了），

只要对每一种颜色开一个vector，存一下所有这个颜色的位置，判定的时候可以去所有颜色里二分找到$x$的前驱后继，把和当前点距离小的加入答案。

交换

Solution 1

如果我们倒叙考虑的话，等于第 $i$ 个位置可以跟第 $2i$ 个位置和第 $2i+1$ 个位置交换，

$dfs$ 找它能取到的最小值（这个结点的两个儿子/
这个结点到根结点的路径上的所有点以及这些点的左儿子（如果这些左儿子原来不在序列里的话））

因此我们剩下来的任务就是判断对于一个结点来说，哪些点是可以取的，哪些是不能取的。

我们把一个结点分成三类：

1. 取值不来自于它的后代
2. 取值来自于它的左儿子
3. 取值来自于它的右儿子

我们发现，对于第一类结点，它上面的点（包括它自己，下同）是不会换到它的下面的，它的左儿子也不可能到它的右子树上；对于第二类结点，它上面的点只有一个可以换到它的左子树上，并且它的左儿子也不会到右子树上。对于第三类结点，它上面的点只有一个可以到它的左子树或者右子树上（相对应的，它的左儿子可以到另一边去）。

因此，我们只需要在每一个点上维护一些信息，就可以实现前面说的功能。具体来说，我们需要记录每一个点是第几类点（如果这个点还没有选就是 $0$），然后对于第二类点和第三类点记录它们是否被用过，对于第三类点还需要记录它将左儿子放到了左边还是右边。每一次选择完后维护这些信息也是 $O(logN)$ 的。

Tests

由于 $s$ 并没有简单的方式处理，观察满足单调性，所以用二分，

贪心思路是尽量选满$X$，除此之外只有一个余数。

贪吃蛇

简单博弈论，用双端队列可优化至 $O(n)$。