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

scguo · 2025-02-26 15:48:29 · 题解

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

思路

注意到 n \le 20，直接全排列或者选和不选的 DFS 即可，最后判断和是不是素数，非常暴力。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[25],b[25],ans;
bool vis[25];
bool ss(int x)
{
    if(x<2) return false;
    for(int i=2;i*i<=x;++i) if(x%i==0) return false;
    return true;
}
void dfs(int x)
{
    if(x>k)
    {
        int sum=0;
        for(int i=1;i<=k;++i) sum+=a[b[i]];
        if(ss(sum)) ans++;
        return;
    }
    for(int i=b[x-1]+1;i<=n;++i)
    {
        if(!vis[i])
        {
            vis[i]=1;
            b[x]=i;
            dfs(x+1);
            vis[i]=0;
        }
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>a[i];
    dfs(1);
    cout<<ans;
    return 0;
}