蓝桥杯备赛：Day5-P1036 选数

算法笔记P1036 [NOIP 2002 普及组] 选数1. 题目描述[P1036 NOIP 2002 普及组] 选数 - 洛谷从n nn个整数中任选k kk个数相加统计有多少种选法的和为质数。数据范围n ≤ 20 , k n n \le 20, k nn≤20,kn每个整数 5 × 10 6 5 \times 10^65×106。2. 核心代码 (C AC版本)#include bits/stdc.h using namespace std; typedef long long ll; ll a[25]; // 存储输入的 n 个数 int N, K; ll ans 0; // 计数器符合条件的质数和个数 // 质数判定O(sqrt(sum)) bool is_prime(int n) { if (n 2) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; } // DFS 组合模型 // position: 当前选到了第几个数 // sum: 当前已选数字的累加和 // start: 搜索起点保证下标单调递增 void dfs(int position, ll sum, int start) { // 1. 递归出口选够了 K 个数 if(position K) { if(is_prime(sum)) ans; return; } // 2. 组合模型核心从 start 开始往后选不回头 for(int i start; i N; i) { // 隐式回溯sum a[i] 作为参数传递无需手动撤销 dfs(position 1, sum a[i], i 1); } } void solve() { if(!(cin N K)) return; for (int i 1; i N; i) cin a[i]; ans 0; dfs(1, 0, 1); cout ans endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int _ 1; while(_--) solve(); return 0; }3. 核心考点与注意事项组合模型 (Combination)与全排列不同组合不计较顺序。通过引入start参数强制让选取的下标单调递增i → i 1 i \rightarrow i1i→i1从而物理隔绝了重复排列如选了1 , 2 1,21,2就不会再选2 , 1 2,12,1。隐式回溯在dfs(position 1, sum a[i], i 1)中sum a[i]的结果直接传给下一层。当递归返回时本层的sum值并没有改变因此不需要像used数组那样手动执行sum - a[i]。质数优化使用i * i n进行判定时间复杂度为O ( N ) O(\sqrt{N})O(N​)是应对高频调用的标准写法。