P2089 烤鸡
题目背景
猪猪 Hanke 得到了一只鸡。
题目描述
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 \(10\) 种配料（芥末、孜然等），每种配料可以放 \(1\) 到 \(3\) 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 \(n\) ，请输出这 \(10\) 种配料的所有搭配方案。
输入格式
一个正整数 \(n\)，表示美味程度。
输出格式
第一行，方案总数。
第二行至结束，\(10\) 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 \(0\)。
输入输出样例 #1
输入 #1
输出 #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\)。
Tip
📌 题目分析
给定数据：
求出所有配料总和等于 n 的方案数，并按字典序输出所有方案。
👉 本质：
👉 类型：
Note
我的做法，我看童老师ppt上和我的思路差不多，但是语法细节上，童老师用了带参的宏定义，然后细节上童老师还用了更细化的剪枝
我的做法->最无脑的暴力
#include <iostream>
using namespace std;
int main() {
int n, a0, a1, a2, a3, a4, a5, a6, a7, a8, a9;
cin >> n;
//简单剪枝
if (n < 10 || n>30) {
cout << "不能合理分配";
}else{
for (int a0 = 1;a0 <= 3;a0++) {
for (int a1 = 1;a1 <= 3;a1++) {
for (int a2 = 1;a2 <= 3;a2++) {
for (int a3 = 1;a3 <= 3;a3++) {
for (int a4 = 1;a4 <= 3;a4++) {
for (int a5 = 1;a5 <= 3;a5++) {
for (int a6 = 1;a6 <= 3;a6++) {
for (int a7 = 1;a7 <= 3;a7++) {
for (int a8 = 1;a8 <= 3;a8++) {
for (int a9 = 1;a9 <= 3;a9++) {
if (a0 + a1 + a2 + a3 + a4 +
a5 + a6 + a7 + a8 + a9 == n) {
printf("%d %d %d %d %d %d %d %d %d %d\n"
, a0, a1, a2, a3, a4, a5, a6, a7, a8, a9);
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
🧠 解题思路
1️⃣ 为什么可以使用暴力搜索
这道题看起来 n 很大（10000），但实际上配料的限制非常严格：
一共 10 种配料，每种最多放 3 克。
这意味着所有的组合总数只有：
五万多次的计算对于 C++ 来说连 1 毫秒都用不到，所以直接暴力把所有情况试一遍是最优解。
2️⃣ 怎样保证字典序输出
字典序就是从小到大排序输出。 我们在进行暴力搜索（或者 DFS）的时候，只要规定每次尝试的顺序是先放 1 克，再放 2 克，最后放 3 克。 因为按固定顺序往下搜，天然找出来的方案就已经是完全符合字典序的了，不需要做任何额外的排序。
3️⃣ 怎样满足题目的输出格式
题目要求：
这就意味着我们不能边找边输出（因为你还没找完，不知道总数是多少）。
我们需要一个大容器（比如二维数组或者 vector）把所有合法的方案先存起来。等全部搜完后，先输出容器里存了多少个方案，然后再把容器里的方案挨个打印出来。
4️⃣ 特殊情况（剪枝）
10 种配料，每种最少 1 克，最多 3 克。 所以总和必定在：
如果输入的 n 小于 10 或者大于 30，直接输出 0 即可，连搜索都可以省了。
💻 C++代码
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> ans; // 用二维 vector 保存所有合法的方案
vector<int> path; // 保存当前正在尝试的搭配方案
// step: 当前正在选第几种配料 (1~10)
// sum: 当前配料的总和
void dfs(int step, int sum) {
// 简单剪枝：如果当前总和已经超过了要求的 n，后面的都不用试了
if (sum > n) return;
// 边界条件：当 10 种配料都选完了（准备选第 11 种时）
if (step == 11) {
if (sum == n) {
ans.push_back(path); // 找到一个合法方案，存下来
}
return;
}
// 暴力尝试当前配料放 1克、2克、3克
for (int i = 1; i <= 3; i++) {
path.push_back(i); // 把 i 克加进去
dfs(step + 1, sum + i); // 继续搜下一种配料
path.pop_back(); // 回溯：把刚刚加的拿出来，换下一种克数试
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// 只有在合理范围内才去搜
if (n >= 10 && n <= 30) {
dfs(1, 0);
}
// 1. 先输出总方案数（如果没有就是 0）
cout << ans.size() << "\n";
// 2. 挨个输出存下来的合法方案
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < 10; j++) {
cout << ans[i][j] << " ";
}
cout << "\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 边找边输出导致全错
很多人在 dfs 到了目标后直接 cout << path[i]。
这会导致你的方案直接打在屏幕上，而题目要求第一行必须是总数，输出顺序错了会直接判 0 分（WA）。必须用数组存起来。
❌ 2. 递归深度搞错
配料有 10 种。如果你的层数是从 1 开始算，当 step == 11 时才说明前面的 1 到 10 种都已经选定了。
不能写成 step == 10 时就结算，那样会漏掉第 10 种配料的选择。
❌ 3. 忘记回溯
这是初学者写 DFS 最容易犯的错误：
如果不把上一次尝试的克数拿出来（退栈），你的数组里就会不停地堆积无用的克数，导致后续验证全部失效。
🚀 一句话总结
🔥 补充
关于终极暴力： 其实这道题如果你完全不会写 DFS 递归，写一个 10 层的 for 循环嵌套 也是绝对满分通过的（而且速度同样极快）。
就像这样：
虽然这种代码看起来像“大炮打蚊子”，但它最纯粹地体现了“暴力枚举”的本质。在比赛中如果时间紧迫且层数固定，十层循环也是一种“实用且稳妥”的策略！