P1036 [NOIP 2002 普及组] 选数

记录140#includebits/stdc.h using namespace std; const int N25; // 定义常量N表示n的最大范围题目n20 int n,k; // n表示整数个数k表示需要选出的个数 int a[N]; // 记录n个整数 int ans0; // 记录和为素数的组合种类数 // 判断一个数x是否为素数 bool is_prime(int x){ if(x2) return false; // 小于2的数不是素数 for(int i2;i*ix;i){ if(x%i0) return false; // 如果能被i整除不是素数 } return true; // 是素数 } // 深度优先搜索DFS // start: 当前从第几个数开始选保证组合不重复且有序 // cur: 当前已经选了几个数 // sum: 当前已选数的总和 void dfs(int start,int cur,int sum){ if(curk){ // 如果已经选够了k个数递归终止条件 if(is_prime(sum)) ans; // 判断总和是否为素数,种类数加1 return; // 结束当前递归分支 } // 可行性剪枝剩下的数必须足够凑齐k个 // 当前从start开始选还需要选(k-cur)个数所以i的上限是 n-(k-cur)1 // 循环终点 总数 - 还需要选的个数 1 for(int istart;in-(k-cur)1;i){ dfs(i1,cur1,suma[i]); // 从下一个位置开始选已选数量1总和加上a[i] } } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定加快读取速度 cinnk; // 读入n和k for(int i1;in;i) cina[i];// 读入n个整数 dfs(1,0,0); // 从第1个数开始选当前选了0个当前总和为0 coutans; // 输出和为素数的组合种类数 return 0; // 程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P1036前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的组合枚举与素数判定问题。问题转化题目要求从 n个整数中任选 kk 个相加统计和为素数的组合种类数。这本质上是一个“从 n 个数中取 k 个数的组合问题”即 Cnk 而不是排列问题。因为加法满足交换律3719和7319是同一个组合我们需要避免重复计算。算法选择DFS 剪枝由于 n≤20 数据规模较小我们可以使用深度优先搜索DFS来暴力枚举所有可能的组合。避免重复在 DFS 过程中我们通过一个start参数来记录当前从哪个位置开始选数。每次递归选择下一个数时都从当前位置的下一个位置i1开始选从而保证选出的数在原数组中的下标是严格递增的天然避免了组合的重复。可行性剪枝在枚举当前层的选择时如果剩下的数字个数不足以凑齐 kk 个数就提前停止枚举减少无效搜索。素数判定当凑齐 kk 个数时计算它们的和并使用试除法判断该和是否为素数。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; const int N25; // 定义常量 N表示 n 的最大范围题目 n20 int n,k; // n 表示整数个数k 表示需要选出的个数 int a[N]; // 记录 n 个整数 int ans0; // 记录和为素数的组合种类数详细分析这部分定义了算法的基础变量。a[N]用来存储输入的 nn 个整数ans作为全局计数器用来累加满足条件的组合数。2. 素数判定函数is_prime// 判断一个数 x 是否为素数 bool is_prime(int x){ if(x2) return false; // 小于 2 的数不是素数 for(int i2;i*ix;i){ if(x%i0) return false; // 如果能被 i 整除不是素数 } return true; // 是素数 }详细分析这是一个标准的试除法求素数函数。边界处理首先排除了小于 2 的情况因为 0 和 1 不是素数。循环优化循环的终止条件是i*i x即 i≤xi≤x​ 。这是因为如果 xx 有一个大于 xx​ 的因子那么它必然有一个小于 xx​ 的对应因子。这种优化将素数判定的时间复杂度从 O(x)O(x) 降低到了 O(x)O(x​) 对于本题中可能达到 5×106×205×106×20 级别的和来说效率提升非常明显。3. 核心逻辑DFS 组合枚举与剪枝// 深度优先搜索DFS // start: 当前从第几个数开始选保证组合不重复且有序 // cur: 当前已经选了几个数 // sum: 当前已选数的总和 void dfs(int start, int cur, int sum){ if(curk){ // 如果已经选够了 k 个数递归终止条件 if(is_prime(sum)) ans; // 判断总和是否为素数,种类数加 1 return; // 结束当前递归分支 } // 可行性剪枝剩下的数必须足够凑齐 k 个 // 当前从 start 开始选还需要选 (k-cur) 个数所以 i 的上限是 n-(k-cur)1 // 循环终点 总数 - 还需要选的个数 1 for(int istart; in-(k-cur)1; i){ dfs(i1, cur1, suma[i]); // 从下一个位置开始选已选数量1总和加上 a[i] } }详细分析这是代码的灵魂完美实现了组合枚举。递归终止条件当cur k时说明已经凑齐了 kk 个数此时直接调用is_prime(sum)进行判定如果为真则全局答案ans加 1。避免重复的核心for循环的起始值是start而递归调用时传入的是i1。这意味着如果当前选择了第i个数下一层递归只能从i1及之后的数中选择。这保证了选出的数在原数组中的下标是严格递增的从而避免了3719和7319这种重复计算。可行性剪枝循环的终止条件i n-(k-cur)1是一个经典的组合数学优化。它的意思是当前还需要选k-cur个数如果从当前位置i往后数剩下的数字个数已经不够填满这k-cur个位置了那么继续枚举i及其后面的数就没有意义了直接跳出循环。4. 主函数输入处理与启动搜索int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnk; // 读入 n 和 k for(int i1;in;i) cina[i]; // 读入 n 个整数 dfs(1,0,0); // 从第 1 个数开始选当前选了 0 个当前总和为 0 coutans; // 输出和为素数的组合种类数 return 0; }详细分析主函数负责数据的读入和算法的启动。dfs(1,0,0)表示从数组的第 1 个位置开始尝试选择当前已经选了 0 个数当前的累加和为 0。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点素数判定is_prime(int x)试除法判断一个数是否为素数准确判定组合的和是否符合题目要求i*ix保证了效率递归终止if(curk)判断是否已经选够了 k 个数到达搜索树的叶子节点进行结果统计避免重复dfs(i1, ...)下一层递归只能从当前数的下一个位置开始选保证选出的组合下标严格递增避免了排列带来的重复计算可行性剪枝i n-(k-cur)1限制当前层枚举的上界当剩余数字不足以凑齐 k 个数时提前终止大幅减少无效搜索状态传递suma[i]将当前选择的数累加到总和中在递归过程中动态维护当前组合的总和避免了在叶子节点重新遍历求和全局计数ans累加满足条件的组合数记录最终的答案