选数_牛客博客

题目描述

已知 $x_1,x_2,…,x_nx1,x2,…,xn，以及11个整数k(k<nk<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3 n=4,k=3,4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：

输入格式

键盘输入，格式为：

$x_1,x_2,…,x_n (1 <= x_i <= 5000000)x1,x2,…,xn(1≤xi≤5000000)$

输出格式

屏幕输出，格式为：

$这题真正的让我对dfs有个初步的了解，真的。$

$这题需要没有遗漏的选出任意k个数之和的所有情况，如果k是个确定的数，我们完全可以用k重循环来解决这道题，然而并非如此，我们想到，循环和递归是互通的，我们不能控制有多少重循环，却可以控制递归的次数。话不多说，上代码。$

#include <iostream>
using namespace std;
long long ans = 0;
int a[25], n, k;

//判断是否为质数
bool is_prime(int x)
{
    for (int i = 2; i * i <= x;i++) if(x%i == 0)
            return false;
    return true;
}

//利用深度优先搜索进行搜索
void dfs(int cnt, int sum, int s)
//cnt为计数器，当cnt等于k时，递归结束。
//sum为当前所加数之和
//s为起始下标
{
    if(cnt == k) {
        //判断和是否为质数
        if(is_prime(sum))
            ans++;
        return;//递归结束
    }
    for (int i = s; i < n;i++)
        dfs(cnt + 1, sum + a[i], i + 1);
//每加一次，计数器加一，自底而上的加，防止遗漏
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n;i++)
        cin >> a[i];
    dfs(0, 0, 0);//初始化
    cout << ans << endl;
    return 0;
}

原文链接：https://www.luogu.com.cn/problemnew/solution/P1036

原创作者：东北小蟹蟹