题目大意
把一个数组分成三个部分,每个部分和相同,且都有至少一个正数。
思考过程
容易证明,若总和不是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;
}