Eugene and an array CodeForces - 1333C （思维）

题目大意：求好数组的个数，所谓好数组 1好数组是原数组的一段连续的子数组，2 好数组不包含元素和为0的子数组。

题解：唉，这个题目把我给些懵了....我一开始的想法求后缀和，保存位置，然后枚举前缀和，二分查找大于当前位置的第一个后缀合，但是ai的范围太大了，位置保存不了，然后又瞎搞了很久....最后看的题解，没想到这么简单....（吐了）直接用前缀和，如果两个前缀和相等比如果说[1,l]和[1,r]那么[l+1,r]，这段区间内的和一定为0，

然后好数组怎么求呢？当然就是[l+2,r],[l+3,r]....[r,r]。也就是他的区间长度。。。我们可以枚举没个前缀和，让i做右端点，然后用mp保存最右边的左端点。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=2e5+;

map<ll,ll >mp;

int main(){

    ll n;

    cin>>n;

    ll sum=;

    ll tmp=;

    mp[]=;

    ll x,maxl=;

    ll ans=;

    for(ll i=;i<=n+;i++){

        cin>>x;

        sum+=x;

        if(mp[sum]!=) maxl=max(maxl,mp[sum]+);

        ans+=i-maxl;

        mp[sum]=i;

    }

    cout<<ans<<endl;

    return ;

}

巴特西

Eugene and an array CodeForces - 1333C （思维）

最新文章

热门文章