把拉赫什的身体想象成一条由长度为 n 的二进制字符串 s 表示的斑点线，其中每个 0 表示一个弱点，每个 1 表示一个强点。罗斯塔姆的目标是确保 m 个连续点中没有一个间隔是完全弱的(全部都是 0 )。 幸运的是，罗斯塔姆拥有一种名为 "提玛尔 "的特殊能力，这是他出生时从母亲 鲁达贝 那里继承来的。有了 timar，他就可以选择长度为 k 的任意语段，并立即将其全部强化(将该语段中的每个字符都变为 1 )。现在的挑战是如何计算出罗斯塔姆需要使用 timar 的最少次数，以保持 rakhsh 的移动，确保没有长度为 m 的连续完全薄弱点。 **输入** 第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )，即测试用例的数量。 每个测试用例的第一行包含三个数字 $n$ , $m$ , $k$ ( $1 \le m, k \le n \le 2 \cdot 10^5$ )。每个测试用例的第二行包含由 $n$ 个字符 $s_1s_2 \ldots s_n$ 组成的二进制字符串 $s$ 。 $s_i \in \{$ 0,1 $\}$ 为 $1 \le

首先，我们需要找到所有长度为 m 的连续子串中，包含的弱点数目最小的子串。假设该子串的弱点数目为 x。 接下来，我们需要计算 x 除以 k 的向上取整的值。我们需要将这个值乘以 k ，得到的结果就是需要使用 timar 的最少次数。 具体实现时，我们可以通过滑动窗口的方式来找到最小的弱点数目。我们维护一个变量 cnt 来记录当前滑动窗口内的弱点数目，初始化为 0。我们先将滑动窗口设置为前 m 个字符，并统计其中的弱点数目。 然后，我们循环从第 m+1 个字符开始到第 n 个字符，每次将一个字符加入滑动窗口的右端，并将滑动窗口左端的一个字符移出。我们需要根据新加入的字符是否为弱点，分别更新 cnt 的值。具体地，如果新加入的字符是弱点，则 cnt 加 1；如果移出的字符是弱点，则 cnt 减 1。 在每次更新 cnt 的过程中，我们可以将 cnt 的值与之前得到的最小弱点数目 x 比较，更新 x 的值。 当循环结束后，我们得到了 x 的值。最后，我们需要计算 x 除以 k 的向上取整的值。这可以通过 (x+k-1)/k 来计算。 对于每个测试用例，我们输出计算得到的最少次数。 算法的时间复杂度为 O(n)，其中 n 为字符串的长度。因为我们只需遍历一次字符串，并且每次更新 cnt 的操作只需要常数时间。算法的空间复杂度为 O(1)。 [2024-11-30 23:08:18 | AI写代码神器 | 700点数解答]