寮步网站建设价钱,建网站的公司哪里好,建站模板 discuz,无货电商怎么入门AcWing《蓝桥杯集训每日一题》—— 3956. 截断数组 文章目录AcWing《蓝桥杯集训每日一题》—— 3956. 截断数组一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的#xff0c;转md文件可能不太美观#xff0c;大家可以去我的博客中查看#xff1a;北天的 BLOG…AcWing《蓝桥杯集训·每日一题》—— 3956. 截断数组 文章目录AcWing《蓝桥杯集训·每日一题》—— 3956. 截断数组一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、题目
✍ 给定一个长度为n的数组a1, a2,.. . , an 。 现在要将该数组从中间截断得到三个非空子数组。
要求三个子数组内各元素之和都相等。
请问共有多少种不同的截断方法?
输入格式
第一行包含整数n。
第二行包含n个整数a1, a2,… . , an。
输出格式
输出一个整数表示截断方法数量。
数据范围
前六个测试点满足1≤n≤10。
所有测试点满足1≤n≤10^5-10000≤a_i≤10000。
输入样例1
4
1 2 3 3输出样例1
1输入样例2
5
1 2 3 4 5输出样例2
0输入样例3
2
0 0输出样例3
0二、解题思路 当我们看见这个题目时我们可以从以下几个方面去思考解决这个问题 首先需要确定数组的长度是否符合题目中的要求也就是说长度是否大于等于3。如果数组的长度符合要求您可以计算出数组的总和并判断总和是否能够被3整除。如果数组的总和可以被3整除您可以计算出每个子数组的目标和。接下来您可以使用前缀和数组来预处理数组的前缀和。然后您可以遍历前缀和数组如果当前前缀和等于目标和的两倍则该点是可能的分割点。最后您可以从第一个可能的分割点开始计算其他可能的分割点的数量并将其加入答案。
通过使用前缀和我们可以在O(n)的时间复杂度内解决此问题。
什么是前缀和
前缀和是一种数学技巧用于快速求出一个数组的前缀和。前缀和数组定义为对于数组a中的每个元素a[i]前缀和数组prefix[i]表示a[0]到a[i]的和。
例如对于数组a[1, 2, 3, 4, 5]前缀和数组prefix为[1, 3, 6, 10, 15]。
使用前缀和数组可以在O(1)的时间复杂度内查询数组中某一段元素的和而不需要重新遍历数组。这在很多题目中如区间求和有很多应用。
三、代码实现
具体实现代码如下 def cut(n, nums):# 判断数组元素个数是否小于3若是则不存在可行解直接返回0if n 3:return 0# 求数组元素和s sum(nums)# 判断数组元素和是否为3的倍数若不是则不存在可行解直接返回0if s % 3 ! 0:return 0# 将数组元素和除以3得到每段的平均值avg s // 3# 初始化cnt数组用于存储每个前缀的符合要求的数量cnt [0] * (n 1)# 初始化presum数组用于存储每个前缀的元素和presum [0] * (n 1)# 枚举每个前缀计算元素和for i in range(1, n 1):presum[i] presum[i - 1] nums[i - 1]# 枚举每个前缀判断元素和是否为2倍的平均值for i in range(1, n):if presum[i] avg * 2:cnt[i] 1# 枚举每个前缀累加符合要求的数量for i in range(1, n):cnt[i] cnt[i - 1]# 初始化结果为0res 0# 枚举每个前缀判断元素和是否为平均值for i in range(n - 2):if presum[i 1] avg:res cnt[n - 1] - cnt[i 1]# 返回结果return resn int(input().strip())
nums list(map(int, input().strip().split()))
print(cut(n, nums))
