NOIP 2002 选数(DFS+素数判定)

一时失言乱红尘 2022-05-17 09:37 267阅读 0赞

题目描述

已知n个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k＝3，4个整数分别为 3，7，12，19时，可得全部的组合与它们的和为：  
3＋7＋12=22  3＋7＋19＝29  7＋12＋19＝38  3＋12＋19＝34  
现在，要求你计算出和为素数共有多少种。  
例如上例，只有一种的和为素数：3＋7＋19＝29

输入

每个测试文件只包含一组测试数据，每组输入的第一行输入两个整数n和k（1<=n<=20，k＜n）。  
第二行输入n个整数x1,x2,…,xn（1<=xi<=5000000）。

输出

对于每组输入数据，输出一个整数，表示满足条件的种数。

分析：求解k个数的和就用到DFS来求，然后每次选了k个数后，判断一下是否是素数，是的话，累加即可。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e2+7;
    const int maxn1 = 5e6+7;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    int a[maxn];
    bool vis[maxn1];
    int n,k,ans=0;
     
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
     
    bool check(int x)
    {
        rfup(i,2,sqrt(x))
        {
            if(x%i==0)
                return false;
        }
        return true;
    }
     
    void dfs(int index,int sum,int step)//当前从哪个数字开始选,当前已选数字的和,当前选了几个数
    {
        if(step>k)
            return;
        if(step==k&&check(sum))
        {
            ans++;
            return;
        }
        fup(i,index,n)
        {
            if(!vis[i])
            {
                vis[i]=true;
                dfs(i+1,sum+a[i],step+1);
                vis[i]=false;//回溯的时候退回标记
            }
        }
    }
     
    int main()
    {
        n=read();
        k=read();
        memset(vis,false,sizeof(vis));
        fup(i,0,n)  a[i]=read();
        dfs(0,0,0);
        printf("%d\n",ans);
        return 0;
    }