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

· · 题解

题目分析

本题的核心问题是从给定的 n 个整数中任选 k 个整数进行相加，然后统计这些和中为素数的组合的数量。下面我们从输入输出、问题求解思路等方面进行详细分析。

输入输出分析

输入： 第一行包含两个用空格隔开的整数 n 和 k，其中 1\leq n\leq 20 且 k < n。n 表示整数的总数，k 表示需要选取的整数个数。

第二行包含 n 个整数 x_1,x_2,\cdots,x_n，每个整数的范围是 1\leq x_i\leq 5\times 10^6。

输出： 输出一个整数，表示和为素数的组合的种类数。

问题求解思路分析

要解决这个问题，主要分为两个关键步骤：一是找出从 n 个整数中选取 k 个整数的所有组合；二是判断每个组合的和是否为素数。

组合选取

由于 n 的范围较小（1\leq n\leq 20），我们可以使用深度优先搜索（DFS）算法来枚举所有可能的组合。深度优先搜索是一种通过递归的方式遍历所有可能状态的算法，非常适合解决组合问题。在本题中，我们从第一个数开始，依次尝试选取每个数，并递归地选取后续的数，直到选取了 k 个数为止。

素数判断

对于每一种组合的和，我们需要判断它是否为素数。素数是指大于 1 且只能被 1 和自身整除的正整数。判断一个数 num 是否为素数，我们可以从 2 开始到 \sqrt{num} 进行遍历，如果 num 能被其中任何一个数整除，则它不是素数；否则，它是素数。

代码实现思路

代码整体结构

代码主要由三个部分组成：素数判断函数、深度优先搜索函数和主函数。

各部分详细解释

素数判断函数 isPrime
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

首先判断 num 是否小于 2，如果小于 2，则直接返回 false，因为素数定义要求大于 1。\ 然后从 2 开始到 \sqrt{num} 进行遍历，如果 num 能被其中任何一个数整除，则返回 false，表示不是素数。\ 如果遍历完都没有找到能整除 num 的数，则返回 true，表示是素数。

深度优先搜索函数 dfs
void dfs(int start, int cnt, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) {
            ans++;
        }
        return;
    }
    for (int i = start; i < n; i++) {
        dfs(i + 1, cnt + 1, sum + nums[i]);
    }
}

start 表示当前搜索的起始位置，cnt 表示已经选取的数的个数，sum 表示当前选取的数的和。

当 cnt 等于 k 时，说明已经选取了 k 个数，此时调用 isPrime 函数判断 sum 是否为素数，如果是则将结果 ans 加 1。

从 start 开始遍历数组，递归调用 dfs 函数，更新 start 为 i + 1，cnt 为 cnt + 1，sum 为 sum + nums[i]，以继续选取下一个数。

主函数 main
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

首先读取输入的 n 和 k，以及 n 个整数。

调用 dfs 函数开始搜索，初始时 start 为 0，cnt 为 0，sum 为 0。

最后输出结果 ans。

复杂度分析

时间复杂度

组合选取的时间复杂度为 O(C_{n}^k)，其中 C_{n}^k=\frac{n!}{k!(n - k)!} 表示从 n 个数中选 k 个数的组合数。

对于每一种组合，判断素数的时间复杂度为 O(\sqrt{m})，其中 m 为选取的数的和的最大值。

因此，总的时间复杂度为 O(C_{n}^k \sqrt{m})。

空间复杂度

主要的空间开销是递归调用栈的空间，递归的深度最大为 k，因此空间复杂度为 O(k)。

创造不易，点个赞再走吧