codeForces 165C.Another Problem on Strings （二分+前缀和）

题意：给你一个整数K和一个只含01的字符串s，问你在这个字符串s中有多少个含有k个‘1’的子串。

思路：k和字符串长度都为10^6，所以暴力枚举所有子串不行，我们可先求一个前缀和sum统计到当前位置有多少个1，这样我们每次只需要用右端点R的sum[R]减去左端点L的sum[L-1]，O（1）的复杂度就可以知道任意两个位置之间（也就是某个子串中）有多少个‘1’了，然后我们枚举子串起点i，然后对于每一个起点寻找sum[i - 1 ] + k的值有多少个，如果再去枚举复杂度太高，这里可以用两次二分第一个二分寻找到第一个不大于sum[i - 1] + k的位置pos1，第二个二分寻找到第一个大于sum[i - 1] + k 的位置pos2，那么pos2-pos1就是以i为起点的时候含有k个‘1’的子串个数。累加对于所有起点的pos2-pos1就是答案。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int sum[MAXN];
int main()
{
	int k;
	string s;
	while(cin>>k>>s)
	{
		int len = s.length();
		sum[0] = s[0] - '0';
		for(int i = 1; i < len; i++) sum[i] = sum[i - 1] + (s[i] - '0');
		long long ans = 0;
		for(int i = 0; i < len; i++)
		{
			int pos1,pos2; 
			//int pos1 = lower_bound(sum + i,sum + len,sum[i - 1] + k) - sum;
			int l = i,r = len,m = l + (r - l) / 2,key = sum[i - 1] + k;
			while(l < r)
			{
				if(sum[m] < key) l = m + 1;
				else r = m;
				m = l + (r - l) / 2;
			}
			pos1=m;
			//int pos2 = upper_bound(sum + i,sum + len,sum[i - 1] + k) - sum;
			l = i,r = len,m = l + (r - l) / 2,key = sum[i - 1] + k;
			while(l < r)
			{
				if(sum[m] <= key) l = m + 1;
				else r = m;
				m = l + (r - l) / 2;
			}
			pos2=m;
			ans = ans + (pos2 - pos1); 
		}
		printf("%lld\n",ans);
	} 
	return 0;
}
/*
1
1010
2
01010
100
01010
0
01010
*/

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
long long num[MAXN];
int main()
{
	int k;
	string s;
	while(cin>>k>>s)
	{
		memset(num,0,sizeof(num));//将num数组全部置为0，等价于一个for将num置为0 
		num[0] = 1;
		int len = s.length();
		long long cnt = 0,ans = 0;
		for(int i = 0; i < len; i++)  
	    {  
	        if(s[i] == '1') cnt++;//1的个数  
	        if(cnt >= k) ans += num[cnt - k];//截止到第i位，第 cnt-k 个1前面有几个0答案就有几种可能  
	        num[cnt]++;//第cnt个1前面的0的个数（cnt从0开始）  
	    }
		printf("%lld\n",ans);
	} 
	return 0;
}
/*
1
1010
2
01010
100
01010
0
01010
*/