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

别人内卷我在躺平 · 2025-02-25 21:56:47 · 题解

本题考查算法：搜索，质数（素数）。
我在这里给大家介绍一种 DFS 的写法：

• 首先这个数 a_i 要么选，要么不选，而且只能选 k 个数。
• 为了保证不会出现选 2,3,5，再选 3,2,5 的情况，我们可以让每种情况中的数保持升序。即 k=3,lattice_1<lattice_2<lattice_k。
• 我们需要在选这个数的同时记录当前的和 Addition，到了判断和的时候，我们可以再写一个判断函数的函数，判断当前这种情况是否满足要求。
  判断质数：

bool is_Prime(int x){
    if(x<=1){//x<=1肯定不是质数
        return false;
    }
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){//找到除1和它本身2个因数的其它一个因数
            return false;
        }
    }
    return true;
}

完整代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1005;
int a[maxn];
int n,k;
int lattice[maxn],Addition=0,ans=0;
bool is_Prime(int x){
    if(x<=1){
        return false;
    }
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
void dfs(int x){
    if(x>k){
        if(is_Prime(Addition)){
            ans++;
        }
        return ;
    }
    for(int i=lattice[x-1]+1;i<=n;i++){
        lattice[x]=i;
        Addition+=a[i];
        dfs(x+1);
        lattice[x]=0;
        Addition-=a[i];
    }
    return ;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1);
    cout<<ans;
    return 0;
}

时间复杂度：O(N!)。