2022.10.29每日一题

Daimayuan Online Judge-01序列

题目描述

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

输入格式

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

输出格式

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

数据范围

$0\le k\le {10}^6,|s|\le {10}^6$

样例输入1

1
1010

样例输出1

6

样例输入2

2
01010

样例输出2

4

解题思路

我们考虑使用双指针算法

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

C++代码

#include 
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;
}