1. 选数问题在考什么拆开包装看本质接触过 NOIP 普及组的选手基本都绕不开 P1036 这道题。题目描述很短给 n 个正整数从里面任选 k 个把选出来的数加起来判断这个和是不是素数最后输出和为素数的方案总数。代码量不到四十行但当年考场上在这道题上翻车的人真不少。4 3 3 7 12 19这组样例对应四种选法37122237192931219347121938其中只有 29 是素数所以答案是 1。表面看这题只考枚举组合 素数判断两个点。但往深了说它真正在考三件事能不能把任选 k 个翻译成可执行的搜索过程会不会在搜索时通过参数控制顺序避免同一组数被重复计数对素数判断的理解是不是还停留在从 2 试到 x-1的原始阶段。1.1 数据范围直接决定你的写法题目里 n 的上限一般是 20k 不超过 nxi 最大能到 5000000。这意味着组合数的规模在 C(20, k) 这个量级最坏情况发生在 k10 时大约是 18 万多种组合。这个规模下暴力枚举所有组合是完全可行的不需要什么高级剪枝也不需要记忆化搜索。但同样的数据范围放在别的场景里可能就会出事如果你用全排列去枚举那就是 P(20, 10)约 6.7 万亿种直接跑死。所以这道题虽然代码简单但枚举组合和枚举排列的差异恰恰是第一道分水岭。1.2 组合与排列的本质区别组合不关心顺序{3, 7, 19} 和 {7, 3, 19} 是同一种选法。如果你写三层循环去枚举只要保证每层起点比上一层大就能天然避免重复。换成递归写法这个起点递增的约束就落在 DFS 的start参数上。理解了这个你才明白为什么很多人写的 DFS 里有一个start而不是每次都从 0 开始。从 0 开始是排列的逻辑从start开始才是组合的逻辑。这个细节不搞清楚代码跑出来的答案铁定偏大而且你自己还看不出来问题在哪。2. DFS 生成组合一个 start 参数省掉所有重复组合问题最经典的做法就是 DFS 回溯。核心思路是每次递归决定下一个选谁同时用一个参数记录我该从哪个位置开始选保证后面的选择范围永远在当前下标之后。2.1 标准写法与逐行解读int n, k, ans; int a[25]; void dfs(int step, int start, int sum) { if (step k) { if (isPrime(sum)) ans; return; } for (int i start; i n; i) { dfs(step 1, i 1, sum a[i]); } }step记录已经选了几个数start表示这一层可以从哪个下标开始尝试sum是当前已选数的累加和。递归终止条件是step k说明已经选满 k 个数这时候只需要判断sum是不是素数。关键在dfs(step 1, i 1, sum a[i])这个递归调用第二层的起点被强制设为i 1这就砍掉了所有往回选的可能。比如第一层选了下标 2 的数第二层就只能从下标 3 开始永远不会再碰下标 0 到 2。整个搜索过程生成的序列下标是严格递增的对应到数学上就是标准的组合枚举。这种写法的好处是状态里不需要额外开布尔数组记录哪些数用过。排列问题要vis[]是因为每个位置都可能选到任何一个未用过的数而组合问题用起点递增就堵死了重复路径省内存也省判断。2.2 另一种思路每个数选或不选除了上面这种选下一个的写法还有一种常见的递归分支方式——对每个数做要或不要的决定void dfs(int idx, int cnt, int sum) { if (cnt k) { if (isPrime(sum)) ans; return; } if (idx n) return; // 选当前这个数 dfs(idx 1, cnt 1, sum a[idx]); // 不选当前这个数 dfs(idx 1, cnt, sum); }这种写法的本质是二叉树遍历每个节点分两支深度为 n但因为有cnt k提前收口实际展开的节点数比 2^n 小得多。两种写法最终生成的组合集合完全一样区别只在于思考角度第一种是从剩下的数里挑下一个第二种是逐个决定每个数的去留。我个人的习惯是推荐第一种因为step start sum三个参数对应选了几个、能选谁、和是多少信息更直观调试的时候打日志也方便看状态变化。第二种适合在需要额外剪枝的场景下用比如已经选够 k 个数但还有剩余元素时可以在cnt k处直接返回不用再继续往后走。3. 素数判定试除法的正确打开方式选好组合之后剩下的工作就是判断 sum 是不是素数。素数在数学上的定义是不大于 1 的自然数中除了 1 和它本身以外不再有其他因数。注意1 不是素数2 是最小的素数这两个边界条件在代码里特别容易漏。3.1 为什么只要试到平方根判断一个数 x 是否为素数最朴素的办法是从 2 试到 x-1看有没有能整除的因子。但仔细想一下如果 x 有一个大于 sqrt(x) 的因子 d那么 x/d 一定是小于 sqrt(x) 的因子。也就是说因子是成对出现的一大一小。只要小的那边没有因子大的那边也必然没有。所以循环只需要跑到i * i x就够了。sum 的最大值不会超过 k 乘 xi 的上限按 n20、xi5000000 算sum 最大约一亿sqrt(1e8) 才一万。也就是说每组组合最多试除一万次18 万组组合就是 18 亿次模运算。听着吓人但实际数据基本到不了这个极端而且很多数在试除到 3 或 5 的时候就提前 break 了真实耗时远低于理论最坏值。3.2 一个隐藏的溢出风险判断条件写成i * i x的时候要注意 i 和 x 的类型。如果 x 是 inti 最大到 sqrt(INT_MAX) 也就是 46340 左右i 乘 i 还在 int 范围内。但如果你把 x 的范围放大到十亿级以上i 的平方就可能溢出 int导致判断条件变成死循环或者提前退出。这道题的数据范围里 sum 用 int 存是够的但谁也不能保证以后做题不会遇到更大的数据。稳妥的做法是把相关变量都声明成long long或者用i x / i这种不乘法的写法bool isPrime(long long x) { if (x 2) return false; for (long long i 2; i x / i; i) { if (x % i 0) return false; } return true; }i x / i和i * i x在数学上等价但完全避开了乘法溢出的问题。这算是一个很小的细节可是在正式比赛里这种细节往往就是 AC 和 WA 的分界线。3.3 需不需要上米勒-拉宾有读者可能会问既然要判这么多组和用 Miller-Rabin 或者预处理素数表会不会更快答案是这道题不需要。试除法在数据范围内已经足够通过而且 Miller-Rabin 的常数并不小对一亿以内的数来说优势不明显。预处理素数表倒是可以考虑先筛出 sqrt(最大和) 以内的所有素数然后用这些素数去试除 sum试除次数从一万次降到一千多次。不过在 n20 的规模下这点提升远不如把 DFS 写对来得重要。4. 完整参考代码与复杂度账本把前面的 DFS 和素数判断拼起来就是这道题的完整解法。我下面给出完整的 C 实现这段代码可以直接提交到 OJ 上。4.1 完整实现#include bits/stdc.h using namespace std; int n, k, ans; int a[25]; bool isPrime(int x) { if (x 2) return false; for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; } void dfs(int step, int start, int sum) { if (step k) { if (isPrime(sum)) ans; return; } for (int i start; i n; i) { dfs(step 1, i 1, sum a[i]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; for (int i 0; i n; i) { cin a[i]; } dfs(0, 0, 0); cout ans \n; return 0; }ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是输入输出加速刷题习惯了都会加上在数据量大的时候能明显减少 IO 耗时。注意答案变量 ans 要声明成全局变量或者用引用传递不然递归层数一变就容易丢值。4.2 复杂度账本怎么算时间复杂度分两部分组合生成和素数判断。组合生成部分DFS 展开的节点数等于所有满足step k的中间状态数加起来大约是 C(n, 0) C(n, 1) ... C(n, k) 的量级。当 k10、n20 时大约是 61 万个节点完全可接受。每个叶子节点调用一次素数判断每次判断最多试除 sqrt(sum) 次所以总复杂度是 O(C(n, k) * sqrt(k * max(xi)))。空间复杂度很简单递归深度最多 k 层加上一个长度为 n 的数组总空间就是 O(n k)几乎是零额外开销。4.3 可选的优化手段如果你对性能有执念可以试试这几个方向的优化在dfs开头加一个剪枝如果剩下可选的数量n - start已经不足k - step直接返回因为无论如何都凑不满 k 个数了。素数判断时先查一个小素数表比如 2、3、5能被整除就直接返回 false能省掉不少大循环。如果测试数据有多组可以把已经判断过的 sum 存进哈希表重复的 sum 直接复用结果。不过这道题通常只有一组数据这个优化用不上。5. 我在调试这道题时踩过的三个坑这道题代码虽然短但越是短的代码越容易在细节上栽跟头。我把自己实际踩过的坑和帮别人调试时见过的典型错误整理出来每一个都对应具体的错误现象和原因。5.1 递归参数传错start 和 i1 的区别我第一次写这道题的时候递归调用写成了dfs(step 1, start 1, sum a[i])结果答案比标准答案多了不少。原因在于start 1和i 1根本不是一回事。下一层的可选取范围应该从当前真正选中的下标i之后开始而不是从上一层的起始位置往后挪一位。举个例子就明白了n5 时第一层start0的循环里i会依次取 0、1、2、3、4。如果第二层传的是start 1那无论第一层选了哪个 i第二层都只能从下标 1 开始。当第一层选了 i2 时第二层还能选下标 1 的数这就产生了下标非递增的组合和第一层选了 i1 再选下标 2 的组合完全重复。排查这类问题有个笨办法在dfs入口把step, start, i, sum全部打印出来跟着跑几轮很快就能发现递归参数传递的异常。5.2 素数的边界1 和 0 的处理组合出来的和最小可能是三个最小的正整数相加直接等于 3 甚至 2一般不会出现 1 或 0 的情况。但如果 k1且输入数据里有 x1那 sum 就可能等于 1。判断函数里必须有if (x 2) return false;这一行否则 1 会被误判成素数。很多新手只在循环里判断x % i 0忘了处理小于 2 的情况遇到特殊数据就会崩。这种数据往往不在样例里只有提交之后 WA 了你才会发现。5.3 数组越界和读取顺序还有一个容易忽略的问题是输入顺序。题目是先给 n 和 k再给 n 个数但我在帮人调试时见过有人把读取顺序写反了导致k被读成一个大数DFS 直接跑飞。虽然不是算法问题但考场上一紧张就容易写错。建议养成分行读取的习惯cin n k; for (int i 0; i n; i) cin a[i];还有一点a 数组的容量要留够。n 最大 20声明成a[25]没问题但如果你习惯用a[20]一旦循环写成i n就会出现下标越界。这种越界在本地不一定会报错但在 OJ 上有时会表现为莫名其妙的运行时错误。6. 这道题能迁移到哪些地方P1036 虽然是一道普及组的老题但它的解法骨架在后续很多题目里都能见到。组合生成的 DFS 模式、参数状态设计、剪枝思路这些东西的价值远不止这一道题。6.1 同一套模板能解的变式求组合的具体方案在 DFS 里多开一个path[]数组选中的数记下来到step k时输出。组合总和问题比如 LeetCode 40 这类题在step k或者sum target时记录答案区别只是终止条件不同。有重复元素的组合去重先把数组排序DFS 循环里如果i start a[i] a[i-1]就跳过避免同一层选择相同的数。数的划分类问题把选 k 个数改成把 n 分成 k 个正整数同样用这个带起点递增的 DFS 框架。6.2 从普及组到提高组的衔接再往后学你会发现这个 DFS 框架在动态规划、状态压缩、折半搜索里都有影子。比如 n 扩大到 40 时C(40, 20) 太大了暴力枚举会超时这时候就要用 meet-in-the-middle前一半和后一半分别枚举所有组合再排序后双指针找满足条件的配对。这个技巧的核心思想其实还是建立在会枚举组合的基础上。还有一类问题是背包计数给你 n 个物品选任意个问有多少种方式让总重量等于目标值。这类题如果 n 小完全可以套用这道题的选/不选 DFS 写法只是把终止条件从cnt k改成sum target。6.3 学这道题真正该带走什么我在帮学生准备比赛的时候经常拿这道题当组合枚举的第一课。它不像图论、数论那些模块那样需要大量前置知识只要会递归、知道素数的定义就能上手。但在这么小的体量里它浓缩了三个最重要的基本功状态设计step、start、sum 三个参数各司其职、边界处理素数判断的边界、递归终止的边界、复杂度估算C(n,k) 的量级判断。这三样东西几乎会跟着你从普及组一路走到提高组再到更远的比赛。所以如果你刚开始刷题或者正在带别人入门把这道题吃透远比多刷十道简单模拟题更有价值。我自己现在偶尔给学生讲递归还是会从这道题入手——因为它足够简单简单到能让你把注意力完全放在搜索过程本身上而不是被题目背景干扰。