AcWing 3956. 截断数组
本文最后更新于615 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com

题目

给定一个长度为 n的数组 a1,a2,…,an。

现在,要将该数组从中间截断,得到三个非空子数组。

要求,三个子数组内各元素之和都相等。

请问,共有多少种不同的截断方法?

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数,表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤1e5,−10000≤ai≤10000。

输入样例1:

4
1 2 3 34
1 2 3 3

输出样例1:

1

输入样例2:

5
1 2 3 4 5

输出样例2:

0

输入样例3:

2
0 0

输出样例3:

0

思路:

1.分为三个数组,并且和相等,也就意味着每个部分都是总和的1/3

2.总和必须能整除3

3.相当于要在数组上找两个位置,第一个位置 sum/3,第二个位置 (sum/3)*2

4.这两个位置可取的点都有若干个,那么它们的全部组合为(第一个位置可取的点)*(第二个位置可取的点)

//注意数据范围

代码:

#include<iostream>
using namespace std;
long long sum[100005];
long long n, tmp,ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    if (sum[n] % 3 != 0)ans = 0;
    else
    {
        long long cnt = 0;
        tmp = sum[n] / 3;
        for (int i = 1; i < n; i++)
        {
            if (sum[i] == 2 * tmp)ans += cnt;
            if (sum[i] == tmp)cnt++;
        }
    }
    cout << ans;
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇