官方题解（中文整理）

基于 Benjamin Qi 的官方题解整理。

先把位置按模 \(K\) 分组

我们先考虑如何求最小值；最大值的做法与之对称。

由题意可知：

\(r_i \equiv b_i + b_{i+1} + \dots + b_{i+K-1} \pmod 2\)

把相邻两个窗口的式子相减，就能得到：

\(b_{i+K} \equiv r_i + r_{i+1} + b_i \pmod 2\)

因此一旦知道某个 \(b_i\)，就能唯一推出 \(b_{i+K}, b_{i+2K}, \dots\)。这说明整个串会分成 \(K\) 条互不影响的链：

• \(b_1, b_{1+K}, b_{1+2K}, \dots\)
• \(b_2, b_{2+K}, b_{2+2K}, \dots\)
• ...
• \(b_K, b_{2K}, b_{3K}, \dots\)

对于每一条链，只需要考虑它的起点取 \(0\) 或 \(1\) 两种情况，就能得到整条链的两个候选方案。

每条链独立求最优

对某条链，设：

• 起点取 \(0\) 时，这条链中 1 的个数为 \(s_0\)
• 起点取 \(1\) 时，这条链中 1 的个数为 \(s_1\)

那么为了让全局 1 的总数尽量小，我们显然会先在这条链上取 \(\min(s_0,s_1)\)。

把所有链的这个最小值加起来，就得到一个“候选最小值”。但这里还差一步：这样独立选出来的起点奇偶性，未必满足第一个窗口对应的约束 \(r_1\)。

如何修正第一个窗口的奇偶性

第一个窗口正好覆盖 \(b_1, b_2, \dots, b_K\)，所以它只与每条链的第一个元素有关。

在前面的贪心选择下，我们可以顺便维护：

• 当前已选方案中，\(b_1 \dots b_K\) 里 1 的奇偶性
• 每条链把方案从较优方案切换到另一种方案时，总代价会增加多少

设最小的这个增量为 \(d\)。

如果当前奇偶性已经满足 \(r_1\)，那么候选值就是最终最小值。

否则，我们至少要翻转一条链的选法来改变奇偶性。显然应选择代价增加最小的那一条，于是最终最小值就是：

\(\text{candidate} + d\)

最大值怎么做

求最大值完全类似。你可以把每条链里 1 的数量取较大者，再用同样的奇偶性修正思路处理。

或者也可以利用“0/1 互补”的关系，按官方代码中的写法直接由最小值推出最大值。

复杂度

每个位置只会被遍历常数次，所以每组测试的时间复杂度为 \(O(N)\)。