← 返回题目列表

Codeforces · 2034/B

B. 拉赫什的复兴

中文机器翻译题面 查看原题

罗斯坦的忠诚马拉赫什 (Rakhsh) 已经过上了好日子。拉赫什曾经强大而快速,但随着时间的推移,它变得越来越虚弱,甚至连移动都困难。罗斯坦担心,如果拉赫什身体的太多部位同时失去力量,拉赫什可能会完全停止运动。为了让他的同伴继续前进,罗斯坦决定一点一点地增强拉赫什的力量,这样他身体的任何部位都不会太脆弱太久。

将 Rakhsh 的身体想象成一排点,由长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 表示,其中每个 $$$0$$$ 表示一个弱点,每个 $$$1$$$ 表示一个强点。 Rostam 的目标是确保没有 $$$m$$$ 连续点的间隔是完全弱的(所有 $$$0$$$s)。

幸运的是,罗斯坦有一种叫做蒂玛的特殊能力,这是他出生时从母亲鲁达贝那里继承的。使用 Timar,他可以选择任何长度为 $$$k$$$ 的片段并立即强化所有片段(将该片段中的每个字符更改为 $$$1$$$)。挑战在于计算 Rostam 需要使用 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$$$\}$$$ for $$$1 \le i \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 Rostam 需要使用 Timar 来保持 Rakhsh 移动的最小次数,确保不存在长度为 $$$m$$$ 的连续完全弱点。

示例

输入 #1

3
5 1 1
10101
5 2 1
10101
6 3 2
000000

输出 #1

2
0
1

注意

在第一个测试用例中,我们应该对每个 0 进行操作。

在第二个测试用例中,$$$s$$$ 已经可以了。

在第三个测试用例中,我们可以对区间 $$$[3,4]$$$ 进行运算,得到 001100。