[Daimayuan] 三段式（C++，数组前缀和）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Daimayuan] 三段式（C++，数组前缀和）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有一个长度为 $n$ 的序列，现在我们想把它切割成三段(每一段都是连续的），使得每一段的元素总和都相同，请问有多少种不同的切割方法

输入描述

第一行给出一个数 $n$ ，( $1≤n≤10^5$ )

第二行给出序列 $a_1$ ， $a_2$ ， $a_3$ ，…， $a_n$ ，( $a_i|≤10^5$ )

输出描述

输出一个数表示有多少种不同的切割方法

样例输入

4
1 2 3 3

样例输出

样例解释

可以将它分成第一组 $1$ ， $2$ ，第二组 $3$ ，第三组 $3$

解题思路

根据题意，很容易得到下面的公式：
$sum_1+sum_2+sum_3=sum\\ sum_1=sum_2=sum_3\\ \\ sum_1=sum_2=sum_3=\frac{1}{3}sum$
要满足题意有两个前提条件（特殊判定）：

（1） $sum\ \%\ 3==0$ ；

（2） $n\ge3$ 。

if (n < 3 || sum % 3 != 0) {
    cout << 0 << endl;
    return 0;
}

然后我们来寻找可能的分割方式。

如果有多于 $1$ 种的分割方法，那么一定存在子段和为 $0$ 。

与其去找子段和为 $0$ 的部分，不如转化思维，使用前缀和的概念（经常用于连续区间和问题）。

这样我们就只需要寻找前缀和同为 $\frac13sum$ 的部分了。

然后具体问题具体分析，因为题目中只要求分割为三段，所以我们直接找出前后两段 $\frac13sum$ 即可。

注意，至少要为中间的 $\frac13sum$ 预留一个元素的位置。

long long ans = 0;
for (int i = 1; i <= n - 1; i++) {
	if (pre[i] == subsum) {
		ans += tail_counter[i + 2];
	}
}

其中tail_counter中的元素意义为： $i$ 位置及其之后有多少个后缀和为 $\frac13sum$ 。

最后，AC代码如下：文章来源地址https://www.toymoban.com/news/detail-452101.html

#include <iostream>
using namespace std;
const int max_n = 1e5;

long long arr[max_n + 1], pre[max_n + 1], tail[max_n + 2];
long long tail_counter[max_n + 1];

int main() {
	int n;
	long long sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	if (n < 3 || sum % 3 != 0) {
		cout << 0 << endl;
		return 0;
	}
	long long subsum = sum / 3;
	for (int i = 1; i <= n; i++) {
		pre[i] = arr[i] + pre[i - 1];
	}
	for (int i = n; i >= 1; i--) {
		tail[i] = arr[i] + tail[i + 1];
		tail_counter[i] = tail_counter[i + 1];
		if (tail[i] == subsum) tail_counter[i]++;
	}
	long long ans = 0;
	for (int i = 1; i <= n - 1; i++) {
		if (pre[i] == subsum) {
			ans += tail_counter[i + 2];
		}
	}
	cout << ans << endl;
	return 0;
}