P2386 放苹果

记录163#includebits/stdc.h // 引入万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间 int t,m,n; // 定义全局变量t(测试数据组数)、m(苹果数)、n(盘子数) int ans; // 定义全局变量ans用来记录当前测试数据的合法方案总数 // remain_apple: 当前还剩下多少个苹果没放 // remain_plate: 当前还剩下多少个盘子没放 // min_apple: 当前这个盘子至少要放多少个苹果保证非递减避免重复 void dfs(int remain_apple,int remain_plate,int min_apple){ // 如果只剩下最后1个盘子剩下的苹果全部放进去这算作一种合法方案 if(remain_plate1){ ans; // 方案数加1 return; // 结束当前递归分支 } // 枚举当前盘子放多少个苹果从min_apple开始枚举 // 剪枝因为后面还有remain_plate-1个盘子且每个至少放i个 // 所以当前最多只能放 remain_apple / remain_plate 个 for(int imin_apple;iremain_apple/remain_plate;i){ dfs(remain_apple-i,remain_plate-1,i); // 递归搜索下一个盘子传入减去i后的剩余苹果盘子数减1最小可选值更新为i } } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭cin与stdio的同步加快输入输出速度 cin.tie(0); // 解除cin与cout的绑定进一步加快IO效率 cint; // 输入测试数据的组数t while(t--){ // 循环t次处理每一组测试数据 cinmn; // 输入当前组的苹果数m和盘子数n ans0; // 每次测试数据开始前将方案数清零 dfs(m,n,0); // 调用dfs开始搜索初始剩余m个苹果需放n个盘子最小从0开始选允许空盘 coutans\n; // 输出当前测试数据的合法方案总数 } return 0; // 主函数正常结束返回0 }题目传送门https://www.luogu.com.cn/problem/P2386前言我是一名专注信奥赛GESP、CSP-J/S的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的组合数学与深度优先搜索DFS剪枝问题。问题转化非递减序列模型题目要求将 mm 个相同的苹果放入 n 个相同的盘子且允许空盘。因为盘子是相同的所以 (5,1,1) 和 (1,1,5) 被视为同一种方案。为了避免重复计数我们可以强制规定每个盘子放的苹果数量呈非递减顺序即前一个盘子放的苹果数 ≤≤ 后一个盘子放的苹果数。这样每一种合法的分配方案都唯一对应一个非递减序列。算法设计DFS 与剪枝优化我们可以使用 DFS 逐个盘子进行分配。在搜索过程中需要维护三个状态剩余苹果数、剩余盘子数、以及当前盘子至少需要放的苹果数即上一个盘子放的苹果数保证非递减。边界条件当剩余盘子数为 1 时说明前面的盘子都已经分配完毕剩下的苹果必须全部放入最后一个盘子。由于是非递减序列只要前面的分配合法最后一步必然合法直接方案数加 1 并返回。枚举与剪枝对于当前盘子枚举放入的苹果数 i 。下界是min_apple上界则是通过平均值剪枝得出的为了保证剩下的盘子也能满足非递减条件当前盘子最多只能放remain_apple / remain_plate个苹果。这极大地减少了搜索树的规模。代码分块详细解释1. 全局变量与函数签名定义#includebits/stdc.h using namespace std; int t, m, n; // 定义全局变量t(测试数据组数)、m(苹果数)、n(盘子数) int ans; // 定义全局变量ans用来记录当前测试数据的合法方案总数 // remain_apple: 当前还剩下多少个苹果没放 // remain_plate: 当前还剩下多少个盘子没放 // min_apple: 当前这个盘子至少要放多少个苹果保证非递减避免重复 void dfs(int remain_apple, int remain_plate, int min_apple){详细分析定义了三个全局变量用于主循环控制。dfs函数是核心搜索函数参数设计非常精妙min_apple参数完美地解决了“盘子相同导致方案重复”的问题它充当了当前枚举的下界强制后续的分配不会小于之前的分配。2. 核心逻辑边界处理与剪枝枚举// 如果只剩下最后1个盘子剩下的苹果全部放进去这算作一种合法方案 if(remain_plate 1){ ans; // 方案数加1 return; // 结束当前递归分支 } // 枚举当前盘子放多少个苹果从min_apple开始枚举 // 剪枝因为后面还有remain_plate-1个盘子且每个至少放i个 // 所以当前最多只能放 remain_apple / remain_plate 个 for(int i min_apple; i remain_apple / remain_plate; i){ dfs(remain_apple - i, remain_plate - 1, i); // 递归搜索下一个盘子 } }详细分析边界处理当remain_plate 1时意味着只剩下一个盘子此时无论剩下多少苹果都只能全放进去。由于我们一直在维护非递减序列只要前面的分配合法最后一步必然合法因此直接ans并返回。循环与剪枝for循环的下界是min_apple保证了非递减上界是remain_apple / remain_plate这是极其关键的平均值剪枝。假设还剩 10 个苹果和 4 个盘子当前盘子最多只能放 10/4210/42 个因为如果放 3 个剩下的 7 个苹果分给 3 个盘子平均值大于 2必然违反非递减规则。这个剪枝将时间复杂度大幅降低。3. 主函数多组数据测试与状态重置int main(){ ios::sync_with_stdio(false); cin.tie(0); cin t; while(t--){ cin m n; ans 0; // 每次测试数据开始前将方案数清零 dfs(m, n, 0); // 调用dfs开始搜索初始剩余m个苹果需放n个盘子最小从0开始选允许空盘 cout ans \n; } return 0; }详细分析主函数处理多组测试数据。每次调用dfs前必须将全局变量ans重置为 0。初始调用时min_apple传入 0完美契合了题目中“允许有的盘子空着不放”的条件。核心逻辑总结代码模块核心变量/操作精炼作用解决的痛点非递减约束min_apple参数传递记录上一个盘子放的苹果数作为当前枚举下界完美解决了“盘子相同导致 (5,1,1) 和 (1,1,5) 重复计数”的痛点边界快速返回if(remain_plate 1)仅剩一个盘子时直接累加方案数避免了无意义的深层递归提升了搜索效率平均值剪枝i remain_apple / remain_plate限制当前盘子能放苹果的最大值极大地缩减了搜索树的规模防止超时状态重置ans 0每组测试数据开始前清零计数器保证多组测试数据之间的独立性防止答案污染允许空盘初始调用dfs(m, n, 0)将初始最小苹果数设为 0满足了题目中“允许有的盘子空着不放”的特殊要求