CF1353E K-periodic Garland

你有一个由 $n$ 个灯泡组成的花环。灯泡的状态由长度为 $n$ 的字符串 $s$ 表示。字符串 $s$ 的第 $i$ 个字符 $s_i$ 等于 '0' 表示第 $i$ 个灯泡是关闭的，等于 '1' 表示第 $i$ 个灯泡是开启的。你还得到一个正整数 $k$。 每次操作，你可以选择一个灯泡并改变它的状态（即如果它是关闭的就打开，如果是打开的就关闭）。 如果每对相邻的开启灯泡之间的距离恰好为 $k$，则称这个花环是 $k$-周期的。考虑 $k=3$ 的情况。则花环 "00010010"、"1001001"、"00010" 和 "0" 是好的，但 "00101001"、"1000001" 和 "01001100" 不是。注意花环不是循环的，即第一个开启的灯泡不会接在最后一个开启的灯泡之后，反之亦然。 你的任务是计算，为了将给定的花环变为 $k$-周期的花环，最少需要多少次操作。 你需要回答 $t$ 个独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 25000$），表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^6; 1 \le k \le n$），分别表示字符串 $s$ 的长度和所需的周期。第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 '0' 和 '1' 组成。 保证所有测试用例中 $n$ 的总和不超过 $10^6$（$\sum n \le 10^6$）。

对于每个测试用例，输出一个整数，表示将给定花环变为 $k$-周期花环所需的最少操作次数。

由 ChatGPT 4.1 翻译