1. 从“烤鸡”到“枚举”一道经典算法题的深度剖析看到“洛谷P2089 烤鸡”这个标题你可能会一愣以为是什么美食攻略或者生活分享。但在算法竞赛和编程学习的圈子里这却是一道大名鼎鼎的入门级“暴力枚举”练习题。它的核心是要求你用程序模拟一位挑剔的“吃货”为一只烤鸡搭配10种配料每种配料可以放1到3克最终使得所有配料的总重量恰好等于一个给定的美味值n。题目看似简单却像一块试金石能清晰地检验出一个编程新手对循环控制、条件判断、结果存储和输出格式化这些基础概念的掌握程度。对于正在学习C、准备参加信息学奥赛NOIP/CSP或者单纯想夯实编程基础的朋友来说这道题的价值远超其表面。今天我就结合自己带学生刷题的经验用两种最典型的解法——深度优先搜索DFS和多重循环枚举带你彻底吃透这道题并分享那些只有踩过坑才知道的调试技巧和优化思路。2. 题意拆解与核心逻辑建模2.1 问题重述把生活问题转化为数学模型题目描述可以抽象为以下数学模型 我们有10个变量分别代表10种配料的质量记为 ( a_1, a_2, ..., a_{10} )。 每个变量的取值范围是固定的( a_i \in {1, 2, 3} )。 给定一个总和 ( n ) 题目中的“美味值”要求找出所有满足以下等式的变量赋值组合 [ \sum_{i1}^{10} a_i n ] 并且我们需要按字典序输出所有可能的组合。如果没有任何组合满足条件则输出0。注意这里的“字典序”输出是很多新手容易忽略的关键点。它意味着在输出时组合需要按照 ( a_1, a_2, ..., a_{10} ) 这个顺序从小到大排列。例如组合1 1 1 1 1 1 1 1 1 4假设4合法会排在1 1 1 1 1 1 1 1 2 3之前因为从左到右比较第一个不同的位置是第9位1 2。我们采用的两种方法其搜索或枚举的顺序天然保证了结果的字典序这是设计算法时需要提前考虑的。2.2 算法选择背后的“为什么”为什么这道题通常用DFS或多重循环来解决这源于问题本身的两个特性解空间有限且离散每种配料只有3种选择10种配料的所有可能组合是 ( 3^{10} 59049 ) 种。这个数量对于现代计算机来说完全可以在极短时间内完成穷举。因此“暴力”搜索是可行且直接的。需要遍历所有可能性题目要求列出“所有”符合要求的方案而不是仅仅判断是否存在或找出一个。这直接指向了需要遍历整个解空间的算法。深度优先搜索DFS是一种递归的遍历策略它沿着每一个分支深入到底再回溯尝试其他分支。在这道题里每一种配料的选择就是一个分支。DFS的代码结构清晰易于扩展到配料种类可变或约束更复杂的情况比如每种配料的克数范围不同。多重循环枚举则是更“硬核”的暴力直接写10层for循环。它的思路直观执行效率在固定规模下可能略高于DFS因为省去了递归调用的开销但代码冗长且一旦配料种类改变就需要重写循环层数扩展性差。选择哪种方法取决于你的目的。如果是学习通用的搜索框架和递归思想DFS是必修课。如果追求在固定题目下的极致简洁某些竞赛环境或理解最基础的枚举那么多重循环值得一试。接下来我们将深入这两种方法的实现细节。3. 方法一深度优先搜索DFS实现详解DFS是解决这类组合问题的“标准武器”。其核心思想是尝试与回溯。3.1 DFS算法框架与递归树构建我们可以把寻找10种配料组合的过程想象成在一棵树上进行深度遍历。树的每一层对应一种配料的选择第1层是 (a_1)第2层是 (a_2)以此类推。树的每个节点有3个子节点分别代表选择1克、2克或3克。一条从根到叶子的路径就对应了一种完整的配料方案。我们的任务就是遍历所有从根到叶子的路径并检查路径上所有节点的值配料克数之和是否等于n。递归函数的参数设计是关键int step当前正在决定第几种配料从1到10。int current_sum当前已经累加的配料总重量。vectorint recipe用于存储当前路径即当前尝试的配方组合的数组。递归的流程如下递归边界终止条件当step 10时说明10种配料都已决定完毕。此时检查current_sum n。如果相等则当前recipe是一个合法解将其保存。递归体选择与探索在当前step我们有三种选择加1、加2、加3。依次尝试每一种选择 a. 将选择的值加入recipe。 b. 更新current_sum。 c. 递归调用函数处理下一步 (step1)。 d.回溯在递归返回后需要将recipe中当前步的选择移除或覆盖并恢复current_sum以便尝试下一个选择。这是DFS的精髓。3.2 完整C代码实现与逐行注释#include iostream #include vector using namespace std; int n; // 美味值即目标总重量 int totalSolutions 0; // 方案总数 vectorvectorint allRecipes; // 存储所有合法的配方方案 // DFS递归函数 void dfs(int step, int currentSum, vectorint currentRecipe) { // 边界条件已经决策完10种配料 if (step 10) { // 如果当前总重量恰好等于目标n则找到一个合法方案 if (currentSum n) { totalSolutions; // 方案数加1 allRecipes.push_back(currentRecipe); // 存储当前方案 } return; // 无论是否合法都返回上一层 } // 递归体尝试为第step种配料添加1、2、3克 // 注意这里有一个重要的剪枝优化条件我们稍后讨论 for (int gram 1; gram 3; gram) { // 尝试加入当前克数 currentRecipe.push_back(gram); // 递归进入下一步决策 dfs(step 1, currentSum gram, currentRecipe); // 回溯撤销当前选择尝试下一个gram值 currentRecipe.pop_back(); } } int main() { cin n; // 输入合法性快速判断重要优化 // 因为每种配料至少1克所以10种配料至少重10克。 // 每种配料至多3克所以10种配料至多重30克。 // 如果n不在[10, 30]区间直接输出0并结束。 if (n 10 || n 30) { cout 0 endl; return 0; } vectorint recipe; // 用于在DFS中传递当前配方 dfs(1, 0, recipe); // 从第1种配料开始当前总重为0 // 输出结果 cout totalSolutions endl; for (const auto r : allRecipes) { for (int i 0; i 10; i) { cout r[i] ; } cout endl; } return 0; }3.3 DFS实战中的关键技巧与剪枝优化上面的代码是DFS的基础框架但直接提交到洛谷可能会因为方案数过多最多有3^10种递归调用而导致在极端情况下递归栈开销或时间不那么美观。虽然本题数据规模完全可以承受但引入“剪枝”优化是必须养成的习惯。剪枝Pruning就是在搜索过程中提前判断出某些分支不可能产生合法解从而不再深入探索直接返回。这能显著减少不必要的计算。在这道题中一个非常有效的剪枝是在递归过程中如果当前累计重量已经超过目标n或者即使后面所有配料都按最小重量1克加也无法达到n那么这条路径就没必要继续了。我们可以在递归函数的开头加入这个判断void dfs(int step, int currentSum, vectorint currentRecipe) { // 剪枝1当前和已超过目标不可能成功 if (currentSum n) return; // 剪枝2即使后面所有配料都放1克最终和也小于目标也不可能成功 // 剩余配料种类数10 - step 1 // 最小可能增加重量(10 - step 1) * 1 if (currentSum (10 - step 1) * 1 n) return; // 这个条件实际上被第一个条件覆盖了更关键的是下面这个 // 剪枝3即使后面所有配料都放3克最终和也小于目标也不可能成功 if (currentSum (10 - step 1) * 3 n) return; // ... 原来的边界条件和递归体 ... }实际上最常用的是“可行性剪枝”if (currentSum n) return;。加上它之后程序性能会有可观的提升。实操心得在写DFS时recipe这个存储当前路径的容器一定要用引用传递vectorint。如果使用值传递每次递归调用都会完整地复制整个数组当递归深度达到10层时会产生巨大的内存和时间开销。使用引用传递后我们只需要在递归返回前做好“回溯”pop_back就能保证不同路径间的选择互不干扰。4. 方法二多重循环枚举实现详解如果说DFS是精巧的“手术刀”那么多重循环就是一把“重剑”。它的思路无比直接既然只有10种配料每种有3种可能那我就用10层for循环遍历所有 (3^{10}) 种组合。4.1 十重循环的构建逻辑与可行性分析为什么十重循环是可行的我们来算一笔账最内层循环体的执行次数 (3^{10} 59049)。对于现代CPU以每秒数十亿次运算计执行几万次简单的加法、比较判断耗时仅在毫秒级完全可接受。循环的设计如下每一层循环控制一种配料的质量gram_i其取值从1到3。在最内层循环即所有配料的值都确定后计算总重量sum gram1 gram2 ... gram10。如果sum n则记录该组合。4.2 完整C代码实现与逐行注释#include iostream #include vector using namespace std; int main() { int n; cin n; // 同样进行输入范围的快速判断 if (n 10 || n 30) { cout 0 endl; return 0; } vectorvectorint validRecipes; // 存储所有有效配方 int count 0; // 有效方案计数器 // 十重循环开始 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) for (int a10 1; a10 3; a10) { // 在最内层循环计算总和 int totalWeight a1 a2 a3 a4 a5 a6 a7 a8 a9 a10; if (totalWeight n) { count; // 将当前组合存入向量 validRecipes.push_back({a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}); } } // 输出结果 cout count endl; for (const auto recipe : validRecipes) { for (int gram : recipe) { cout gram ; } cout endl; } return 0; }4.3 循环枚举的优缺点与适用场景分析优点直观易懂逻辑直白非常适合初学者理解“穷举”的概念。执行高效在循环层数固定且不多的情况下避免了递归的函数调用开销通常运行速度略快于DFS。代码顺序即字典序循环从a1到a10依次从小到大遍历自然保证了结果输出的字典序无需额外排序。缺点代码冗余扩展性为零如果题目改成“20种配料”你就得写20层循环代码几乎无法维护。而DFS只需改变递归边界条件step 20即可。难以优化在循环内部进行复杂的剪枝不如在递归中方便。例如如果想实现“当前部分和超过n就跳过剩余循环”在多重循环中实现起来非常别扭可能需要配合goto或额外标志位破坏代码结构。可读性差十层缩进的代码看起来并不美观。适用场景仅适用于规模固定且非常小的穷举问题。在算法竞赛中它更像一种“特化”的解题技巧用于在时间紧迫时快速写出小规模枚举的代码。但在学习阶段掌握DFS这类通用范式更为重要。注意事项在多重循环中validRecipes.push_back({a1, a2, ..., a10})这行代码使用了C11的初始化列表来快速构建一个向量并存入。这是非常简洁的写法。如果你使用的编译器较老可能需要先创建一个临时vectorint然后依次push_back各个变量。5. 性能对比、存储方案与输出陷阱5.1 两种方法的时间与空间复杂度分析时间复杂度两种方法在最坏情况下都需要遍历所有 (3^{10} 59049) 种状态。因此它们的时间复杂度都是O(3^m)其中 m 是配料种类数本题为10。加上剪枝的DFS在实际运行中会提前终止很多分支平均性能优于无剪枝的循环枚举。空间复杂度DFS主要消耗在递归调用栈深度最大为10和存储所有解的容器上。存储解的容器是主要的空间占用最多需要存储所有合法方案。方案数量的上限是一个组合数学问题在n20时最多但远小于59049。递归栈空间可以忽略不计。多重循环空间消耗主要也在存储解的容器上与DFS相同。所以在本题限制下两种方法的实际运行时间和内存占用差异微乎其微选择哪种主要取决于你的编码习惯和对算法思想的练习目的。5.2 结果存储方案的选择vector vs. 直接输出在上面的代码中我们都选择先将所有合法方案存入一个vectorvectorint最后统一输出。这是最清晰的思路。但它有一个潜在问题如果合法方案非常多虽然本题不会可能会占用较多内存。另一种思路是找到一个方案就立即输出一个方案。这在DFS中很容易实现在递归边界条件里一旦发现currentSum n就直接输出当前的currentRecipe数组。这样可以节省存储所有方案的内存。但是这里有一个洛谷判题系统的大坑题目要求先输出方案总数再输出所有方案。如果你找到一个就输出一个那么第一行输出的就不是总数而是第一个方案的详情这会导致输出格式错误判为“Wrong Answer”。所以我们必须先知道总数才能输出。这就要求要么先存储再输出要么用其他方法先计数。一个常见的技巧是先运行一次DFS只计数得到总数并输出然后再运行一次DFS在找到合法方案时直接输出方案内容。这样避免了存储所有方案但付出了运行两次的代价。对于本题存储开销完全可以接受因此第一种先存后输出的方法更简单可靠。5.3 输出格式的“坑”与边界条件处理末尾空格与换行洛谷的判题机通常对输出格式中的空格和换行比较敏感。我们的代码在输出每个配方时最后一个数字后面也跟了一个空格然后才换行。大多数在线判题系统包括洛谷会忽略行末空格所以这样写是安全的。但更严谨的做法是for (int i 0; i 10; i) { cout r[i]; if (i 9) cout ; // 最后一个数字后不加空格 } cout endl;无解情况题目明确要求如果无解只输出一个0。我们通过预先判断n是否在 [10, 30] 区间可以提前处理大部分无解情况。但即使n在此区间内也可能无解例如n29因为最大是30但10种配料都是3克总和为30要得到29必须有一种是2克其余是3克这是可能的但n11呢最小是10要得到11必须有一种是2克其余是1克也是可能的。实际上对于10n30本题都有解。我们的DFS或循环逻辑自然能处理如果count为0就只输出一个0。输入范围检查这是一个非常重要的编程习惯。在cin n后立即判断if(n10 || n30)如果为真直接输出0并返回。这避免了进行无意义的巨额枚举是有效的优化也体现了程序的健壮性。6. 从“烤鸡”延伸枚举与搜索算法的核心思维通过“烤鸡”这道题我们深入实践了两种最基本的算法思想枚举与搜索DFS。它们看似简单却是解决无数复杂问题的基石。6.1 如何识别这类“枚举/搜索”题当你看到题目具有以下特征时就要考虑枚举或搜索了问题涉及在一个有限的、离散的候选集合中做出选择或排列。需要找出所有满足特定条件的组合而不是单个解。数据规模允许进行穷举通常候选状态数在 (10^6) 到 (10^7) 量级以下现代计算机1秒内可完成。6.2 DFS模板的通用化与变形本次使用的DFS是一个标准的“组合型”DFS模板它可以很容易地改编以解决其他问题排列问题如洛谷P1706 全排列问题。需要记录哪些数字已被使用过递归时选择未使用的数字。子集问题如从n个数中选取若干个数求和。每一步的决策是“选”或“不选”当前数。棋盘类问题如八皇后、迷宫路径。递归的每一步代表在棋盘上做一个放置或移动决策。模板变形的关键点通常在于递归参数除了当前步骤step可能还需要传递棋盘状态、访问标记数组等。递归边界可能是步数用完、到达终点、或条件满足。选择列表在当前步骤有哪些可选项如1/2/3克、上下左右四个方向、未使用的数字等。剪枝策略如何提前排除无效路径这是优化搜索效率的灵魂。6.3 调试技巧与常见错误排查在实现DFS时新手最容易犯的几个错误忘记回溯在递归调用返回后没有恢复现场currentRecipe.pop_back()。这会导致不同路径的状态污染结果完全错误。调试方法在递归函数入口和出口打印step和currentRecipe观察路径是否正确回溯。递归边界条件错误例如把if(step 10)写成if(step 10)后者会在决定完第10种配料后直接返回而不会执行到检查总和的逻辑。调试方法用一个小数据如n10只有1种解1 1 1...测试单步跟踪递归过程。全局变量与局部变量混淆例如在DFS函数内定义了局部变量vectorint currentRecipe但递归调用时又希望修改外层的容器。必须使用引用传递或全局变量。编译器的警告通常是你的好朋友注意查看。输出格式错误如前所述先输出了方案内容才输出总数。调试方法自己设计几个极端测试用例如n10 n30 n15运行肉眼检查输出格式是否与题目示例完全一致。对于多重循环方法常见错误是循环变量名写错例如第九层循环误写成for(int a9...但内层计算总和时用了a10或者括号匹配错误导致循环层次混乱。建议写的时候每一层循环后面加一个注释并保持良好的缩进。6.4 性能优化进阶思考虽然本题无需优化也能过但思考优化是算法学习的乐趣所在更早的剪枝我们只在递归入口处做了剪枝。其实可以在for循环内部做如果currentSum gram n那么即使后面的配料都放1克也会超所以可以直接break出当前循环因为gram是从小到大尝试的后面的gram更大更不可能。对称性剪枝如果题目不要求按顺序输出本题要求且认为1 2 3和3 2 1是相同的组合那么可以规定一个非递减的顺序进行搜索能减少大量重复状态。但这属于更高级的技巧。最后这道“烤鸡”题就像编程学习路上的一道经典开胃菜。它味道简单但营养丰富涵盖了从问题建模、算法选择、代码实现到调试优化的完整流程。希望这篇超详细的解析能帮你不仅“做出”这道题更能“吃透”它背后的思想。编程的学习正是在这样一道道题目的反复咀嚼和实践中逐渐积累起扎实的功力和清晰的思路。当你再遇到更复杂的搜索问题时不妨回想一下这只“烤鸡”想想它的变量、它的循环、它的递归树或许就能找到解题的灵感。