C/C++教程

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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!