[code source] daily one question three paragraph

2022.05.08

Topic link ： Three paragraph - subject - Daimayuan Online Judge

Title Description

There is a length of n Sequence , Now we want to cut it into three sections ( Every paragraph is continuous ）, Make the sum of the elements of each paragraph the same , How many different cutting methods are there

Input description

The first line gives a number nn,(1≤n≤10^5)

The second line gives the sequence a1,a2,a3,...,an,(|ai|≤10^5)

Output description

Output a number to indicate how many different cutting methods there are

The sample input

4
1 2 3 3

Sample output

1

Sample explanation

It can be divided into the first group 1,2, The second group 3, The third group 3

analysis ：

The title requires that an array be divided into three consecutive segments and the same as , It is to find two different positions in the array to make the values of the three parts equal ,O（n^2） The method of direct violence enumeration is very simple , Obviously it's going to be overtime , So how to optimize ？ use num1 Indicates the sum of the first paragraph ,num2 Indicates the sum of the second paragraph .num1 and num2 The size of is certain , Every num2 It can be compared with all the previous num1 Can meet the conditions , So you only need to record how many are in front of the current position num1 The position of .

See the code for details. ：

#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; // Preprocessing prefixes and 
    }
    int cnt = 0, res = 0;
    if (a[n] % 3 || n <= 2) // Sum is not 3 The multiple or array size of is less than 3 It is impossible to meet the conditions , Output 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; // Add current num1 The number of , namely num2 The front is num1 The number of 
        }
        if (a[i] == num1)
        {
            cnt++;
        }
    }
    cout << res;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
}