CF1367C Social Distance

Polycarp 和他的朋友们想去一家新餐厅。餐厅里有 $n$ 张桌子，沿直线排列。有些桌子上已经有人坐了。桌子的编号从 $1$ 到 $n$，从左到右依次排列。餐厅的状态用一个长度为 $n$ 的字符串描述，字符串由字符 "1"（该桌有人）和 "0"（该桌为空）组成。 餐厅规定，任何两个人之间的距离必须大于 $k$。也就是说，如果某人在第 $i$ 张桌子上坐下，那么编号从 $i-k$ 到 $i+k$（除了 $i$ 本身）的所有桌子都必须是空的。换句话说，任意两张被占用的桌子的编号之差的绝对值必须严格大于 $k$。 例如，如果 $n=8$，$k=2$，那么： - 字符串 "10010001"、"10000010"、"00000000"、"00100000" 满足餐厅的规定； - 字符串 "10100100"、"10011001"、"11111111" 不满足餐厅的规定，因为它们中存在一对 "1"，其距离小于或等于 $k=2$。 特别地，如果餐厅状态描述的字符串中没有 "1" 或只有一个 "1"，那么餐厅的规定一定被满足。 现在给定一个二进制字符串 $s$，描述了餐厅当前的状态。保证字符串 $s$ 满足餐厅的规定。 请你计算，在不违反餐厅规定的前提下，最多还能有多少张空桌可以被占用？换句话说，最多可以将多少个 "0" 替换成 "1"，使得规定依然被满足？ 例如，如果 $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" 组成，描述了餐厅中空桌和已占用桌子的情况。保证给定的字符串 $s$ 满足餐厅的规定——任意两个 "1" 的下标之差都大于 $k$。 所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，输出一个整数，表示在不违反餐厅规定的前提下，最多还能占用多少张桌子。如果不能再占用任何桌子，则输出 $0$。

第一个测试用例的解释见题面。 第二个测试用例，答案为 $2$，因为你可以选择第 $1$ 张和第 $6$ 张桌子。 第三个测试用例，无法再占用任何空桌，否则会违反餐厅规定。 由 ChatGPT 4.1 翻译