huring
0%

2518-和为S

Posted on In

题目:
小b有一个01序列A，她想知道A有多少个非空连续子序列和为S。

你能帮帮她吗？

输入
第一行输入一个数n，表示A的长度；
第二行输入n个数‘0’或‘1’，表示A中的元素，以空格隔开；
第三行输入一个非负整数S；
其中0≤S≤n≤30000。

输出
输出一个数，表示子数组的个数
输入样例
5
1 0 1 0 1
2
解法:
统计每个1之前0的个数即可，然后组合计算一下乘积，注意处理S为0的情况。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
int sum[30010];
int main()
{
    int n;
    scanf("%d", &n);
    int now = 0;
    int l = 0;
    for(int i = 0;i < n; i++)
    {
        int s;
        scanf("%d", &s);
        if(s == 0){
            now++;
        }
        else{
            sum[l++] = now;
            now = 0;
        }
    }
    sum[l] = now;
    int s;
    scanf("%d", &s);
    long long ans = 0;
    if(s > 0){
        for(int i = 0; i + s <= l; i++)
        {
            ans += (sum[i] + 1) * (sum[i + s] + 1);
        }
    }
    else{
        for(int i = 0; i <= l; i++){
            //printf("%d\n", sum[i]);
            ans += sum[i] *(sum[i] + 1)/2;
        }
    }
    printf("%lld", ans);
    return 0;
}