题目大意

把一个数组分成三个部分,每个部分和相同,且都有至少一个正数。

思考过程

容易证明,若总和不是3的倍数或者数组中没有整数,则方案数为0

解题过程

分两类情况

1.总和不是3的倍数或者数组中没有整数

输出0

2.其他情况

可以维护一个前缀和数组遍历

CODE

#include <bits/stdc++.h>
using namespace std;
int n;
int a[200010];
typedef long long ll;
ll sum[200010];
ll sumz[200010];
int zheng = 0;
ll deng;
ll ans;

int mian() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum[i] = sum[i - 1] + a[i] + 0ll;
		sumz[i] = sumz[i - 1] + (a[i] > 0);
		if (a[i] > 0)
			zheng = i;
	}
	if (sum[n] % 3 != 0 || zheng == 0) {
		puts("0");
		return 0;
	}
	deng = sum[n] / 3;
	for (int i = 1; i <= n; i++) {
		if (sumz[i] == 0ll || sum[i] != deng)
			continue;
		for (int j = i + 1; j <= n; j++) {
			if (sumz[j] - sumz[i] == 0ll || sum[j] - sum[i] != deng)
				continue;
			if (sumz[n] - sumz[j] == 0ll || sum[n] - sum[j] != deng)
				continue;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}