信息学奥赛一本通 1919：【02NOIP普及组】选数 | 洛谷 P1036 [NOIP2002 普及组] 选数

【题目链接】

ybt 1919：【02NOIP普及组】选数
洛谷 P1036 [NOIP2002 普及组] 选数

【题目考点】

1.排列组合

2.深搜（子集树）

3.质数

【解题思路】

深搜（子集树），每次确定要不要选择某个数字。选择该数字，则加和增加，然后看下一个数字。不选择，则直接看下一个数字。如果选择的数字个数达到k个，那么看加和是不是质数，如果是，计数加1。最后输出计数。

看数据范围k,n都小于等于20，从n个数中找k个数的组合数$C_n^k$最大值为$C_{20}^{10}=184756$，可以通过深搜搜索所有可能的组合看加和为质数有多少种情况。
如果直接判断一个数是否是质数，复杂度为$O(\sqrt{x})$，x为待判断的数字。x的最大可以是$10$个$5\ast 10^6$相加即$5\ast 10^7$，$\sqrt{5\ast 10^7}\approx 7\ast 10^3$这个数再乘以184756，结果接近$10^9$。
以上只是对时间复杂度最坏情况的理论上的分析，实际每次判断质数多数情况下不会循环$O(\sqrt{x})$次，应该不会超时，实际也没有超时。

【题解代码】

解法1：

#include <bits/stdc++.h>
using namespace std;
#define N 25
int n, k, x[N], sum, ct;//sum:加和 
bool isPrime(int n)//判断n是不是质数
{
    for(int i = 2; i <= sqrt(n); ++i)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}
//看要不要选择第i个数字，现在还需要选择m个数字（深搜子集树） 
void dfs(int i, int m)
{
    if(m == 0)//找到解，已经选择了k个数字 
    {
        if(isPrime(sum))//如果num是质数 
            ct++;//计数加1 
        return;
    }
    if(n-i+1 < m)//剪枝 若 剩余的数字个数 小于 要选择的数字个数 就退出 
        return;
    dfs(i+1, m);//第i数字不加入
    sum += x[i];//状态更新 
    dfs(i+1, m-1);//第i数字加入
    sum -= x[i];//状态还原 
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> x[i];
    dfs(1, k);
    cout << ct;
    return 0;
}