本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-14 23:57:25

ABCDE 都是一眼题，不写了。

F 题思维比较简单，赛时 并查集 写挂被罚了两发。

G 题有点思维难度，但也就是个状压板子。

因为 whk 赛时只做了 F 就跑路了。

F

将 $a_i,b_i$ 建边，形成的图，对于每个连通分量只需要规定任意一点为 $0$，其他点权值便可推算出来，并判断出矛盾。

看起来不那么容易整体计算答案，那么考虑加边带来的影响。

• $a_i,b_i$ 均未加入图中
  建立一个新的包含 $a_i,b_i$ 两个点的连通分量，并规定 $a_i = 0,b_i =-d_i$。
• $a_i,b_i$ 有一个已经在图中的
  将尚未在图中的点加入已经在图中的点所在的连通分量，并计算出新加入的这个点的点权。
• $a_i,b_i$ 都已经在图中，且 $a_i$ 和 $b_i$ 处于相同连通分量
  此前由于 $a_i,b_i$ 权值已经确定，现在只需要判定原来权值是否满足新的条件即可。
• $a_i,b_i$ 都已经在图中，且 $a_i$ 和 $b_i$ 不处于相同连通分量 此时应合并两个连通分量，这样，要么是 $a_i$ 所在连通分量的所有数加上一个特定值，要么是 $b_i$ 所在连通分量的所有数加上一个特定值（是什么能根据 $a_i,b_i,d_i$ 推算出来），此时启发式合并。

G

显然操作 $1$ 只会执行最多 $1$ 次。

问题转化成将序列 $a$ 分割成若干个区间，将这些区间重新排列后前后连接形成新的序列 $c$，使得 $\sum\limits_{i=1}^{n} |b_i-c_i|$ 最小化。

我的思路是依次加入区间，并算答案。

所以状态：$dp_s$ 表示已经加入集合的点集为 $s$ 的情况下的最小答案。

转移的话，枚举新加入的区间。

看上去复杂度是 $O(2^n \cdot n^2)$ 的，但实际根本跑不满，通过本题绰绰有余。