2020多校2竞赛题解：并查集与区间和优化

本资源主要关注于两道编程题目，分别来自2020年多校联合训练竞赛中的"Total Eclipse"和"Blood Pressure Game"。以下是详细的解析： 1. Total Eclipse: 这是一道关于图论的题目，主要目标是在一个带权重的图中，通过连续减小连通块内所有节点的数值，直到某个节点变为0并将其移除，重复此过程直到所有连通块都达到最小值。核心策略是反向思考，从最大权重的节点开始，每次加入新节点时，检查与其相连的节点，若新节点x与已加入的y不连通且y在x之前加入，则合并它们，更新树根关系。每个节点x被合并的次数为bfatherx，因此其对答案的贡献为bx−bfatherx。利用并查集数据结构支持路径压缩，整个过程的时间复杂度为O((n+m)logn)，其中n是节点数，m是边数。 2. Blood Pressure Game: 这道题目涉及数组操作和动态规划。给定一组数字ai，要求找出使得绝对差值之和最小的排列方式。首先，将数组排序得到b1, b2, ..., bn，绝对差值转化为区间和，即|ai−aj|等于排序后的相邻元素差值的和。问题转换为计算每个相邻区间(bi−bi−1)对最终结果的贡献。通过动态规划，定义f[i][j][t]表示前i个数形成j个连通块，其中有t个数作为a1或an的前k大，目标是求解f[n][1][2]。转移状态考虑四种情况：新建连通块、作为a1/an的连通块、合并连通块和扩展连通块。具体转移规则根据题目描述计算对应区间贡献，并调整方案数。 这两道题目均考察了选手的算法设计和优化能力，特别是图论和动态规划在实际问题中的应用，需要对数据结构和算法有深入理解才能高效解决。解决这类问题的关键在于分析题意，合理构建数据结构，以及巧妙地运用动态规划或者回溯的方法来求解。