题目链接:Codeforces 466C Number of Ways
题目大意:给定一个序列,要求分成三段,每段和相同,问有多少种拆分方法。
解题思路:将所有前缀和为sum3的位置全部记录下来,然后在逐个计算后缀和,然后对应如果和为sum3,计算该位置前有多少个前缀和sum3。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5 * 1e5 + 5;
int n, arr[maxn];
ll s = 0;
vector<int> vec;
ll solve () {
if (s % 3)
return 0;
s /= 3;
ll p = 0, ret = 0;
for (int i = 0; i < n; i++) {
p += arr[i];
if (p == s)
vec.push_back(i);
}
p = 0;
for (int i = n-1; i >= 0; i--) {
p += arr[i];
if (p == s)
ret += lower_bound(vec.begin(), vec.end(), i-1) - vec.begin();
}
return ret;
}
int main () {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
s += arr[i];
}
printf("%lld\n", solve());
return 0;
}