← 返回题目列表

Codeforces · 1367/C

C. 社交距离

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

波利卡普和他的朋友想要参观一家新餐厅。餐厅的桌子沿直线排列。人们已经坐在一些桌子旁。这些表按照从左到右的顺序从 $$$1$$$ 到 $$$n$$$ 进行编号。餐厅的状态由长度为 $$$n$$$ 的字符串描述,其中包含字符“1”(桌子被占用)和“0”(桌子为空)。

餐厅规则禁止人们坐在 $$$k$$$ 或以下的距离。也就是说,如果一个人坐在第 $$$i$$$ 号桌,那么所有编号从 $$$i-k$$$ 到 $$$i+k$$$ 的桌子(第 $$$i$$$-th 除外)都应该是免费的。也就是说,任意两个占用表的数量的绝对差必须严格大于$$$k$$$。

例如,如果 $$$n=8$$$ 且 $$$k=2$$$,则:

- 字符串“10010001”、“10000010”、“00000000”、“00100000”满足餐厅的规则;
- 字符串“10100100”、“10011001”、“11111111”不满足餐厅的规则,因为它们每个都有一对距离小于或等于$$$k=2$$$的“1”。

具体地,如果餐厅的状态是由不带“1”的字符串或带有一个“1”的字符串来描述的,则满足餐厅的要求。

给您一个二进制字符串 $$$s$$$ 来描述餐厅的当前状态。保证字符串 $$$s$$$ 满足餐厅的规则。

找出您可以占用的最大空闲餐桌数量,以免违反餐厅规则。从形式上来说,最多可以用“1”替换多少个“0”才能仍然满足要求?

例如,如果 $$$n=6$$$、$$$k=1$$$、$$$s=$$$ "100010",则问题的答案将为 $$$1$$$,因为只有位置 $$$3$$$ 的表可以被占用,从而仍然满足规则。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以包含两个整数 $$$n$$$ 和 $$$k$$$ 的行开头 ($$$1 \le k \le n \le 2\cdot 10^5$$$) - 餐厅的桌子数量和两个人之间允许的最小距离。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,由“0”和“1”组成 - 餐厅中空闲和占用餐桌的描述。给定的字符串满足餐厅的规则 - 任何两个“1”的索引之间的差异大于 $$$k$$$。

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

输出

对于每个测试用例,输出一个整数——您可以占用的桌子数量,以免违反餐厅的规则。如果无法获取额外的表,那么显然您需要输出$$$0$$$。

示例

输入 #1

6
6 1
100010
6 2
000000
5 1
10101
3 1
001
2 2
00
1 1
0

输出 #1

1
2
0
1
1
1

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,答案是 $$$2$$$,因为您可以选择第一个和第六个表。

在第三个测试用例中,如果不违反餐厅规则,则不能占用任何免费餐桌。