网站建设合同模板下载全媒体运营师报名费多少钱
AcWing 3956. 截断数组
题目描述
给定一个长度为 nnn 的数组 a1,a2,…,ana_1, a_2, …, a_na1,a2,…,an 。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
输入格式
第一行包含整数 nnn。
第二行包含 nnn 个整数 a1,a2,…,ana_1, a_2, …, a_na1,a2,…,an 。
输出格式
输出一个整数，表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤101≤n≤101≤n≤10 。
所有测试点满足 1≤n≤1051≤n≤10^51≤n≤105，−10000≤ai≤10000−10000≤a_i≤10000−10000≤ai≤10000 。
输入样例1：
4
1 2 3 3
输出样例1：
1
输入样例2：
5
1 2 3 4 5
输出样例2：
0
输入样例3：
2
0 0
输出样例3：
0
思路
先预处理前缀和，先判断如果s[n] % 3 != 0 ，则不能被均分为三份，输出 0.
然后从 i = 3 开始枚举前缀和数组，以 iii 作为切割点，s[i - 2] 为第一段，s[n] - s[i - 1] 为第三段，如果 第一段 = 第三段 = s[n]/3s[n] / 3s[n]/3，则第二段也一定相等，都符合条件。
先判断第一段是否符合，记录个数，如果第三段不符合，则表示该切割点不行，继续后移，每次当第三段符合时，都加上第一段符合的个数即可。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;int n;
ll s[N];int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> s[i];s[i] += s[i - 1];}if (s[n] % 3){cout << 0 << endl;return 0;}ll cnt = 0, res = 0;for (int i = 3; i <= n; i++){if (s[i - 2] == s[n] / 3) cnt++;if (s[n] - s[i - 1] == s[n] / 3) res += cnt;}cout << res << endl;return 0;
}