首页 > 试题广场 >

[NOIP2002]选数

[编程题][NOIP2002]选数

热度指数：1042 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

已知 n 个整数 x₁,x₂,…,x_n，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29）。

输入描述:

输入格式为：n , k（1<=n<=20，k＜n）
x₁,x₂，…,x_n （1<=x_i<=5000000）

输出描述:

输出格式为：一个整数（满足条件的种数）。

示例1

输入

4 3
3 7 12 19

输出

算法知识视频讲解

💪✊💪abc

#include<bits/stdc++.h>
using namespace std;

bool is_prime(int n)
{
	if (n <= 3) return n > 1;
	int k = static_cast<int>(sqrt(static_cast<double>(n)));
	for (int i = 2; i <= k; ++i) if (n % i == 0) return false;
	return true;
}

int count_prime(vector<int>& inputs, int i, int remained_k, int cur_sum)
{
	if (i == inputs.size()) return remained_k != 0 ? 0 : is_prime(cur_sum);
	return count_prime(inputs, i + 1, remained_k - 1, cur_sum + inputs[i]) + count_prime(
		inputs, i + 1, remained_k, cur_sum);
}

int main()
{
	int n, k, num;
	vector<int> inputs;
	cin >> n >> k;
	while (n--)
	{
		cin >> num;
		inputs.push_back(num);
	}
	cout << count_prime(inputs, 0, k, 0) << endl;
	return 0;
}

发表于 2019-11-10 21:53:49 回复(0)