[Problem - E - Codeforces](https://codeforces.com/contest/2248/problem/E) 题目本身难度并不大，但是很有意思，赛时完全是阴差阳错大概猜了猜就通过了 感觉和今年 CCPC Final 的 G 题思路很像，都是通过贪心的调整对比来说明最优解的形式，只可惜当时赛时想到了但没时间调代码😭证明方法和题解有点不一样，尽量避开繁杂的数学推导 容易发现最终合法的一定是若干个极长 `1` 段被 `0` 隔开，因为如果有不低于 $2$ 个 `0` 连在一起，把其中一个改成 `1` 更优 然后尝试把当前相邻两个极长 `1` 段合并成一段，即把中间的 `0` 改成 `1` 会不会更优 如果不优，假设两段的长度为 $x$ 和 $y$，令 $S_i = F(I(i))$ 表示长度为 $x$ 的 `1` 段的价值，则此时 $S_x+S_y>S_{x+y+1}$，通过这个式子可以发现，我们只取两段 $x$ 和 $y$ 就已经合法了 如果更优，那就直接合并，如果一直合并到只有一段，就一定不合法了 这就说明如果存在解，那一定存在某个解只包含两段 并且，如果一个极长 `1` 段的长度不在 $p$ 中，我们可以直接把这一段删掉尽可能少的 `1` 变成变成某个 $p$，一定不会更不优 所以只需要枚举两个 $p$ 作为极长 `1` 段就好了 $O(m^2\log m)$ 或者 $O(m^2)$ 都可以，用二分或者双指针计算 $S$ Loading... [Problem - E - Codeforces](https://codeforces.com/contest/2248/problem/E) 题目本身难度并不大，但是很有意思，赛时完全是阴差阳错大概猜了猜就通过了 感觉和今年 CCPC Final 的 G 题思路很像，都是通过贪心的调整对比来说明最优解的形式，只可惜当时赛时想到了但没时间调代码😭证明方法和题解有点不一样，尽量避开繁杂的数学推导 容易发现最终合法的一定是若干个极长 `1` 段被 `0` 隔开，因为如果有不低于 $2$ 个 `0` 连在一起，把其中一个改成 `1` 更优 然后尝试把当前相邻两个极长 `1` 段合并成一段，即把中间的 `0` 改成 `1` 会不会更优 如果不优，假设两段的长度为 $x$ 和 $y$，令 $S_i = F(I(i))$ 表示长度为 $x$ 的 `1` 段的价值，则此时 $S_x+S_y>S_{x+y+1}$，通过这个式子可以发现，我们只取两段 $x$ 和 $y$ 就已经合法了 如果更优，那就直接合并，如果一直合并到只有一段，就一定不合法了 这就说明如果存在解，那一定存在某个解只包含两段 并且，如果一个极长 `1` 段的长度不在 $p$ 中，我们可以直接把这一段删掉尽可能少的 `1` 变成变成某个 $p$，一定不会更不优 所以只需要枚举两个 $p$ 作为极长 `1` 段就好了 $O(m^2\log m)$ 或者 $O(m^2)$ 都可以，用二分或者双指针计算 $S$ 最后修改：2026 年 08 月 03 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏