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

piske · 2025-02-25 12:29:02 · 题解

[NOIP 2002 普及组] 选数

题目传送门

思路：

用深搜枚举所有合法是组合，统计结果是素数的个数，最后输出。

Coding:

#include <bits/stdc++.h>
using namespace std;
int n;
int a[21];
int k;
int num;
void dfs(int now,int id,int ans)
{
    if(now==k+1) //满足条件 
    {
        bool f=true;
        for(int i=2;i*i<=ans;i++)
            if(ans%i==0)
            {
                f=false;
                break;
            }
        if(f==true) //判断是否是素数 
            num++;
    }
    else if(id<=n)
        for(int i=id;i<=n;i++)
            dfs(now+1,i+1,ans+a[i]); //搜索所有组合 
}
int main( ){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dfs(1,1,0);
    cout<<num; //输出方案数 
    return 0;
}