AcWing 5491. 选数
原题链接
简单
作者:
louiscy
,
2024-04-03 21:14:39
,
所有人可见
,
阅读 428
写的很好理解,我觉得新手非常适合参考
include <iostream>
using namespace std;
const int N = 20;
int q[N];// 定义数组q存储数据
int n, k, res;
bool b[N]; // 定义一个bool类型的数组b, 来判断该数是否选取
// 判断是否是素数
bool su(int p){
if (p < 2) return false;
for (int i = 2; i <= p / i; i ++)
if (p % i == 0) return false;
return true;
}
// 定义一个函数,来讨论每个数的状态,选或不选
void f(int u){
if (u > n){
int sum = 0, t = 0;
for (int i = 1; i <= n; i ++)
if (b[i]) t ++, sum += q[i];
if (t == k && su(sum)) res ++;
return ;
}
b[u] = true;// 选
f(u + 1); // 讨论下一个数的状态
b[u] = false;// 不选(恢复现场)
f(u + 1); // 讨论下一个数的状态
}
int main(){
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++) scanf("%d", &q[i]);
f(1);
printf("%d\n", res);
return 0;
}
//作者:家里蹲大学附属搬码队队长
//链接:https://www.acwing.com/solution/content/226304/
自己写的代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 21;
int n, k;
int a[N];
bool is_prime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
int dfs(int idx, int cnt, int sum) {
if (cnt == k) {
return is_prime(sum) ? 1 : 0;
}
if (idx == n) return 0;
return dfs(idx + 1, cnt + 1, sum + a[idx]) + dfs(idx + 1, cnt, sum);
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
cout << dfs(0, 0, 0) << endl; //从第0个数字开始选择,当前已选择0个,总和是0
return 0;
}