• 搬题人
  • 电塔：Wu_Ren
  • 并查集：p_b_p_b, Lynkcat
  • 划分序列：Crysfly
• 组题人
  • p_b_p_b
• 题解：部分题解可以见验题人题解。

电塔

来源：

• Petrozavodsk Winter 2020 Day 5: Jagiellonian U Contest, Problem C
• https://qoj.ac/contest/445/problem/1177

首先把 $x_i$ 从小到大排序，不妨假设 $x_i$ 相对大小关系不变，那么只需满足 $x^\prime_{i+1}-x^\prime_i\ge d$。

设 $y_i=x_i-id$，那么只需保证最终 $y_{i+1}\ge y_i$。同时，在这个过程中我们需要保证 $y_i\ge -id$。

由于我们需要保证 $y_i\ge y_1\ge -d$，所以我们先把比 $-d$ 小的 $y_i$ 先提升到 $-d$，然后就不需要考虑下界的限制了。

那么接下来就是有一个数组，每次给某个数加减一，使得最终单调不降，求最小操作数。

考虑设 $f_{i,j}$ 为 $y^\prime_i\le j$ 且前 $i$ 个数已经单调不降的最小花费，$g_{i,j}$ 为 $y^\prime_i=j$ 且前 $i$ 个数已经单调不降的最小花费，那么有 $g_{i,j}=f_{i-1,j}+|y_i-j|$，容易发现我们的 $j$ 只需要取在 $\{y_i\}$ 里出现过的即可，复杂度 $O(n^2)$。

然后发现假如 $(j,g_{i-1,j})$ 这些点是下凸的，$f\leftarrow g$ 相当于前缀最小值，所以 $(j,f_{i-1,j})$ 这些点也是下凸的，然后 $(j,|y_i-j|)$ 也是下凸的，所以 $(j,g_{i,j})$ 也是下凸的。

同时 $(j,f_{i,j})$ 是呈现分段线性函数的样式，具体的，存在 $0=a_0\le a_1\le a_2\le \dots\le a_i$，使得 $f(x)=f_{i,x}$ 在 $[a_j,a_{j+1}]$ 上斜率为 $j-i$，且 $\forall x\ge a_i,f(x)=f(a_i)$。我们尝试用堆维护 $a_1,a_2,\dots,a_i$ 以及 $w=f_{i,a_i}$。那么从 $f_{i-1}$ 转移到 $f_{i}$ 时，假如 $y_i \ge a_{i-1}$，那么直接令 $a_i=y_i$ 即可；假如 $y_i < a_{i-1}$，那么令 $w:=w+a_{i-1}-y_i$，并设置 $a_{i-1}:=y_i,a_i=y_i$ 即可。

复杂度 $O(n\log n)$。

并查集

来源：

• Toyota Programming Contest 2023 Spring Final, Problem G
• https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota2023spring_final_g

考虑每条边对答案的贡献。合并 $A_i,B_i$ 时，如果令 $A_i$ 为 $B_i$ 的父亲，则这条边被走的次数是 $B_i$ 当前连通块向外连的边数。

因此只要确定了边的顺序，那么一定是让度数小的连通块成为度数大的连通块的父亲。

进一步可以发现，如果 $B_i$ 的连通块度数非零，那么把加边的顺序修改为先合并 $B_i$ 的连通块，再连接 $(A_i,B_i)$ ，再按照原顺序合并 $A_i$ 的连通块，一定不劣。

因此不难证明，最优加边顺序一定满足加入的边在任意时刻都是连通的。即存在一个根，每次加边是把儿子和父亲合并，且父亲此时一定已经与根连通。

感性理解一下，最优加边顺序里，儿子的度数应该不会比上面一整个连通块的度数要大。事实上，如若不然，把儿子选为根一定更优。

于是加入一个儿子就是给答案加上总度数，然后给总度数加上儿子的度数减一。

最后只需要把加入儿子的顺序定下来，满足父亲比儿子早加入。这是一个经典的贪心题，可以用并查集加优先队列实现。

复杂度 $O(n^2\log n)$ 。

划分序列

来源：

• Petrozavodsk Summer 2019. Day 9. MEX Foundation Contest, Problem J
• https://qoj.ac/contest/1392/problem/7605

咕了，见验题人题解。