题解：P1036 [NOIP 2002 普及组] 选数

· · 题解

前置知识

你需要先学习深度优先搜索和基础语法，阅读本篇题解前请确保你已经掌握上述内容。

思路讲解

题目要求我们从给出的 n 个数里面选 k 个数，希望所选的数之和为素数，要求输出方案数。通过分析数据范围，我们发现可以使用深度优先搜索和剪枝优化进行暴力求解。

搜索函数要定义三个参数，分别表示当前已选择几个元素、上个元素的下标、当前选的数字之和，记录已选几个元素的参数用于判定边界及时退出，上个元素的下标参数用于剪枝优化，同时也防止了两个数顺序不同导致的重复计算，当前选的数字之和参数用于记录数字和，在末尾判断是否为素数时能够起到优化作用，防止多次循环求和导致的超时。

每次搜索时判定是否已选够 k 个数，如果是就判断数字和是否为素数，并且累加方案数，如果未到达边界，就从上个元素下标的下一个位置开始选择元素，开启下一轮搜索时记得修改传参，记录已选个数、当前元素下标、数字和。

代码展示

写的时候注意搜索函数的编写，保证基本框架正确的同时，也要记得把上述的剪枝优化写进去。如果你的程序输出比标准答案要大，可以检查一下是否重复选相同元素，顺序不同的情况是否重复计算。

写的时候注意细节，下面是我的代码：

#include <bits/stdc++.h>

using namespace std;

int n,m,cnt; // 题面里的n和k，以及累加方案数的变量cnt
int a[21]; // 存储n个整数

void dfs(int w,int start,int sum){ // 已选个数、上个元素下标、数字和
    if (w == m){ // 判断边界，是否已选k个数
        bool y=1; // 假设是素数
        for(int i=2;i<=sqrt(sum);i++){ // 枚举可能的因数来判断素数
            if(sum%i==0){ // 如果可以整除
                y=0; // 那就不是素数，标记
                break; // 退出循环
            }
        }
        if(y) cnt++; // 如果是素数就累加方案数

        return; // 返回上一层搜索调用
    }
    for(int i=start+1;i<n;i++){ // 枚举，注意从上个元素下标的下一个位置开始选，防止重复和多次计算
        dfs(w+1,i,sum+a[i]); // 选的数字个数加一，把上个元素下标设为该元素下标，数字和要加上这个元素的值
    }
}

int main(){
    cin >> n >> m; // 读入n和k，我只是改了变量名，含义是一样的

    for(int i=0;i<n;i++) cin>>a[i]; // 读入n个整数

    dfs(0,-1,0); // 调用函数，注意传参的已选个数、上个元素下标、数字和，还没选所以是0个数字，下标在搜索时会加一处理，所以设为-1，没选数字所以和为0
    cout << cnt; // 输出方案数

    return 0; // 完结撒花
}