代码源：502、01序列-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

这是代码源div2的每日一题，对应cf分数1500。

知识点：前缀和+哈希表

01序列 – 题目 – Daimayuan Online Judge

我们称一个字符串为好字符串，指这个字符串中只包含’0’和’1’。

现在有一个好字符串，求这个字符串中’1’恰好出现k次的子串有多少个。

输入格式

第一行给出一个数字k，表示子串中’1’的个数。

第二行给出好字符串。

输出格式

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

数据范围

0≤k≤1e6, |s|≤1e6

样例输入1

1
1010
复制代码

样例输出1

6
复制代码

问题解析

题目要求我们找的是子串中1的个数为k的情况有多少，我们当然可以枚举字串的长度，然后遍历字串的组成情况，如果满足要求则计数器++，但这样的时间复杂度为O(n^2)，在这题1e6的数据下显然是会超时的，所以我们想办法把题目转化一下。

既然是子串，那就说明是连续的，且字符串除了0就是1，那么我们可以用前缀和的思路来写，这样问题就变成了，区间和为k的情况有多少。

我们计算子串的前缀和数组，并把相同前缀和的数量用哈希表记录下来。每一个前缀和为sum的位置，都能和所有前缀和为sum-k的位置形成好子串,所以我们计数器记录的是（前缀和为sum的数量 * 前缀和为sum-k的数量）。最后只要把计数器输出即可。

但有一种情况是特殊的，即k=0的情况，如果k=0，那么我们记录的子串数量就是（前缀和为sum的情况 * 前缀和为sum的情况），这显然是不对的，会出现重复的好子串。所以遇到k=0时我们应该特殊处理，它的子串数为：连续ans个0组成的子串，它能形成的不同好子串为：（ans+1） * ans/2。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<map>


typedef long long ll;
typedef pair<int, int>PII;
const int MOD = 1e9 + 7;
const int N = 100100;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int k, l = 0;
    cin >> k;
    string str;
    cin >> str;
    int n = str.size();
    map<int, ll>mymap;
    mymap[0]++;
    ll res = 0;
    vector<int>v(n + 1), sum(n + 1);
    if (k == 0)
    {
        ll ans = 0;
        //末尾加上1，防止字符串全是0的情况
        str += '1';
        n++;
        for (int i = 0; i < n; i++)
        {
            if (str[i] == '0')ans++;
            else
            {
                res += (ans + 1) * ans / 2;
                ans = 0;
            }
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            v[i] = str[i - 1] - '0';
            sum[i] = v[i] + sum[i - 1];
            mymap[sum[i]]++;
        }
        int ans = 0;
        while (mymap[ans + k] != 0)
        {
            res += mymap[ans] * mymap[ans + k];
            ans++;
        }
    }
    cout << res << endl;
    return 0;
}
复制代码