AcWing 5491. 选数
原题链接
简单
作者:
xuebudong
,
2024-03-14 19:59:47
,
所有人可见
,
阅读 19
代码详解
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,k;
int arr[N],b[N];//b[n]用来存组合,arr存数去数据
int res;//素数个数
//递归组合,往往以前的都是一个递增有序的数组进行组合1-n,但这道题是将给定的元素进行组合
//组合得到的和还要进行素数判断
//顺序:枚举每个位置放哪个数
bool sushu(int x){
if(x<2) return false;
for(int i=2;i<=x/i;i++){
if(x % i==0) return false;
}
return true;
}
void dfs(int x,int start){//x是第几个位置,start是从哪个数开始枚举
//出口
if(x>k){
int sum=0;
for(int i=1;i<=k;i++) sum+=b[i];
//判断组合之和是不是素数
if(sushu(sum)) res++;
//每次枚举完一次组合都要将sum归零
return ;
}
//枚举数字
for(int i=start;i<=n;i++){
//选择这个数
b[x]=arr[i];
dfs(x+1,i+1);
//恢复现场
b[x]=0;
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
dfs(1,1);//这里前数字1代表第几个位置,后1代表我枚举的第几个数
printf("%d",res);
return 0;
}