烤鸡 - 题目列表

题意

有 10 种配料，每种配料可以放 1,2,3 克。给定总美味程度 n，输出所有总和等于 n 的方案，按字典序排列。

思路

每个位置都有 1,2,3 三种选择，一共是：

text

13^10 = 59049

种方案，可以直接枚举。

Python 的 itertools.product(range(1, 4), repeat=10) 正好表示“10 个位置，每个位置从 1 到 3 中选一个”。product 产生的顺序就是字典序，因此筛选后直接输出即可。

Python 知识

product(range(1, 4), repeat=10) 可以代替 10 层循环。
sum(plan) 直接计算一个方案的总质量。
print(*plan) 把元组拆开，用空格分隔输出。
这里需要先保存全部合法方案，因为第一行要输出方案总数。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/itertools_recipes.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13from itertools import product

n = int(input())

plans = [
    plan
    for plan in product(range(1, 4), repeat=10)
    if sum(plan) == n
]

print(len(plans))
for plan in plans:
    print(*plan)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n, cnt;
int choose[11];          // choose[1..10] 每种配料的选择
int ans[60000][11];       // 保存所有方案,最多 3^10=59049

void dfs(int dep) {
    if (dep == 11) {
        int sum = 0;
        for (int i = 1; i <= 10; i++) sum += choose[i];
        if (sum == n) {
            cnt++;
            for (int i = 1; i <= 10; i++) ans[cnt][i] = choose[i];
        }
        return;
    }
    for (int i = 1; i <= 3; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    cin >> n;
    dfs(1);
    cout << cnt << endl;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= 10; j++) {
            cout << ans[i][j];
            if (j < 10) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

复杂度

总共枚举 $3^{10}$ 个方案。每个方案求和需要 $O(10)$ ，所以时间复杂度为 $O(10 \cdot 3^{10})$ 。空间复杂度为合法方案数量。

总结

当每个位置都有固定候选值时，product 是非常适合 Python 初学者模仿的枚举工具。

烤鸡

目录

题意

思路

Python 知识

代码

复杂度

总结