分苹果方案
P5518. 分苹果方案
场次:2026年10月20日-非AI方向 · 来源:CodeFun2000 P5518
题目描述
有 个苹果要分给 个人,每个人可以分到 到 个苹果,要求苹果总量恰好分完。请输出所有合法的分配方案,方案按字典序升序排列,最后一行输出方案总数。
苹果彼此不作区分,人是有区别的:某个人拿到的个数变了,就是另一种方案。
输入格式
一行两个整数 ,以空格分隔。
数据范围: ,。
输出格式
每行输出一个方案,包含 个整数(空格分隔),依次表示第 个人到第 个人分到的苹果数。所有方案按字典序升序输出。
最后一行输出一个整数,表示方案总数。
示例
示例 1
输入:
0 2输出:
0 0
1说明: 个苹果分给 个人,只有一种分法;最后一行 1 是方案总数。
示例 2
输入:
2 1输出:
2
1说明: 只有一个人时,苹果全归他,方案唯一。第一行是方案本身,第二行是计数。
解题思路
输出里有两件事:先列出全部方案,再报一次总数
题面的输出由两部分组成,判定标准也要分开看。
方案长什么样: 一个方案就是一个长度为 的整数序列 ,要求每个 ,且 。人是互不相同的,所以第 个位置上的数字属于第 个人,位置一换就是另一种方案;苹果是相同的,所以同一个序列只会被列一次,不存在「换个苹果」的重复。
顺序与总数: 所有合法序列按字典序升序输出,最后再单独一行给出序列的个数。这两件事决定了实现上不能「先随便搜、最后排序」——枚举顺序选对,字典序是白送的。
每个人能拿多少:手里还剩多少就是枚举上界
按人的顺序往下分。处理到第 个人时,前面的 个人已经拿走了一部分,手上还剩 个苹果。第 个人能拿的个数就是 到 :不能超过剩下的总量,也没有任何其它上限(题面没有规定每人最多拿几个)。
于是搜索树的一层对应一个人,这一层的分支数由「剩下的苹果数」现场决定:
def dfs(i, rest):
for x in range(rest + 1): # 第 i 个人拿 x 个,最多拿光剩下的
cur[i] = x
dfs(i + 1, rest - x)cur 是当前的分配方案,rest - x 就是传给下一个人的剩余量。因为上界正是 rest,搜索过程不会出现 rest < 0 的分支,也就不需要额外的可行性检查。
最后一个人不再枚举,直接收下剩余的
如果最后一个人也照上面的写法枚举 到 ,那么只有 时总和才恰好等于 ,其余的 都会产出总和不足 的残缺序列。与其先生成再筛掉,不如让最后一层直接把剩余的苹果全部交给他:
if i == n - 1: # 最后一个人:剩下的全给他
cur[i] = rest
lines.append(" ".join(map(str, cur)))
return
for x in range(rest + 1):
cur[i] = x
dfs(i + 1, rest - x)这一步同时保证了「不重不漏」:前 个人的数一旦定下来,最后一个数被总和唯一确定,所以每个合法方案恰好被生成一次,既不会重复也不会遗漏。
时这条规则照样成立:rest 一路都是 ,每个人只能拿 ,整个搜索退化成一条链,输出唯一方案 0 0 … 0(示例 1 就是这一情形)。
字典序是枚举顺序白送的
字典序的比较规则是「先比第 个人,相同再比第 个人……」,而深度优先搜索恰好是这么展开的:先把第 个人的取值从 数到 ,在每一个取值内部,再让第 个人从 开始往上数。这与「按字典序逐位展开」逐字对应,所以收集到的方案列表不需要再排序。
把内层循环反过来写(range(rest, -1, -1))也能得到全部方案,但顺序会变成字典序的逆序,那就必须再排一次序才能满足题面。
数据范围给出的信号:答案规模本身就是枚举量
、 这组数字不是随手写的。把 个相同的苹果分给 个不同的人,方案数是隔板法的 ,最大的一组是 :
也就是说最多只有不到四千个方案要输出。DFS 的每一片叶子正好对应一个方案,枚举量就是输出规模本身,没有任何浪费。
反过来看另一条路——把 个位置各自从 枚举到 ,再筛掉和不等于 的:最大数据下有 个组合,比真正要输出的方案多两个数量级,而且其中绝大多数都要被丢弃。数据范围把这两条路分得很清楚。
用隔板法给总数做一次独立校验
隔板法给的公式可以直接拿来核对程序: 时 , 时 。本文的 run_tests() 里就用 math.comb(15+5-1, 5-1) 与程序输出的最后一行对照——这类「组合公式 vs 枚举结果」的互证,比只对一组样例更能说明搜索没有漏掉分支。
实现落点
dfs(i, rest):i是当前处理到第几个人( 起),rest是还没分出去的苹果数;cur[i] = x之后再递归,回溯时不需要清空——下一次循环会把它覆盖掉;lines先把每一行攒起来,最后用一次sys.stdout.write写出,避免方案多时反复调用print;- 收尾的
lines.append(str(len(lines)))读的是加入计数行之前的长度,正好是方案数。
完整代码实现
"""
P5518. 分苹果方案 - DFS 按人枚举 + 字典序输出
m 个完全相同的苹果分给 n 个互不相同的人,每人可以拿 0 到 m 个,
总和恰好为 m。输出全部方案(每行 n 个数,按字典序升序),
最后单独一行输出方案总数。
输入格式:
- 一行两个整数 m、n(m <= 15,n <= 5)。
输出格式:
- 每个方案一行:第 1 个人到第 n 个人分到的个数,空格分隔;
- 全部方案之后单独一行输出方案总数。
核心思路:
按人的顺序做深度优先搜索。处理到第 i 个人、手里还剩 rest 个苹果时,
枚举他拿 x = 0..rest,把 x 记进当前方案,带着 rest - x 进入下一个人。
最后一个人不再枚举:剩下的全部归他,否则总和不足 m 的残缺方案会混进来。
x 从小到大枚举,加上人序固定,输出的顺序天然就是字典序。
时间复杂度:O(n * C(m+n-1, n-1)),m=15、n=5 时最多 3876 个方案
空间复杂度:O(n)(递归栈与当前方案,不含输出缓冲)
"""
# https://codefun2000.com/p/P5518
import sys
# @sample-start
"""
样例输入 1:
0 2
样例输出 1:
0 0
1
"""
# @sample-end
# @sample-start
"""
样例输入 2:
2 1
样例输出 2:
2
1
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
m, n = int(data[0]), int(data[1])
cur = [0] * n # 当前方案:cur[i] 是第 i+1 个人拿到的个数
lines = []
def dfs(i, rest):
"""给第 i 个人(0 起)分苹果,手上还剩 rest 个。"""
if i == n - 1: # 最后一个人:剩下的全给他
cur[i] = rest
lines.append(" ".join(map(str, cur)))
return
for x in range(rest + 1): # 从小到大枚举,保证字典序升序
cur[i] = x
dfs(i + 1, rest - x)
dfs(0, m)
lines.append(str(len(lines))) # 最后一行是方案总数
sys.stdout.write("\n".join(lines) + "\n")
def run_tests():
"""运行嵌入的示例与边界用例,方便本地自测。"""
import io
from math import comb
cases = [
# 示例 1:0 个苹果分给 2 个人,只有 0 0 一种分法
("0 2\n", "0 0\n1"),
# 示例 2:只有 1 个人,方案唯一
("2 1\n", "2\n1"),
# 4 个苹果分给 2 个人,5 种分法
("4 2\n", "0 4\n1 3\n2 2\n3 1\n4 0\n5"),
# 1 个苹果分给 3 个人:3 种
("1 3\n", "0 0 1\n0 1 0\n1 0 0\n3"),
# 最大规模:m=15、n=5,方案数应为 C(19,4)=3876
("15 5\n", None),
]
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
if expected is None:
got = int(output.splitlines()[-1])
expect = comb(15 + 5 - 1, 5 - 1)
status = "✓" if got == expect else "✗"
print(f"用例 {i}: 方案数 期望={expect}, 实际={got} {status}")
continue
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:,
,最后一个人是下标 。dfs(0, 0) 进来时 不是最后一个人,于是枚举第 个人能拿的数:rest = 0,range(rest + 1) 里只有 一个分支。
| 调用 | 判定 | 动作 |
|---|---|---|
dfs(0, 0) | 不是最后一个人 | 枚举 ,cur[0]=0 |
dfs(1, 0) | 就是最后一个人 | cur[1]=0,攒下一行 0 0 |
一片叶子对应一个方案,所以方案数 ,计数行输出 1。用隔板法核对:,一致。
示例 2:,
时,i == n - 1 在第一次调用就成立(),于是直接执行 cur[0] = 2 并输出方案。没有第二层,也就没有分支:
| 调用 | 判定 | 动作 |
|---|---|---|
dfs(0, 2) | 就是最后一个人 | cur[0]=2,输出 2 |
方案数 ,计数行输出 1。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举 元组再筛掉和不等于 的 | 时 个组合,绝大多数要丢弃 | ||
| 按人 DFS,最后一层直接收尾(最优) | 每片叶子就是一个方案,最多 个, 是输出一个方案的成本 |
空间里的 指递归深度与 cur 的长度;lines 里攒着全部输出行,属于输出本身的开销。
易错点总结
1. 最后一层也照常枚举
把 if i == n - 1: 那一小段整体删掉、让最后一层继续走 for x in range(rest + 1),程序仍然跑得完,但会输出大量总和不足 的行。示例 1 的 0 2 碰巧看不出差别(只有 0 0 一种),换成 4 2 就会从 5 行方案变成 15 行,0 3、0 2、1 2 这类和小于 4 的组合全都混进来,计数行也跟着变成 15。
2. 枚举方向写成从大到小
把内层循环写成 for x in range(rest, -1, -1),数字一个不差,顺序却整个反过来。用 4 2 试,输出会是 4 0 / 3 1 / 2 2 / 1 3 / 0 4,与题面要求的字典序升序正好相反。