XTU OJ 1464 黑子的鸡脚（说人话）

2
5 2
10111
8 3
11101110

2
2

#include 
#include 
#define N 10007
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
 
char s[N];
int n, k;
int L[N], R[N], cnt;
 
void sol() {
	scanf("%d %d", &n, &k);
	int ans = 0;
	cnt = 0;//第多少个区间
	scanf("%s", s + 1);//这里有意思，因为如果直接输入%s的话，开头的下标为0，如果后面加1的话开头的下标就变为1了，这样就满足题目的编号条件
	s[0] = '0';//开头补0，不妨看题解，因为我们会尝试在一段区间开头或者结尾的0变成1来试试能不能将数量增加一个
	//因此为了保证不用特殊判断开头和中间的情况，我们直接开头补0，实际上不会影响我们的结果
	for (int i = 1; i <= n; ++i) {
		if (s[i - 1] == '0' && s[i] == '1') cnt ++, L[cnt] = N, R[cnt] = -1; //为什么这里取N和-1?，这是因为我们之后有一个min和max
		//为了保证更新的时候对两个端点也有影响，我们直接取端点的旁边的值，这样就不会对端点产生误判
				//上面的if同时保证了一个区间开头必定为1，开头前必定为0，为什么在开头前只看一个0？
				//这里其实有一种贪心的思想，比如，对于一个串 111000111111，你要获得数量最多的长度为k的连续为1的字串
				//是不是只能对最靠近1的0进行变化，才有可能使其能被提出来
		if (s[i] == '1') { // 更新块的信息
			L[cnt] = min(L[cnt], i);//储存一下区间坐标
			//左边肯定是取小的，右边肯定是取大的
			R[cnt] = max(R[cnt], i);
		}
	}
	for (int i = 1; i <= cnt; ++i) { // 对于每一块，取值。
//		printf("%d %d\n", L[i], R[i]);
		ans += (R[i] - L[i] + 1) / k;//如果说这个区间的长度为k倍数，那么数量就相应的变化;
		//我们其实不用判断能不能提出来，我们直接除以k，如果能提出来就！=0，不能提出来就=0
		//不需要单独判断了，我之前做的时候总想在这里判断一下
		//太过于麻烦
	}
	for (int i = 1; i <= cnt; ++i) { // 尝试合并
	//分为两种情况,情况一，如果说开头或者末尾为0，且后面没有连接的为1的连续字符串
		if ((R[i] - L[i] + 2) <= n && (R[i] - L[i] + 2) / k > (R[i] - L[i] + 1) / k) {
			//这段代码的意思是，如果说区间长度+1(也就是往后面或者前面延展一位：因为我们只能将一个0变为1，也就是说只能延展一位将其变为1)
			//的长度仍比长度n小(保证不会超出限制)与此同时延展一位后/k(代表分割成长度k的子串的数量)大于之前没有延展一位的子串的数量
			//代表将后一位或者
			//前一位的0变为1能够对最终答案的数量贡献1，因此就break，就不用再判断了
			//
			ans ++;
			break;
		}
		//情况2，末尾或者开头为0，但后面有连接的字符串
		if (i < cnt && R[i] + 2 == L[i + 1]) {
			int t1 = (R[i] - L[i] + 1) / k + (R[i + 1] - L[i + 1] + 1) / k;
			//将后面的字符串连接起来，看下能分出多少个长度为k的子区间
			int t2 = (R[i + 1] - L[i] + 1) / k;//如何保证两个子区间中间只相差一个0呢？
			//我们由之前的代码知道，两个区间的中间连接的必定为一个0，因此我们将这个0变为1
			//使得这个区间和下一个区间完全相连，来看一下有多少个长度为k的连续为1的子区间
//			printf("%d %d\n", t1, t2);
			if (t2 > t1) {
				ans ++;
				break;
			}
		}
	}
	if (cnt == 0 && k == 1)ans = 1;//特殊判断
	printf("%d\n", ans);
}
 
int main() {
//	 freopen("std3.in", "r", stdin);
//	 freopen("std3.out", "w", stdout);
	int T = 1;
	scanf("%d", &T);
	while (T--) sol();
	return 0;
}