【GESP】C++三级、四级练习 luogu-P2089 烤鸡

GESP C++ 三级、四级经典练习题，考察多重循环枚举、递归回溯搜索（DFS）以及剪枝优化。题目要求找出 10 种配料（每种 1~3 克）使其质量之和恰好等于目标美味度 $n$ 的所有可能方案，并按字典序输出。本题规模适中（$3^{10} = 59049$ 种状态），既是初学者练习多层嵌套循环的绝佳载体，也是迈入递归回溯、状态树搜索和可行性剪枝大门的“新手村第一题”。题目难度⭐⭐☆☆☆，洛谷难度等级入门 / 普及−。

luogu-P2089 烤鸡

题目要求

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 $n$ ，请输出这 $10$ 种配料的所有搭配方案。

输入格式

一个正整数 $n$，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束，$10$ 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 $0$。

输入输出样例 #1

输入 #1

11

输出 #1

10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1

说明/提示

对于 $100\%$ 的数据，$n \leq 10000$。

---

题目分析

这道题目是一道非常经典的组合方案枚举与回溯搜索问题。我们需要为 10 种配料确定具体质量（每种质量只能为 1、2 或 3 克），要求 10 种配料的质量总和等于给定的美味程度 $n$。

1. 问题数学特征与极值特判（$\mathcal{O}(1)$ 快速过滤）

我们先从数学极值的角度分析本题的取值范围：

• 共有 10 种不同的配料；
• 每种配料放 $1 \sim 3$ 克；
• 最小可能总和：所有配料都放 1 克，总质量为 $10 \times 1 = 10$ 克；
• 最大可能总和：所有配料都放 3 克，总质量为 $10 \times 3 = 30$ 克。

因此，能够凑出的美味程度 $n$ 的取值区间严格限制在 $[10, 30]$ 内：

• 若 $n < 10$ 或 $n > 30$，无论怎样调配都绝对不可能凑出美味程度 $n$；
• 此时方案数必然为 $0$，根据题意直接输出一个 0 即可结束程序。

题目数据范围给到 $n \le 10000$，加入此特判后，绝大多数无效输入（例如 $n = 5$ 或 $n = 100$ 等）都可以在 $\mathcal{O}(1)$ 时间内瞬间完成判断，无需进行任何搜索或循环。

---

2. 搜索状态空间规模分析

若 $n \in [10, 30]$，我们需要列举出所有可行的搭配。

• 10 种配料，每种配料有 3 种选择（1、2、3 克）；
• 整个搜索空间构造成一棵深度为 10 的三叉树，所有可能的分配方案总数为： \(3^{10} = 59049 \approx 5.9 \times 10^4\)
• 在现代计算机中，C++ 程序 1 秒大约可执行 $10^8$ 次基础操作。$5.9 \times 10^4$ 次遍历耗时通常在 5 毫秒以内，因此即使不做任何剪枝的完全暴力枚举，也能在时限内轻松通过。
• 合法方案的最大数量： 根据组合数学与生成函数对称性，当 $n = 20$ 时，方案总数达到峰值 8953 种。存放这 8953 个方案仅需几十 KB 内存，我们完全可以将所有合法方案保存在内存中统一处理。

---

3. 字典序输出的天然满足

题目要求输出的方案“按字典序排列”。

• 字典序规则：对于两个长度为 10 的方案序列 $A = (a_1, a_2, \dots, a_{10})$ 和 $B = (b_1, b_2, \dots, b_{10})$，如果在第一个数值不同的位置 $k$ 上有 $a_k < b_k$，则方案 $A$ 排在方案 $B$ 前面。
• 天然保序：
  • 如果采用循环枚举，外层循环代表第 1 种配料（取值 $1 \to 3$），最内层代表第 10 种配料（取值 $1 \to 3$）；
  • 如果采用递归搜索，每一层递归分支依次尝试 $1 \to 2 \to 3$。

无论是多重循环还是深度优先搜索，只要按照从前往后、从小到大的顺序枚举，遍历生成方案的先后次序与字典序完全一致，不需要使用任何额外的排序操作！

---

4. 先输出总数后输出方案的处理策略

题目要求第一行输出“方案总数”，接下来才输出具体方案。由于我们在枚举初期无法直接得知最终满足条件的方案数，通常有两种处理方式：

1. 方案暂存法（推荐）： 使用动态数组 std::vector<std::vector<int>> 或者全局二维数组 int ans[10000][10]。枚举过程中只要发现和为 $n$ 的合法方案，就将其存入数组中。遍历结束后，方案总数即为数组长度，先输出总数，再逐行输出各个方案。
2. 两遍搜索法： 第一遍完整遍历只统计数量并输出；第二遍完整遍历按相同顺序打印方案。本题规模极小，两遍遍历耗时依然低于 10ms，但代码较为冗长，不如暂存法直观。

---

5. 两种核心算法剖析

思路一：十重嵌套循环枚举（适合 GESP 三级）

这是最朴素、最容易理解的直观解法：

• 嵌套书写 10 个 for 循环，循环变量分别表示 10 种配料的质量；
• 每个循环变量从 1 递增至 3；
• 在最内层循环中判断 10 个变量之和是否等于 $n$；
• 若相等，则记录或存入方案数组中。

优缺点分析：

• 优点：无需递归函数调用开销，对初学者而言没有调用栈、回溯等思维负担；
• 缺点：代码层级深（10 层缩进），可扩展性较弱（如果题目改为 $M$ 种配料，循环嵌套则无法动态书写）。

思路二：深度优先搜索（DFS）与回溯法（适合 GESP 四级）

深度优先搜索（DFS）是解决排列、组合与枚举类问题的标准通用模板：

• 状态设计：void dfs(int step, int current_sum)
  • step：当前正在决策第几种配料（$0 \sim 9$）；
  • current_sum：当前已经放置的配料质量总和。
• 递归终止条件：
  • 当 step == 10 时，10 种配料已全部决策完毕；
  • 检查 current_sum == n 是否成立，若成立则将当前路径存入答案数组，随后 return 回溯。
• 状态转移与回溯恢复：
  • 循环枚举当前配料可选质量 $w \in [1, 3]$；
  • 将 $w$ 加入路径中；
  • 递归调用 dfs(step + 1, current_sum + w) 进入下一层；
  • 递归返回后，将 $w$ 从路径中移除（回溯，恢复现场）。

思路三：DFS 可行性剪枝（优化进阶）

在搜索过程中，并不是所有分支都有必要走到底。若中途就能断定当前分支不可能凑出目标和 $n$，应立即返回以节省时间：

• 设当前已选好 step 种配料，剩余 $10 - step$ 种配料未选；
• 剩余配料的最小贡献：剩余配料全取最小值 1 克，最终总和至少为 $\text{current_sum} + (10 - step) \times 1$；
• 剩余配料的最大贡献：剩余配料全取最大值 3 克，最终总和至多为 $\text{current_sum} + (10 - step) \times 3$；
• 剪枝条件： \(\text{current\_sum} + (10 - step) \times 1 > n \quad \text{或} \quad \text{current\_sum} + (10 - step) \times 3 < n\) 一旦上述任一条件成立，表明无论后续怎么选，总和必然偏大或偏小，直接 return 即可！

加入可行性剪枝后，无效分支在浅层即被切除，搜索树节点访问量可从几万次缩减至几百次。

---

⚠️ 核心易错点分析

1. 忽略边界特判与数据范围

• 题目说明中 $n \le 10000$。
• 如果直接盲目运行未剪枝的算法，虽然也不会超时，但如果 $n$ 超出正常范围（例如 $n = 9$ 或 $n = 31$），务必保证程序正确输出 0 并且不产生多余的垃圾输出或越界访问。

2. 无解输出格式

• 题目规定：“如果没有符合要求的方法，就只要在第一行输出一个 0”。
• 切勿在输出 0 后输出空行或多余的空格字符。

3. 字典序枚举顺序错乱

• 在循环或递归分支扩展中，必须保证数值从小到大（1, 2, 3）枚举。
• 若误写为倒序枚举（如 3, 2, 1），虽然方案总数正确，但所有方案顺序将完全颠倒导致判定全 WA。

4. 回溯时的现场恢复

• 若使用 std::vector<int> path 记录路径，递归深入前执行 path.push_back(w)，递归返回后必须配对执行 path.pop_back()。
• 若使用全局数组 path[step] = w，由于每一层只使用对应下标 path[step]，返回后会被下一轮覆盖，但如果在全局变量中维护了累加和 sum，回溯时必须保证配对扣除 sum -= w。

---

示例代码

方法一：深度优先搜索（DFS）+ 可行性剪枝（推荐，GESP 四级标准写法）

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> path;              // 记录当前递归路径上的配料质量
vector<vector<int>> results;   // 暂存所有满足条件的搭配方案

// step: 当前正在决定第 step 种配料 (0 ~ 9)
// current_sum: 当前已放入配料的质量之和
void dfs(int step, int current_sum) {
    // 递归边界：10 种配料均已决策完毕
    if (step == 10) {
        if (current_sum == n) {
            results.push_back(path);
        }
        return;
    }

    // 可行性剪枝：
    // 剩余未决策的配料数为 10 - step
    // 即使剩余全部放最小值 1 克，或者全部放最大值 3 克
    int remaining = 10 - step;
    if (current_sum + remaining * 1 > n || current_sum + remaining * 3 < n) {
        return; // 无论后续怎么放都不可能达到目标 n，直接回溯
    }

    // 按升序 1 -> 2 -> 3 尝试每种可能的配料质量，保证字典序
    for (int weight = 1; weight <= 3; ++weight) {
        path.push_back(weight);               // 1. 做出选择
        dfs(step + 1, current_sum + weight);  // 2. 深入下一层
        path.pop_back();                      // 3. 撤销选择（恢复现场）
    }
}

int main() {
    // 提高输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) {
        return 0;
    }

    // 极值特判：10种配料最小和为10，最大和为30
    if (n < 10 || n > 30) {
        cout << 0 << "\n";
        return 0;
    }

    // 从第 0 种配料、当前总和为 0 开始深搜
    dfs(0, 0);

    // 第一行输出方案总数
    cout << results.size() << "\n";

    // 逐行输出每种搭配方案
    for (const auto& scheme : results) {
        for (int i = 0; i < 10; ++i) {
            cout << scheme[i] << (i == 9 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

---

方法二：十重循环暴力枚举（简单直观，GESP 三级必会解法）

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }

    // 边界特判
    if (n < 10 || n > 30) {
        cout << 0 << "\n";
        return 0;
    }

    // 暂存所有合法方案
    vector<vector<int>> results;

    // 10 重嵌套循环直接枚举每种配料的克数 (1 ~ 3)
    for (int a = 1; a <= 3; ++a) {
        for (int b = 1; b <= 3; ++b) {
            for (int c = 1; c <= 3; ++c) {
                for (int d = 1; d <= 3; ++d) {
                    for (int e = 1; e <= 3; ++e) {
                        for (int f = 1; f <= 3; ++f) {
                            for (int g = 1; g <= 3; ++g) {
                                for (int h = 1; h <= 3; ++h) {
                                    for (int i = 1; i <= 3; ++i) {
                                        for (int j = 1; j <= 3; ++j) {
                                            if (a + b + c + d + e + f + g + h + i + j == n) {
                                                results.push_back({a, b, c, d, e, f, g, h, i, j});
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // 输出方案总数
    cout << results.size() << "\n";

    // 逐行输出方案
    for (const auto& scheme : results) {
        for (int k = 0; k < 10; ++k) {
            cout << scheme[k] << (k == 9 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

---

方法三：基于定长数组的高效 DFS（无 STL 依赖，适合基础语法阶段）

#include <iostream>

using namespace std;

int n;
int path[10];           // 记录当前方案的10个配料值
int ans[10000][10];     // 二维数组存储所有方案（最大方案数小于9000）
int total_count = 0;    // 方案计数器

void dfs(int step, int current_sum) {
    if (step == 10) {
        if (current_sum == n) {
            for (int i = 0; i < 10; ++i) {
                ans[total_count][i] = path[i];
            }
            total_count++;
        }
        return;
    }

    // 可行性剪枝
    int rem = 10 - step;
    if (current_sum + rem * 1 > n || current_sum + rem * 3 < n) {
        return;
    }

    for (int w = 1; w <= 3; ++w) {
        path[step] = w; // 覆盖当前位置，无需显式 pop
        dfs(step + 1, current_sum + w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) {
        return 0;
    }

    if (n < 10 || n > 30) {
        cout << 0 << "\n";
        return 0;
    }

    dfs(0, 0);

    cout << total_count << "\n";
    for (int i = 0; i < total_count; ++i) {
        for (int j = 0; j < 10; ++j) {
            cout << ans[i][j] << (j == 9 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

---

复杂度对比与总结

实现方式	时间复杂度	空间复杂度	适用场景与优缺点
十重循环暴力枚举	$\mathcal{O}(3^{10}) \approx 5.9 \times 10^4$	$\mathcal{O}(K)$	简单直接，GESP 三级学生最易上手；但嵌套代码层级过深，缺乏灵活性
基础 DFS 回溯	$\mathcal{O}(3^{10}) \approx 5.9 \times 10^4$	$\mathcal{O}(D + K)$	GESP 四级核心模板，结构优雅，易于扩展到 $M$ 种配料或变长约束
DFS + 可行性剪枝	远小于 $\mathcal{O}(3^{10})$（节点数 $\le 1000$）	$\mathcal{O}(D + K)$	最推荐做法，运行时间 $< 2\text{ms}$，展示了算法竞赛中的核心剪枝思维

(注：$D = 10$ 为递归树深度，$K \le 8953$ 为存储合法方案的空间大小)

知识点拓展与思维升华：

1. 回溯法的本质：回溯法本质就是一棵树的深度优先遍历。编写回溯算法的三部曲是：
   • 终止条件：何时收集结果并退出当前分支；
   • 遍历候选集合：当前节点能做出哪些选择（本题中为 $1 \sim 3$ 克）；
   • 做选择与撤销选择：进入递归前更新状态，递归返回后恢复现场。
2. 上下界剪枝的威力：通过计算“剩余部分全取最值时的理论极限值”，判断当前状态是否可能达成目标。如果连最乐观的可能都无法达标，即可提前终结该分支，这一思想在数独求解、背包搜索及各种图论搜索中极为普遍。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号