首页 > 试题广场 >

喜欢切数组的红

[编程题]喜欢切数组的红

热度指数：9200 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小红有一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，她打算将数组切两刀变成三个非空子数组，使得每一个子数组中至少存在一个正数，且每个子数组的和都相等。
$\hspace{15pt}$ 看起来不是很难，所以小红想让你求解，一共有多少种不同的切分方案。

输入描述:

第一行输入两个整数  代表数组中的元素数量。
第二行输入  个整数  代表数组元素。

输出描述:

在一行上输出一个整数，代表切分方案数。

示例1

输入

3
3 3 3

输出

示例2

输入

6
1 1 4 5 1 4

输出

示例3

输入

10
0 3 4 2 3 2 1 -1 3 4

输出

算法知识视频讲解

Bezime

发表于 2024-11-24 21:59:25

E题题解：时间复杂度O(n)哦！题目大意：给数组切 2 刀，每份总和相等，都要包含正数思路：首先定义一个前缀和数组 sum，sum[i]=a[1]+a[2]+...+a[i]。如果 sum[n] 不是三的倍数，怎么切，都不行。直接考虑第一刀砍在 i，i+1 之间，求右边能切的位置数量，展开全文

可爱大狐狸若藻

发表于 2024-11-24 22:39:00

E解题思路要将数组切分成三个满足条件的子数组，需要满足以下条件：总和可被3整除：数组的总和必须能够被3整除，否则无法均分为三个相等的子数组。每个子数组至少有一个正数：在切分的位置，需要确保每个子数组包含至少一个正数。子数组和相等：每个子数组的和必须等于。具体步骤展开全文

yitouerbi

发表于 2024-11-24 21:11:47

题目大意把一个数组分成三个部分，每个部分和相同，且都有至少一个正数。思考过程容易证明，若总和不是3的倍数或者数组中没有整数，则方案数为0 解题过程分两类情况 1.总和不是3的倍数或者数组中没有整数输出0 2.其他情况可以维护一个前缀和数组遍历 CODE #include <bits 展开全文

星图史话

发表于 2025-10-12 14:13:44

//***只要你目光是瞄准月亮迷失过又有何妨***// #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n; int a[N]; int pre[N]; int res[N]; bool fl 展开全文

洋洋@王者荣耀

发表于 2025-05-23 11:37:51

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文

庆余年202304042113228

发表于 2025-04-20 10:37:29

import java.util.HashMap; import java.util.LinkedList; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public 展开全文

11155454

发表于 2025-03-25 20:34:54

#include <iostream> using namespace std; long long v[200005],pre_sum[200005],aft_sum[200005]; int main() { long long n; cin>>n; 展开全文

TQ988

发表于 2025-07-08 02:02:29

import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { 展开全文

牛客94987038号

发表于 2025-04-03 10:52:24

import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in. 展开全文

帅气的干饭人在吃瓜

发表于 2025-05-30 16:57:16

import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.h 展开全文

问题信息

动态规划

难度：

25条回答 166收藏 609浏览

喜欢切数组的红

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

相关试题