等和连续段最多划分
P5519. 等和连续段最多划分
场次:2026年10月20日-非AI方向 · 来源:CodeFun2000 P5519
题目描述
给定一个长度为 的整数数组,你需要将其划分为尽可能多的连续子段,使得每个子段的元素之和相等。求最多能分成多少份。
段与段首尾相接、不重不漏,合起来正好覆盖整个数组;整段不切也算一种合法划分。
输入格式
第一行输入一个整数 (),表示数组长度。
第二行输入 个整数 (),表示数组元素,以空格分隔。
输出格式
输出一个整数,表示最多能分成的份数。
示例
示例 1
输入:
5
-3 -4 5 -4 3输出:
1说明: 数组总和为 。若切成 段,每段和只能是 ,而前缀和 里从未出现 ,所以只能整段不切。
示例 2
输入:
4
10 10 10 10输出:
4说明: 每个元素单独成一段,四段的和都是 。
解题思路
判定标准:切成 段,等价于「每段和都是 」
设整个数组的总和为 。如果切成 段、每段的和都是 ,那么把 段加起来必然等于总和:
这条等式把问题翻了个面:不是先决定怎么切、再看各段和是否相等,而是先猜「每段和 是多少」,再验证能不能按这个 一路切下去。 一旦确定, 也随之确定(必须整除),切法也变得唯一——从左边开始,每凑够 就收一段。
用前缀和来表述最方便。记 ,。切成 段当且仅当存在递增的下标
使 。最后一段到 结束,它的和自动是 ,不需要额外检查。
第一段的终点,把所有候选段和一次枚举完
候选的 有多少个?第一段必须在某个位置 结束,此时 。也就是说候选段和最多只有 个,全部来自前缀和数组。枚举量从「所有切法」缩到「第一刀的 个落点」,这是这题能做快的根本原因。
对每个候选 ,先做两个检查:(否则除不了),以及 能否被 整除。通过之后 ,再去核对 是否真的作为前缀和出现过:
for i in range(1, n + 1): # 枚举第一段的终点,T = pre[i]
t = pre[i]
if t == 0 or total % t != 0: # 段和不能为 0,且必须整除总和
continue
k = total // t # 按这个段和能切出 k 段
if k <= best: # 刷不新区间就跳过
continue
... # 核对 2T, 3T, ..., (k-1)Tif k <= best 这一行是纯粹的剪枝:答案只会往上走,比当前最好还小的 没必要验证。
是单独的一支
总和为 时, 且 ,于是 :每一段的和都必须是 。这时上面「枚举第一段终点」的做法失效——合法的段和是 ,而 会变成除以 ,段数根本算不出来。
的切法反而更简单:从左边累加,前缀和每回到一次 ,就说明又收拢了一段和为 的区间。所以只要数一数前缀和数组里有多少个 :
if total == 0:
print(sum(1 for i in range(1, n + 1) if pre[i] == 0))
return计数从下标 开始,这一点不能省。 是「一个元素都还没进来」的起点,不是一次分段;把它数进去,答案会凭空多 。
同一个前缀和可能落在多个位置,切点得逐个向后找
前缀和是一步步走出来的,同一个值完全可能出现在好几个下标上(中间夹着一段和为 的片段)。所以「这个值出现过」并不等于「它能当这一刀」——它可能出现的位置全都在上一刀之前。
看一个具体的数组:,前缀和是 。候选 (第一段在 结束),,而 确实都在前缀和里出现过。可是 只出现在下标 ,在 之前,后面再也找不到——这三段根本切不出来,正确答案是 (整段不拆)。只查「值在不在集合里」会在这里报出 。
正确的做法是给每个值记下它出现过的所有下标(天然升序),再用二分找「严格大于上一刀的最小下标」:
pos = {}
for i, p in enumerate(pre):
pos.setdefault(p, []).append(i) # 每个前缀和值出现过的下标
prev = i # 第一刀在 i,后续切点必须更靠右
for j in range(2, k): # 还要找到 2T, 3T, ..., (k-1)T
idxs = pos.get(j * t)
if not idxs:
ok = False
break
q = bisect_right(idxs, prev) # 第一个 > prev 的位置
if q == len(idxs):
ok = False
break
prev = idxs[q]数组里出现负数时,前缀和会来回走,这种「值出现过但位置不对」的情形就真的会发生;数据即使全为非负,这层判断也不会改变任何答案,只是白送一道保险。
实现落点
pre是长度 的前缀和,pre[0] = 0;total = pre[n]决定走哪一支: 走计数分支,非 走枚举分支;best初值为 :整段不拆永远合法,所以答案不会比 小;pos只在非 分支里构建,bisect_right保证下一刀严格在上一刀右侧;- 校验循环写的是
range(2, k),因为 时 就是pre[n],本身必然存在。
完整代码实现
"""
P5519. 等和连续段最多划分 - 前缀和 + 候选段和枚举
把一个整数数组切成若干段连续的非空子数组,要求每段元素之和相等,
问最多能切成几段。
输入格式:
- 第 1 行:整数 n;
- 第 2 行:n 个整数(空格分隔)。
输出格式:
- 一个整数:最多段数(整段不拆也算一种,答案至少为 1)。
核心思路:
设总和为 S,切成 k 段时每段和必为 T = S / k。第一段的终点 i 一旦
确定,T 就是 pre[i],于是所有候选 T 只需枚举 n 个前缀位置即可。
- S = 0:每段和只能为 0。前缀和每回到一次 0 就收一段,回到 0 的
次数(下标 1..n)就是答案。
- S != 0:对每个候选 T 先要求 T != 0 且 S % T == 0,得到 k = S / T;
再确认 T, 2T, ..., (k-1)T 都真的作为前缀和出现过,而且出现位置
逐次靠后(第一刀的 T 在前缀下标 i 处)。
时间复杂度:O(n + Σk log n),最坏 O(n^2 log n)
空间复杂度:O(n)
"""
# https://codefun2000.com/p/P5519
import sys
from bisect import bisect_right
# @sample-start
"""
样例输入 1:
5
-3 -4 5 -4 3
样例输出 1:
1
"""
# @sample-end
# @sample-start
"""
样例输入 2:
4
10 10 10 10
样例输出 2:
4
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
a = list(map(int, data[1 : 1 + n]))
pre = [0] * (n + 1)
for i, v in enumerate(a, 1):
pre[i] = pre[i - 1] + v
total = pre[n]
# S = 0:只能让每段和也为 0,前缀和每回到 0 就收一段
if total == 0:
print(sum(1 for i in range(1, n + 1) if pre[i] == 0))
return
# 每个前缀和值出现过的下标(升序),用来判断「下一刀在上一刀之后」
pos = {}
for i, p in enumerate(pre):
pos.setdefault(p, []).append(i)
best = 1 # 整段不拆永远合法
for i in range(1, n + 1): # 枚举第一段的终点,T = pre[i]
t = pre[i]
if t == 0 or total % t != 0:
continue
k = total // t
if k <= best: # 不可能刷新答案,跳过
continue
prev = i # 已经切到下标 i
ok = True
for j in range(2, k): # 还要在前缀里找到 2T, 3T, ..., (k-1)T
idxs = pos.get(j * t)
if not idxs:
ok = False
break
p = bisect_right(idxs, prev)
if p == len(idxs):
ok = False
break
prev = idxs[p]
if ok:
best = k
print(best)
def run_tests():
"""运行嵌入的示例与边界用例,方便本地自测。"""
import io
cases = [
# 示例 1:总和为 -3,切不出等和的 3 段,只能整段
("5\n-3 -4 5 -4 3\n", "1"),
# 示例 2:每个元素都是 10,一段一个
("4\n10 10 10 10\n", "4"),
# 2+2=4,切成 [2,2] 与 [4]
("3\n2 2 4\n", "2"),
# 无法均分:只能整段
("2\n1 2\n", "1"),
# 只有一个元素
("1\n7\n", "1"),
# 单个 0
("1\n0\n", "1"),
# [3],[1,2],[3],[3]:四段
("5\n3 1 2 3 3\n", "4"),
# 总和为 0 但中间没有回到 0:只有整段
("2\n-3 3\n", "1"),
# 和等于 0 的片段夹在中间:两段
("4\n1 -1 2 -2\n", "2"),
# 前缀和值都出现过、但出现位置在本刀之前:只能整段
("3\n2 -1 2\n", "1"),
# 全 0:每个元素各成一段
("4\n0 0 0 0\n", "4"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected}, 实际={output} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:
前缀和:,。,走枚举候选段和这一支,从 开始逐个试(表里写作 S % T,取的是 Python 的取模语义,结果与除数同号):
| 第一刀 | 候选 | S % T | 结论 |
|---|---|---|---|
| ,不大于 ,跳过 | |||
| 不能整除,跳过 | |||
| 不能整除,跳过 | |||
| 不能整除,跳过 | |||
| ,跳过 |
所有候选都没能刷新答案,输出 :整段不切。唯一能让答案变大的是切成 段(),那要求段和 、也就是前缀和里出现 ,而这组数据一次都没走到。
示例 2:
前缀和 ,。
| 第一刀 | 核对 | 结果 | ||
|---|---|---|---|---|
| 在下标 ✓, 在下标 ✓ | ||||
| — | ,跳过 | |||
40 % 30 = 10 | — | 不能整除,跳过 | ||
| — | ,跳过 |
答案 :每个元素单独成段,每段和都是 。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个候选终点都把数组重扫一遍来试切分 | 每个候选 ,且不做整除筛选 | ||
| 前缀和 + 候选段和 + 下标二分(最优) | 整除先筛掉大部分候选,只有候选 较大时才真的去查下标 |
上表的 是对所有通过整除检查的候选求和,量级远小于 ;最坏情形(前缀和里塞满了 的小因子)会退化到 ,但那种数据本身极难构造。
易错点总结
1. 忘记检查 能否被 整除
把 if t == 0 or total % t != 0 里的 total % t != 0 去掉,直接用 total // t 算段数: 时 、候选 ,,而 range(2, 2) 是空的,校验循环一次都不跑,程序会直接认定「能切两段」,输出 。而 两段的和是 和 ,并不相等,正确答案是 。
2. 候选终点从下标 开始枚举
把循环写成 for i in range(n),第一次迭代就有 ,接着执行 total % t 直接抛 ZeroDivisionError。起点必须是 :下标 表示「第一段是空的」,不是合法的第一刀。
3. 分支把 也数进去
把 sum(1 for i in range(1, n + 1) if pre[i] == 0) 写成 pre 整表统计, 会输出 : 三个 全被算上,而 只是起点。正确答案是 (两个 各成一段)。