题目理解

我们有一个长度为 $n$ 的二进制字符串 $s$ 和一个参数 $k$。游戏规则是：

1. 我们选择一些位置进行保护。
2. Teto 从左到右扫描每个位置 $i$，如果满足以下三个条件，她可以将 $s_i$ 从 $1$ 改为 $0$：
   • $s_i = 1$
   • 该位置没有被保护
   • 前面 $k-1$ 个位置（即 $i-k+1$ 到 $i-1$）中没有 $1$

目标：选择最少的位置进行保护，使得 Teto 无法改变任何字符（即所有 $1$ 都保持不变）。

关键观察

1. 保护第一个 $1$ 是必要的
   如果字符串的第一个 $1$ 没有被保护，且它前面没有 $1$（因为它是第一个），那么 Teto 就可以将它改为 $0$。
   所以，第一个 $1$ 必须被保护。

2. 保护某些 $1$ 可以阻止后续的 $1$ 被改变
   规则中说：如果前面 $k-1$ 个位置中存在 $1$，则当前 $1$ 不能被 Teto 改变。
   因此，如果我们确保每个 $1$ 的前面 $k-1$ 个位置内至少有一个被保护的 $1$，那么它就不会被 Teto 改变。

3. 只需要保护部分 $1$，而不是所有 $1$
   我们可以让某些 $1$ 承担“保护”后续 $1$ 的任务：
   如果一个被保护的 $1$ 后面 $k-1$ 个位置内出现了另一个 $1$，那么这个 $1$ 不需要被保护，因为它前面有被保护的 $1$。

4. 转化问题
   我们只需要保护一些 $1$，使得：

   • 第一个 $1$ 被保护；
   • 任意两个被保护的 $1$ 之间的距离小于 $k$（因为如果距离 $\ge k$，中间会出现一个 $1$ 前面没有被保护的 $1$，它会被 Teto 改变）。

贪心策略

设所有 $1$ 的位置为 $p_1, p_2, \dots, p_m$（下标从 $0$ 开始，表示在字符串中的索引）。

• 第一个 $1$ 必须被保护，即 $p_0$ 被保护。
• 从 $p_0$ 开始往后看：如果 $p_1 - p_0 \ge k$，说明 $p_1$ 的前面 $k-1$ 个位置内没有被保护的 $1$，那么 $p_1$ 必须被保护。
• 依此类推：我们维护最后一个被保护的 $1$ 的位置 $\text{last}$，遍历所有 $1$，如果当前 $1$ 的位置 $i$ 满足 $i - \text{last} \ge k$，则保护它（答案加 $1$），并更新 $\text{last} = i$。

算法步骤

1. 初始化 $\text{last} = -\infty$（或者一个足够小的数，如 $-10^9$）。
2. 遍历字符串 $s$ 的所有位置 $i$：
   • 如果 $s[i] = 1$ 且 $i - \text{last} \ge k$，则 $\text{ans} \leftarrow \text{ans} + 1$，并更新 $\text{last} = i$。
3. 输出 $\text{ans}$。

示例验证

示例 1：$n=2, k=2, s=11$

• $i=0$，$s[0]=1$，$0 - (-\infty) \ge 2$ 成立，$\text{ans}=1$，$\text{last}=0$。
• $i=1$，$s[1]=1$，$1 - 0 = 1 < 2$，不成立，不保护。
• 输出 $1$，正确。

示例 4：$n=7, k=2, s=1010101$

$1$ 的位置：$0, 2, 4, 6$

• $p_0$ 被保护，$\text{last}=0$
• $p_1=2$，$2-0=2 \ge 2$，保护，$\text{ans}=2$，$\text{last}=2$
• $p_2=4$，$4-2=2 \ge 2$，保护，$\text{ans}=3$，$\text{last}=4$
• $p_3=6$，$6-4=2 \ge 2$，保护，$\text{ans}=4$，$\text{last}=6$
  输出 $4$，正确。

示例 9：$n=8, k=3, s=00000000$

没有 $1$，循环不执行任何保护，$\text{ans}=0$，正确。

时间复杂度

• 遍历一次字符串，$O(n)$。
• 总 $n$ 不超过 $1000$，完全可行。

正确性证明（归纳法）

归纳假设：按上述贪心策略保护的 $1$ 的集合，能够使得所有 $1$ 在游戏过程中保持不变。

• 基础：第一个 $1$ 被保护，不会被改变。
• 归纳步：假设某个被保护的 $1$ 在位置 $p$ 之前的所有 $1$ 都保持不变。
  对于下一个 $1$ 在位置 $q$：
  • 如果 $q - p < k$，那么 $q$ 的前面 $k-1$ 个位置中包含被保护的 $p$，所以 Teto 无法改变 $q$。
  • 如果 $q - p \ge k$，则 $p$ 的“保护范围”无法覆盖 $q$，因此 $q$ 必须被保护，否则它前面 $k-1$ 个位置没有 $1$，Teto 可以改变它。

由于我们正是这样决定保护的，所以所有 $1$ 最终都会处于被保护或被覆盖的状态，字符串保持不变。同时，这种策略显然是最优的，因为我们只在必要时才增加保护。

总结

本题的核心是将问题转化为：在 $1$ 的位置序列中，如果相邻 $1$ 的距离 $\ge k$，则必须保护后一个 $1$。
贪心地从左到右扫描即可得到最少保护数。