题解：AT_arc204_c [ARC204C] Maximize Sum of Mex

dark_moon · 2025-08-29 11:35:15 · 题解

首先可以根据题目得到一堆环，我们把环分为偶数环、奇数环、单点，设偶数环的长度序列为 S_{even}，奇数环的长度序列为 S_{odd}，单点的数量为 K。

思考一下，给定一堆环的时候，我们应该根据什么策略填数。不妨设刚开始所有位置的数字都是 2，我们要选择 A_0 个 2 变成 0，然后选择 A_1 个 2 变成 1。

不妨认为，一个 0 会贡献 2，也就是向左和向右两个 mex 函数，一个 0 和一个 1 挨着可以贡献 1，也就是让 0 的贡献多 1，这样的位置对个数设为 X，两个 0 挨在一起可以贡献 -1，也就是产生了重复的贡献，如果一个单点有一个 0，也贡献 -1，这些位置的数量设为 Y。最终答案是 2A_0 + X - Y，也就是我们要最大化 X - Y。

由于我们是优先填写 A_0，所以能想到计算出一个三元组 (X_2, X_1, Y) 表示，在某个填写 A_0 的方案下，有 X_2 个位置使得填写 1 后会让 X 增加 2，有 X_1 个位置使得填写 1 后会让 X 增加 1，此时的 Y 等于三元组里面的 Y。

考虑一个填写 0 的贪心方案：

• 先填写在偶数环里面，并且隔着一个空格一个一个填 0。
• 然后填写奇数环，也是隔着空格一个一个填，如果一个奇数环的长度为 len，就填写 \frac {len - 1} 2 个 0。先填写长度长的奇数环，再填写长度短的。
• 如果没有剩余的奇数环可以填了，就挑选那些存在相邻的空位的奇数环，把相邻空位的其中一个填写为 0。
• 填单点。
• 如果还剩余的有 0，就只能随便填了。

然后就可以根据上述的方案进行分讨了。

除了第一条，其他的三元组都可以线性预处理，至于第一条，不难发现这是一个背包问题，由于序列的元素大小之和为 O(n)，不难 O(n \sqrt n) 计算。