【代码源】每日一题 三段式

2022.05.08

题目链接：三段式 - 题目 - Daimayuan Online Judge

题目描述

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

输入描述

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

第二行给出序列a1，a2，a3，...，an，(|ai|≤10^5)

输出描述

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

样例输入

4
1 2 3 3

样例输出

1

样例解释

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

分析：

题目要求将一个数组分成连续的三段并且和相同，就是在数组中找两个不相同位置使三个部分的值相等 ,O（n^2）的做法很简单直接暴力枚举，显然会超时，那么如何优化呢？用num1表示第一段的和，num2表示第二段的和。num1和num2的大小是确定的，每个num2可以和前面的所有的num1都可以满足条件，所以只需要记录当前位置前面有多少个num1的位置即可。

详见代码：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
#define int long long
int n, a[100009];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a[i] = a[i - 1] + x; //预处理前缀和
    }
    int cnt = 0, res = 0;
    if (a[n] % 3 || n <= 2) //总和不是3的倍数或者数组大小小于3都不可能满足条件，输出0
    {
        cout << 0;
        return;
    }
    int num1 = a[n] / 3, num2 = num1 * 2;
    for (int i = 1; i < n; i++)
    {
        if (a[i] == num2)
        {
            res += cnt; //加上当前num1的个数，即num2前面为num1的个数
        }
        if (a[i] == num1)
        {
            cnt++;
        }
    }
    cout << res;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
}