CF1333 C. Eugene and an array

C. Eugene and an array

题意

给你一个长度为n的数组,求不含和为0的子串的个数。

思路

前缀和 思维
前缀和 p r e [ i ] = p r e [ j ] pre[i]=pre[j] pre[i]=pre[j]意味着 a i + 1 a j a_{i+1} \sim a_j ai+1aj这一段的和为0,则所求字符串不应该包含这段,令 p p p p r e [ i ] pre[i] pre[i]所在的位置,则不包含子串和为0的个数为 i ( p + 1 ) i-(p+1) i(p+1)
初始化 p o s [ 0 ] = 0 pos[0]=0 pos[0]=0

map.count(key) 返回值为bool型,表示是否存在key。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,q,s,ans;
map<ll,ll> pos;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	pos[0]=0;
	ll q=-1;
	for(int i=1;i<=n;i++){
		ll x;cin>>x;
		s+=x;
		if(pos.count(s)) q=max(q,pos[s]);
		ans+=i-q-1;
		pos[s]=i;
	}
	cout<<ans<<'\n';
	return 0;
}
全部评论

相关推荐

07-21 18:43
门头沟学院 Java
是暑期都招满了吗
ANEOY:今年感觉真是后端地狱级难度了,从暑期就是这样,前端需求非常大
点赞 评论 收藏
分享
07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务