1415: 小ho的01串 [字符串]
题目描述
有一个由0和1组成的字符串，它好长呀--------一望无际
恩，说正题，小ho的数学不太好，虽然是学计算机的但是看见0和1也是很头疼的，
现在他的老师想让他计算出来包含K个1的子串有多少个-----呀，头要炸了！！！
小ho知道你的数学棒棒哒，所以来找你帮忙了。
输入
第一行是一个数K。
第二行是一个字符串str。
0 < |str| ≤ 106
输出
一个数S,代表了满足条件的个数。
样例输入
2
101010
样例输出
6
57
C/C++ (clang++ 3.3)
1
#include<iostream>
2
#include<cstdio>
3
#include<cstdlib>
4
#include<cstring>
5
#include<algorithm>
6
#include<queue>
7
#include<list>
8
#include<cmath>
9
#include<vector>
10
using namespace std;
11
const int maxn=1000010;
12
char str[maxn];
13
long long num[maxn];
14
int main()
15
{16
// freopen("in1.txt","r",stdin); //查BUG17
// freopen("out1.txt","w",stdout);18
long long ans=0,k,cnt=1;
19
scanf("%lld%s",&k,str);20
long long l=1,r,len=strlen(str),temp=0;num[0]=-1;
21
if(k==0)
22
{23
l=0;
24
for(long long i=0;i<len;++i)
25
{26
if(str[i]=='1')
27
{28
r=i-l;l=i+1;
29
ans=ans+r*(r+1)/2;
30
//cout<<ans<<endl;
31
}
32
}
33
r=(len-l);
34
ans=ans+r*(r+1)/2;
35
cout<<ans<<endl;
36
return 0;
37
}
38
for(long long i=0;i<len;++i)
39
{40
if(str[i]=='1')
41
{42
temp++;num[cnt++]=i;
43
}
44
if(temp==k+1)
45
{46
ans=ans+(num[l]-num[l-1])*(num[cnt-1]-num[cnt-2]);l++;temp--;
47
//cout<<num[l]-num[l-1]<<endl;
48
}
49
}
50
if(temp==k)
51
{52
ans=ans+(num[l]-num[l-1])*(len-num[cnt-1]);
53
}
54
cout<<ans<<endl;
55
return 0;
56
}