ABC328

__vector__ · 2023-11-14 23:57:25 · 个人记录

ABCDE 都是一眼题，不写了。

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

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

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

F

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

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

• 建立一个新的包含 $a_i,b_i$ 两个点的连通分量，并规定 $a_i = 0,b_i =-d_i$。
• 将尚未在图中的点加入已经在图中的点所在的连通分量，并计算出新加入的这个点的点权。
• 此前由于 $a_i,b_i$ 权值已经确定，现在只需要判定原来权值是否满足新的条件即可。

G

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

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

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

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

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

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