CodeForces 165C Another Problem on Strings

最新推荐文章于 2024-07-25 20:12:28 发布

追逐星辰的光

最新推荐文章于 2024-07-25 20:12:28 发布

阅读量291

点赞数

分类专栏：计数文章标签：计数

本文链接：https://blog.csdn.net/CS33sun/article/details/79162043

版权

计数专栏收录该内容

1 篇文章

订阅专栏

A string is binary, if it consists only of characters "0" and "1".

String v is a substring of string w if it has a non-zero length and can be read starting from some position in string w. For example, string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. So, if some string occurs multiple times, we should consider it the number of times it occurs.

You are given a binary string s. Your task is to find the number of its substrings, containing exactly k characters "1".

Input

The first line contains the single integer k (0 ≤ k ≤ 10⁶). The second line contains a non-empty binary string s. The length of s does not exceed 10⁶ characters.

Output

Print the single number — the number of substrings of the given string, containing exactly k characters "1".

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Example

Input

1
1010

Output

Input

2
01010

Output

Input

100
01010

Output

Note

In the first sample the sought substrings are: "1", "1", "10", "01", "10", "010".

In the second sample the sought substrings are: "101", "0101", "1010", "01010".

题意很清楚，给一个字符串s，和一个数字k，询问有多少个子串满足1的数目等于k。

1：先特殊考虑k=0这种情况，当k=0时，我们只需要考虑连续0的个数。比如连续的0的个数为ans，那么此时有ans*(ans+1)/2个子串满足。所以我们只需要遍历一下字符串，每次求一段连续的0，然后计数就可以了。

2：然后再考虑k>0这种情况，当k>0时，我们需要记录每个'1'字符左右的'0'字符的个数。比如k=1,s="0100",那么字符'1'的左右分别有1和2个'0'字符，满足要求的子串为'01' , '1' , '010' , '10' , '0100' , '100'，个数为6，所以可以得出结果为左右字符'0'的个数加上1相乘即可，为了方便，我们计数的时候初始化为1，所以直接用l*r即可（l代表左边字符'0'的个数，r代表右边字符'0'的个数)。

需要注意的一点是题目是数据范围很大，我除了k之外，其他的都用了long long ，不然会莫名的wa。具体请看代码：

#include <stdio.h>
#include <string.h>
#define ll long long
char c[1000006];
struct node{ //存字符1的左右字符0的个数 
	ll l, r;
}s[1000006];
int main() {
	int k;
	while(~scanf("%d", &k)) {
		scanf("%s", c);
		ll m = strlen(c);
		ll t = 0, ans = 1;//t代表字符1的个数 ， ans用于计数0 
		ll sum1 = 0, sum2 = 0;//sum1用于计算当k>0时的结果，sum2用于计算k=0的结果 
		for(int i = 0; i < m; i++) {
			if(c[i] == '0') ans++; //计数 
			else {
				sum2 += (ans*(ans-1))/2;//因为ans初始为1，所以是ans*(ans-1)/2 
				if(t == 0) {            //当t=0的时候记录左边的值ans
					s[t++].l = ans;
				}
				else {
					s[t-1].r = ans;     //记录上一个字符1的右边字符0的个数 
					s[t++].l = ans;     //记录此时字符1左边0的个数，这两步要弄懂
				}                       //两个1字符中间的字符0的个数需要格外注意 
				ans = 1;                //重新开始找
			}
			if(i == m-1) {              //当找到最后的时候需要格外考虑一下 
				sum2 += (ans*(ans-1))/2;
				s[t-1].r = ans;
			}
		}
		if(k == 0) {               //当k=0的时候 
			printf("%lld\n", sum2);
			continue;
		}
		ll l = 0;
		ll r = l+k-1;
		while(r < t) {
			sum1 += s[l].l*s[r].r;
			l++;r++;
		}
		printf("%lld\n", sum1);
	}
	return 0;
}