CodeForces 165C Another Problem on Strings

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 ≤ 106). The second line contains a non-empty binary string s. The length of s does not exceed 106 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 cincout streams or the %I64d specifier.

Example
Input
1
1010
Output
6
Input
2
01010
Output
4
Input
100
01010
Output
0
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;
}

### 关于 Codeforces 上二项装箱问题 #### 二项装箱问题概述 二项装箱问题是经典的组合优化问题之一,在计算机科学领域具有重要意义。该类问题通常涉及将一组不同大小的对象放入固定容量的容器中,目标是最小化使用的容器数量[^1]。 对于特定平台上的挑战实例,如Codeforces中的二项装箱问题,其核心在于设计高效算法来解决这一NP难问题。尽管找到最优解可能非常复杂,但存在多种启发式方法可以提供接近最佳的结果,并且这些方法能够在合理的时间内执行完毕。 #### 解决方案策略 一种常见的处理方式是采用贪心算法,即总是尝试把当前最大的未分配物品放置到第一个能够容纳它的箱子中;如果没有任何现有箱子能放下这件物品,则创建一个新的箱子用于装载它。这种方法简单易懂,但在某些情况下可能会导致次优解。 更复杂的近似算法包括首次适应下降(First Fit Decreasing, FFD),此技术首先按照降序排列所有项目尺寸,之后应用首次适配原则(FD)。FFD已被证明能在多项式时间内给出不超过理想最小值11/9倍数加四的解法质量保证[^2]。 此外还有其他高级求解途径比如动态规划、分支限界以及遗传算法等,它们各自适用于不同的应用场景并提供了不同程度上的性能改进。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> items(n); for(int i = 0; i < n; ++i){ cin >> items[i]; } sort(items.begin(), items.end(), greater<int>()); const int bin_capacity = 1000; // 假设每个bin的最大容量为1000单位体积 vector<int> bins; for(auto item : items){ bool placed = false; for(auto& b : bins){ if(b + item <= bin_capacity){ b += item; placed = true; break; } } if(!placed){ bins.push_back(item); } } cout << "Minimum number of bins required is: " << bins.size(); } ```
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值