CF1658 题解. 神奇的结论.

给定长度为 的 01 串 . 对于一个 01 串 , 记 为 中 的数量, 其中 . 给定 , 求总长度为 的若干 的不相交子序列 , 满足 , 且 最小. 输出最小的 和一组方案.

把串首尾相接形成环. 考察环上所有的长度为 的区间中的 1 数量总和, 必为 . 这之后考察每个这样的区间中的 的个数, 不妨记 为从 开始的环上长度为 的区间中 的数量, 有 . 考察将 画成图像, 那么每一段的斜率都是 , 或 . 又 个 之总和 满足 , 所以必然存在一点 满足 (也可以说由中值定理可以得到). 也即答案是环上的一个区间.

容易把环再次拆成串, 留给读者作练习.