Eugene and an array(边界麻烦的模拟)

一道看似小学生的题，搞了我几个小时......

首先思路就有两种:

\(Ⅰ.找和为0的bad子串，再用n*(n+1)/2-bad子串得到答案\)

\(Ⅱ.找和不为0的good子串\)

如果你选择找bad子串就很麻烦了。(为什么呢?自己去试一试吧，不好说。)

这里找good子串，枚举每一个数作为区间的右端点。

\(那么往左找一个前缀和为0的左端点，答案贡献就是i-l+1\)

\(特殊的，对于第一个前缀和为0的要特判。\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+9;

ll n,a[maxn],sumn,ans,L=0;

map<ll,ll>m;

int main()

{

	cin>>n;

	int flag=0;

	m[0]=0;

	for(int i=1;i<=n;i++)

	{

		scanf("%lld",&a[i]);

		sumn+=a[i];

		if(m[sumn])	L=max(L,m[sumn]+1);

		else if(sumn==0)//特判，也要更新

			L=max(L,(ll)1);

		ans+=i-L;

		m[sumn]=i;

	}

	cout<<ans;

}

巴特西

Eugene and an array(边界麻烦的模拟)

最新文章

热门文章