codeforces-Ed93-C

codeforces-Ed93-C

八月 15, 2020

C. Good Subarrays

题意

给出一个数组(字符串形式) 每个位置有一个0~9的值

求出有多少个区间符合$∑_{i=l}^rai=r−l+1 $(区间和=区间长度)

题解

对于区间和问题想到数据结构或前缀和做差求区间和

对于这个问题要找到符合区间和=区间长度的区间有几个

我们可以先将这个条件转化一下 即变为 区间和 - 区间长度=0

我们扩展区间时 长度和区间和都在变化 但是每增加一个单位长度+1是确定的

于是就想到将区间长度信息融入到区间和,将 区间和 - 区间长度作为区间的整体属性 记为sum

对于数ai 将他加入某个区间,ai对区间和的贡献是 +ai 对区间长度的贡献是 +1

那么它对区间的sum属性的贡献是 +ai-1

于是从左到右维护一个前缀值sum

而我们要找的就是 当求得前i个数组成的区间(即前缀)的sum1 以它为右端点R

有多少个已被统计sum=sum1 能被作为左端点L 那么区间[L,R] 他就符合 区间和-区间长度=0

也就是：

区间和[1,R]-区间长度R = 区间和[1,L]-区间长度L

区间和(L,R]=区间长度R-区间长度L

区间和[L+1,R]=区间长度R-区间长度L

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e6+5;
const double Pi=acos(-1);
 
/*
*/
 
int main(){
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string s;cin>>s;
        int sum=0;ll ans=0;
        map<int,ll>cnt;cnt[0]=1;
        for(int i=0;i<n;i++){
            int temp=s[i]-'0';
            temp--;sum+=temp;
            ans+=cnt[sum];
            cnt[sum]++;
        }
        cout<<ans<<endl;
    }
}