洛谷p1036-选数

, ,

题目链接

题解一：

此题是从n个数中选出k个不同的数字出来，然后按要求计算，看k个数的和有多少个数素数。
思考一下，无非难点就是，如何在n个数字中取出k个不同的数字，且不能重复。这里不能重复，一是说取出的数字不能相同，二是说取得方案不能重复。比如：
4 3
3 7 12 19
是说4个数字中取出3个数字，可以这样取
3 7 12
3 7 19
3 12 19
7 12 19
但是不能这样取：
3 3 7之类，
也不能这样取：
3 7 12
3 7 19
3 7 19
3 12 19
7 12 19
即：一组内不能有相同得数字，且不能有相同得两组。

好了，重点是：如何去重！
如果我们有规律得枚举，就能有效得避免重复列举得出现。也即达到了去重得目的。

我们要这样：
3 7 12
3 7 19
3 12 19
7 12 19
这样取，第一个位置，先取最小得数字3，后面递增取出。第一个位置选择为3得排列选完了，那么：第一个位置换为第二小得数字，再进行排列。即选7排列。
这样枚举，就有秩序了。

题解思路是用dfs，和上述文章中提到得降重得方法。
其中startx参数是用来储存当前升序排序时的初始值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;

bool isprime(int a){//判断素数

    for(int i=2;i*i<=a;i++){
        if(a%i==0)  return false;//如果能整除，说明不是素数
    }
    return true;//若能走到这里了，就说明不能整除，说明是素数
}

int n,k;//n为n个数，k为要选取的个数
int a[25];//存储输入的每个数字
bool vis[25];//标记这个数是否有没被选中
long long ans=0;//统计部分和为素数的情况个数

void dfs(int m,int sum,int startx){//递归处
    //m代表了select了多少个数
    //sum表示当前的和
    //startx表示升序排列的起始值，就是用上面所说得按一定规律有序得枚举

    if(m==k){//如果选完了的情况
        if(isprime(sum))    ans++;//如果选取的数的和不为素数，那么就ans++
        return ;
    }

    for(int i=startx;i<n;i++){ //这里就为上述中写的有规律的排列的实现
        if(vis[i])  continue;//如果被选过，直接进入下一次循环
        vis[i]=true;//如果没有被选过，选择之，即标记为选过
        dfs(m+1,sum+a[i],i+1);//递归
//m+1为被选择了的数的个数加一，sum+a[i]计算被选中的数字的和，i+1升序初始值加一，以防止重复排列
        vis[i]=false;//递归出来后，让这个数的标记重新设为未选择状态
    }
    return ;//这里，所有都已枚举完，直接返回
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)    cin>>a[i];//读入输入的数
    dfs(0,0,0);
    cout<<ans;//输出结果
    return 0;
}