[NOIP 2002 普及组] 选数 题解

· · 题解

UPD:被 Hack 了，寻求更快速的 dfs。

题目传送门

题目大意

有 n 个数，问有几组 k 个数的和为质数。

思路

从第一个开始搜索，直到个数等于 k 时再判断，若为质数，答案加一，再回溯。

::::info[原代码]

#include<iostream>
using namespace std;
int n,k,x[21],s[20],answer;
bool prime(int y){//判断是否为质数
    if(y<2)return 0;//特判
    if(y<4)return 1;//特判
    for(int i=2;i*i<=y;i++){
        if(y%i==0)return 0;
    }
    return 1;
}
void search(int sum,int num){//搜索
    if(sum==k){//若已经填完
        int ans=0;
        for(int i=1;i<=k;i++)ans+=s[i];
        if(prime(ans))answer++;//判断和是否为质数
        return ;
    }
    for(int i=num;i+(k-(sum+1))<=n;i++){//i+(k-(sum+1))<=n是判断i之后是否还有足够使填的数等于k的个数
        s[sum+1]=x[i];//填入
        search(sum+1,i+1);//继续搜索
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i];//输入
    search(0,1);//开始搜索
    cout<<answer;//输出结果
    return 0;
}

:::: 然而 Hack 数据运行时间会超过 1000ms。

考虑在判断素数上进行优化。

在判断素数时，取模得出为合数的模数是素数，因为如果是合数，它的因子早被我们判断过了。

我们可以将数分类：6k,6k+1,6k+2,6k+3,6k+4,6k+5。显然的，只有 6k+1 和 6k+5 可能是素数（当然这个数要 \ge6）。

于是我们就去掉了很多不必要的判断，剪枝成功。

::::info[剪枝后判断素数代码]

bool prime(int y){
    if(y<2)return 0;//特判
    if(y<4)return 1;//特判
    if(y%2==0||y%3==0||y%5==0)return 0;//特判
    int i=7;//代表第一个6k+1
    while(i*i<=y){
        if(y%i==0)return 0;
        i+=4;//转换成6k+5
        if(y%i==0)return 0;
        i+=2;//转换回6k+1
    }
    return 1;
}

:::: 当然，这份代码还有一些可剪枝的地方，这里就不介绍了。