CF165C解题报告

tang2hao4zhe2 · 2025-01-01 13:45:14 · 个人记录

洛谷

Solution

比较套路
当我们扫到位置i时，设当前1的个数为sum，i对答案的贡献就是sum-k的数量，用一个map记录就好了
注意初始化mp[0]=1

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> mp;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k;string s;
    cin>>k>>s;
    int n=s.size();s=' '+s;
    int sum=0;
    int ans=0;
    mp[0]=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='1') sum++;

        ans+=mp[sum-k];
        mp[sum]++;
    }
    cout<<ans<<endl;
    return 0;
}