CF-466C Number of Ways 题解

题目大意

给你n个数，问你有多少种方式将其分为大小相同的三份$[l,i],[i,j],[j,r]$。

解题思路

之前写这个题目的时候完全没有思路。

比完一看题解。。。这个方法是真的妙。

我们可以先用前缀和，然后从一开始暴力枚举。

当枚举的前面部分的和为总和的三分之二时，则后面部分则必为总和的三分之一，这时只需要加上前面的和为总和三分之一的个数即可。

当枚举的前面的部分为总和的三分之一的时候，只需要统计个数。

需要注意这两条语句的个数，为三分之一的时候必须要在后面，不然会重复统计。

数据有点大，注意开ll。

完整代码

#include <iostream>
using namespace std;

const int N = 5e5 + 5;
typedef long long ll;
ll sum[N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		sum[i] = sum[i - 1] + a;
	}
	if (sum[n] % 3 != 0 || n < 3) {
		cout << 0 << endl;
		return 0 ;
	}
	ll ans, c;
	ans = c = 0;
	for (int i = 1; i < n; i++) {
		if (sum[i] == sum[n] / 3 * 2)	ans += c;
		if (sum[i] == sum[n] / 3)	c++;
	}
	cout << ans << endl;
}