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;
} 

上一篇:【TSP】基于matlab禁忌搜索算法求解31城市旅行商问题【含Matlab源码 1143期】


下一篇:信息学奥赛一本通(1143:最长最短单词)