专栏文章

题解：AT_arc204_c [ARC204C] Maximize Sum of Mex

ddark_moon
AT_arc204_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio2rs8t
此快照首次捕获于
2025/12/02 12:25
3 个月前
此快照最后确认于
2025/12/02 12:25
3 个月前
查看原文
首先可以根据题目得到一堆环，我们把环分为偶数环、奇数环、单点，设偶数环的长度序列为 SevenS_{even}，奇数环的长度序列为 SoddS_{odd}，单点的数量为 KK。
思考一下，给定一堆环的时候，我们应该根据什么策略填数。不妨设刚开始所有位置的数字都是 22，我们要选择 A0A_0 个 22 变成 00，然后选择 A1A_1 个 22 变成 11。
不妨认为，一个 00 会贡献 22，也就是向左和向右两个 mexmex 函数，一个 00 和一个 11 挨着可以贡献 11，也就是让 00 的贡献多 11，这样的位置对个数设为 XX，两个 00 挨在一起可以贡献 −1-1，也就是产生了重复的贡献，如果一个单点有一个 00，也贡献 −1-1，这些位置的数量设为 YY。最终答案是 2A0+X−Y2A_0 + X - Y，也就是我们要最大化 X−YX - Y。
由于我们是优先填写 A0A_0，所以能想到计算出一个三元组 (X2,X1,Y)(X_2, X_1, Y) 表示，在某个填写 A0A_0 的方案下，有 X2X_2 个位置使得填写 11 后会让 XX 增加 22，有 X1X_1 个位置使得填写 11 后会让 XX 增加 11，此时的 YY 等于三元组里面的 YY。
考虑一个填写 00 的贪心方案：
  • 先填写在偶数环里面，并且隔着一个空格一个一个填 00。
  • 然后填写奇数环，也是隔着空格一个一个填，如果一个奇数环的长度为 lenlen，就填写 len−12\frac {len - 1} 2 个 00。先填写长度长的奇数环，再填写长度短的。
  • 如果没有剩余的奇数环可以填了，就挑选那些存在相邻的空位的奇数环，把相邻空位的其中一个填写为 00。
  • 填单点。
  • 如果还剩余的有 00，就只能随便填了。
然后就可以根据上述的方案进行分讨了。
  • 0≤A0≤∑Seven20 \le A_0 \le \frac {\sum S_{even}} 2。如果存在一个 SS 的子序列 TT，使得 A0=∑T2A_0 = \frac {\sum T} 2，那么三元组为 (A0,0,0)(A_0, 0, 0)。如果不存在，则三元组为 (A0−1,2,0)(A_0 - 1, 2, 0)。
  • ∑Seven2<A0≤∑Seven2+∑Sodd−∣Sodd∣2\frac {\sum S_{even}} 2 < A_0 \le \frac {\sum S_{even}} 2 + \frac {\sum S_{odd} - |S_{odd}|} 2。找到最小的 kk 使得 SoddS_{odd} 的前 kk 项之和减去 kk 再除以 22 大于等于 A0−∑Seven2A_0 - \frac {\sum S_{even}} 2，然后三元组为 (A0−k,2k,0)(A_0 - k, 2k, 0)。从这里也可以反过来说明，为什么填奇数环的时候要先填写长度长的了。
  • ∑Seven2+∑Sodd−∣Sodd∣2<A0≤∑Seven2+∑Sodd+∣Sodd∣2\frac {\sum S_{even}} 2 + \frac {\sum S_{odd} - |S_{odd}|} 2 < A_0 \le \frac {\sum S_{even}} 2 + \frac {\sum S_{odd} + |S_{odd}|} 2。设 s=A0−∑Seven2−∑Sodd−∣Sodd∣2s = A_0 - \frac {\sum S_{even}} 2 - \frac {\sum S_{odd} - |S_{odd}|} 2 表示要把多少个“相邻空位”填写为 00，三元组为 (A0−∣Sodd∣,2(∣Sodd∣−s),s)(A_0 - |S_{odd}|, 2(|S_{odd}| - s), s)。
  • ∑Seven2+∑Sodd+∣Sodd∣2<A≤∑Seven2+∑Sodd+∣Sodd∣2+K\frac {\sum S_{even}} 2 + \frac {\sum S_{odd} + |S_{odd}|} 2 < A \le \frac {\sum S_{even}} 2 + \frac {\sum S_{odd} + |S_{odd}|} 2 + K，每填写一个单点，YY 增加 11，所以三元组为 (∑Seven2+∑Sodd−∣Sodd∣2,0,A0−∑Seven2−∑Sodd+∣Sodd∣2)(\frac {\sum S_{even}} 2 + \frac {\sum S_{odd} - |S_{odd}|} 2, 0, A_0 - \frac {\sum S_{even}} 2 - \frac {\sum S_{odd} + |S_{odd}|} 2)。
  • ∑Seven2+∑Sodd+∣Sodd∣2+K<A\frac {\sum S_{even}} 2 + \frac {\sum S_{odd} + |S_{odd}|} 2 + K < A。此时三元组为 (N−A0,0,N−2(N−A0))(N - A_0, 0, N - 2(N - A_0))。
除了第一条，其他的三元组都可以线性预处理，至于第一条，不难发现这是一个背包问题，由于序列的元素大小之和为 O(n)O(n)，不难 O(nn)O(n \sqrt n) 计算。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...