【[NOIP2002 普及组] 选数】题解

原题目链接：Link

一道简单的DFS

我的思路和大佬们的不一样。很显然，每个数都有选或不选两种情况，这就是搜索的方向。当已经选了 $k$ 个数后，就没必要再往下搜索了，直接判断 $k$ 个数之和 $sum$ 是否为素数即可，这是边界。

Code：

#include <cstdio>
#include <cmath>
using namespace std;
int n, k, ans, x[25];
bool prime(int x) {
     // 判断质数if(x <= 1) return 0;for(int i = 2;i <= sqrt(x); ++i) if(x % i == 0) return false;return true; 
}
void dfs(int index, int nowk, int sum) {
    if(nowk == k) {
     // 已经选了 k 个数if(prime(sum)) ans ++; // 判断总和是否为素数 若是，则答案加一return ; }if(index > n) return ; // 限制条件，查找范围是 [1, n]，这里不写会 TLEdfs(index + 1, nowk, sum); // 不选当前这个数，搜索下一个dfs(index + 1, nowk + 1, sum + x[index]); // 选当前这个数，将这个数累加给 sum，将已经选的个数加一，再搜索下一个
}
int main() {
    scanf("%d %d", &n, &k);for(int i = 1;i <= n; ++i) scanf("%d", &x[i]);dfs(1, 0, 0); // 从 1 ~ n 搜索，开始的 nowk 和 sum 都是0printf("%d", ans);return 0; 
}