題意：

給定長為 n 的 0, 1 字符串，你可以通過一次操作改變一個字符（0 變 1 or 1 變 0），問最少幾次操作可以使任意相鄰兩個 1 之間的距離為 k ?

題目：

You are given a garland consisting of n lamps. States of the lamps are represented by the string s of length n. The i-th character of the string si equals ‘0’ if the i-th lamp is turned off or ‘1’ if the i-th lamp is turned on. You are also given a positive integer k.

In one move, you can choose one lamp and change its state (i.e. turn it on if it is turned off and vice versa).

The garland is called k-periodic if the distance between each pair of adjacent turned on lamps is exactly k. Consider the case k=3. Then garlands “00010010”, “1001001”, “00010” and “0” are good but garlands “00101001”, “1000001” and “01001100” are not. Note that the garland is not cyclic, i.e. the first turned on lamp is not going after the last turned on lamp and vice versa.

Your task is to find the minimum number of moves you need to make to obtain k-periodic garland from the given one.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤25 000) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and k (1≤n≤106;1≤k≤n) — the length of s and the required period. The second line of the test case contains the string s consisting of n characters ‘0’ and ‘1’.

It is guaranteed that the sum of n over all test cases does not exceed 106 (∑n≤106).

Output

For each test case, print the answer — the minimum number of moves you need to make to obtain k-periodic garland from the given one.

Example

Input

6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0

Output

1
2
5
4
0
0

Solution:#

顯然根據題意可以得知最終所有 1 的位置 mod k 的余數 t 都相同。那么我們就可以去枚舉 t，判斷在這種情況下，需要幾次操作，最后取 min 即可。
??首先我們要知道的是我們最多改變多少次：原字符串 1 的個數 ?1 次。
??我們先算出原字符串 1 的個數 cnt。然后假設原字符串的 1 對應 1，0 對應 ?1，那么我們將對應位即：t, t+k, t+2?k, … 的字符提取出來，按照對應方式組成一個新序列，那么求出該序列的最大連續子段和 cur,那么 min(cnt?cur) 就是答案。
??我們知道只有 t, t+k, … 這些位才有可能為 1，那么我們求出的 cur 無非就兩種情況：
??1. a, b, c （a, c是一連串的 ?1; b 是一連串的 1）;
??2. a, b, c （a,c 是一連串的 1; b 是一連串的 ?1）（a+b+c>max(a,c)）。
??對于 1. 來說，cur 個 1 是不需要改變的，那么在其他的位置多出來 cnt?cur 個 1，所以需要 cnt?cur 次來把他們變為 0。
??對于 2. 來說，有 a+c 個 1 是不需要改變的，我們需要把中間的 b 個 0 變為 1，還需要把 cnt?a?c 個其他位置的 1 變為 0。即 b+cnt?a?c=cnt?cur(cur=a+c+b)。
??求出最大子段和其實就是最多不需要改變的個數（新序列）。

AC代碼：

/**題目大意 給你一個01串，要你用最少的變化次數使得所有的1相鄰的距離為k。 變化的方式為1->0,0->1.要你求最少的變化次數 題目思路 emm完全沒啥思路，看了題解，其實就是你要想這些數字1都 是modk等于一個定值，那么你就可以用余數開始枚舉。 首先肯定時要統計所有1的個數 sum 然后把 ai 中的字符 1 看成數字 1，字符 0 看成數字 ?1， 問題就變成了求 ai 中最大連續子序列和 （now）sum-now即為最優解。 有些難解釋，但是自己仔細思考應該就明白了。遇到此類題目就是要 枚舉余數*/ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e6+5; char s[maxn]; int t,n,k,sum,now,ma; int main() {scanf("%d",&t);while(t--){sum=0,ma=0;scanf("%d %d %s",&n,&k,s);for(int i=0; i<=n-1; i++){if(s[i]=='1')sum++;}for(int i=0; i<=k-1; i++){now=0;for(int j=i; j<=n-1; j=j+k) //1->1 0->-1{int x=2*(s[j]-'0')-1;now+=x;if(now<0)now=0;ma=max(ma,now);//最大連續的值}}printf("%d\n",sum-ma);}return 0; }

總結

以上是生活随笔為你收集整理的K-periodic Garland CodeForces - 1353E（暴力+贪心+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。