Solution - [AGC023A] Zero-Sum Ranges

本文主要是介绍Solution - [AGC023A] Zero-Sum Ranges，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Solution.

不难想到前缀和，设 A 数组的前缀和为 \(sum\)， 如果 \(sum_i=sum_j\)，则 \(i \sim j\) 这一段的和一定为 \(0\) 。对于当前的 \(sum_i\)， 它就可以与之前的每一个值等于 \(sum_i\) 的元素构成区间和为 \(0\) ，于是我们就可以用一个桶维护每一个前缀和的值已经出现的数量。这里要注意对 \(sum_i=0\) 进行特判。这里我们可以用 map 来维护。

时间复杂度为 \(O(n \log n)\)

Code.

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[200005];
map<int, int> b;
int sum;
int ans;
signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		sum += a[i];
		if (sum == 0 && b[sum] == 0) {
			b[sum]++;
		}
		b[sum]++;
		ans += (b[sum] - 1);
//		cout << b[sum] << endl;
	}
	printf("%lld", ans);
	return 0;
} 

这篇关于Solution - [AGC023A] Zero-Sum Ranges的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！