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

· · 题解

题意简述

给定 n 个整数，从中选 k 个，问这 k 个数相加的和为素数有几种情况。

思路梳理

简单 dfs 模板。

调用 dfs，每次调用时先判断选到第几个数了，如果已经选了 k 个数，判断质数并将答案记录；否则继续选。深搜结束后输出答案。

避坑指南

  1. 只需要存数字之和，不需要把每个数字存下来。
  2. 设上一次选的数下标为 x ，这一次下标只需要从 x+1 进行枚举，否则会重复。
  3. 注意 1 不是质数，判断质数时不要写错。

AC Code

我知道你们只看这个！

#include<iostream>
#include<cmath>
using namespace std;
int n,k,a[30],ans=0;
bool prime(int y)//质数判断，最简单的筛法
{
    if(y<2)return false;
    for(int i=2;i<=sqrt(y);i++)//注意是<=
    if(y%i==0)//如果能整除，则不是质数
    return false;

    return true;//是质数
}
void dfs(int x,int sum,int now)//深搜
//x代表这次选的是第几个数，sum代表现在所选数的总和，now代表最新选的那个数在a数组里的下标。
{   
    if(x==k+1)//如果已经选了k个数
    {
        if(prime(sum))//如果这k个数的和是质数
        ans++;//将答案+1
    }
    else//如果没有k个数，就继续选 
    {
        for(int i=now;i<=n;i++)//枚举从now到n的所有下标 
        {
            dfs(x+1,sum+a[i],i+1);//选择a[i] 
        }
    }
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];//按题意输入 
    }
    dfs(1,0,1);//调用深搜函数 
    cout<<ans<<endl;//输出答案 
    return 0;//收官 
}

求赞 QWQ~