P1036 [NOIP 2002 普及组] 选数

题目描述

已知 n 个整数 x1,x2,⋯,x**n，以及 1 个整数 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,⋯,x**n（1≤x**i≤5×106）。

输出格式

输出一个整数，表示种类数。

输入输出样例

输入 #1复制运行

4 3
3 7 12 19

输出 #1复制运行

1

说明/提示

【题目来源】

NOIP 2002 普及组第二题

---

---

Code

//自己优化版本  86分（已经够用了）#include<bits/stdc++.h>
using namespace std;
vector<vector<long long>> result;
vector<long long> path;   
long long k;
long long n;
//dfs  获得所有组合（从n个数里面选k个数）
void dfs(long long start,vector<long long>& x)
{long long size = path.size(); if(size==k){result.push_back(path);return;}for(long long i=start;n-i>=k-size;i++){  //剪枝path.push_back(x[i]);dfs(i+1,x);path.pop_back();}
}
//判断是否是素数
bool Prime(long long val) 
{if(val<2) return false;if(val==2) return true;if (val % 2 == 0) return false; // 跳过偶数，提升效率long long limit = sqrt(val);  // 用整数平方根，避免pow的精度误差for(long long i=3;i<=limit;i+=2){  // 改：从3开始，步长2 (因为前面已经跳过偶数了，若对2求余不为0，那么对任何偶数求余都不为0)if(val%i==0){return false;}}return true;
}
int main(void)
{cin >> n >> k;vector<long long> x(n,0);for(long long i =0;i<n;i++){cin >> x[i];}dfs(0,x);vector<long long> sum(result.size(),0);//用sum数组记录每一个组合的和for(long long i=0;i<result.size();i++){for(long long j=0;j<result[i].size();j++){sum[i]+=result[i][j];}}int ans = 0;for(long long i=0;i<sum.size();i++){if(Prime(sum[i])){ans++;}}cout << ans << "\n";return 0;
}

• dfs遍历得到所有组合（注意是组合，不要搞成排列）
• dfs中的剪枝n-i>=k-size ，提前结束不可能选够 k 个数的循环，少做无用功！公式：n - i >= 剩下要选的个数
• 素数的剪枝（非常巧妙，可通用）