2022.10.29每日一题

Daimayuan Online Judge-01序列

题目描述

我们称一个字符串为好字符串，指这个字符串中只包含 \(0\) 和 \(1\)。
现在有一个好字符串，求这个字符串中 \(1\) 恰好出现 \(k\) 次的子串有多少个。

输入格式

第一行给出一个数字 \(k\)，表示子串中 \(1\) 的个数。
第二行给出好字符串。

输出格式

输出一个整数，表示好字符串中有多少个符合条件的子串。

数据范围

\(0≤k≤10^6,|s|≤10^6\)

样例输入1

1
1010

样例输出1

6

样例输入2

2
01010

样例输出2

4

解题思路

我们考虑使用双指针算法

• \(k=0\)：那么我们只能取全为 \(0\) 的子串，比如我们有 \(00000\)，那么子串的个数应该是 \(\frac{n*(n+1)}{2}\)，简单推导一下就可以了
• \(k\ !=0\)：那么我们考虑一个子串，如果其含有 \(k\) 个 \(1\)，那么如果其两头有若干个 \(0\)，加上这些 \(0\)，仍然是符合要求的子串，从第一个 \(1\) 往前，也就是前导 \(0\) 的个数和最后一个 \(1\) 往后，后置 \(0\) 的个数的乘积就是符合要求的子串数，把所有的加起来就是答案

C++代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int k;
string s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> k;
    cin >> s;
    int len = s.size();
    int cnt = 0;
    LL res  = 0;
    if(k == 0)
    {
        for(int i = 0; i < len; i ++)
        {
            if(s[i] - '0') continue;
            int j = i;
            while(s[j] - '0' == 0 && j < len)
            {
                j ++;
            }
            // cout << i << ' ' << j << endl;
            res += ((LL)(j - i + 1) * (LL)(j - i) / 2);
            i = j;
        }
        cout << res << endl;
        return 0;
    }
    for(int i = 0, j = 0; i < len; i ++)
    {
        while(j < len)
        {
            if(s[j] == '1')
                cnt ++;
            if(cnt == k)
                break;
            j ++;
        }
        if(cnt == k)
        {
            int ed = j + 1;
            while(ed < len && s[ed] != '1')
                ed ++;
            int c = ed - j; // 后置0
            while(i < len && s[i] != '1')
            {
                i ++;
                res += c;
            }
            res += c;
            j ++;
            cnt --;
        }
    }
    cout << res << endl;
    return 0;
}