P1036 选数
2024-08-24 03:40:37
题目描述
已知 nn 个整数 x_1,x_2,…,x_nx1,x2,…,xn,以及11个整数kk(k<nk<n)。从nn个整数中任选kk个整数相加,可分别得到一系列的和。例如当n=4,k=3n=4,k=3,44个整数分别为3,7,12,193,7,12,19时,可得全部的组合与它们的和为:
3+7+12=223+7+12=22
3+7+19=293+7+19=29
7+12+19=387+12+19=38
3+12+19=343+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=293+7+19=29。
输入输出格式
输入格式:
键盘输入,格式为:
n,kn,k(1 \le n \le 20,k<n1≤n≤20,k<n)
x_1,x_2,…,x_n (1 \le x_i \le 5000000)x1,x2,…,xn(1≤xi≤5000000)
输出格式:
屏幕输出,格式为: 11个整数(满足条件的种数)。
输入输出样例
输入样例#1: 复制
4 3
3 7 12 19
输出样例#1: 复制
1
思路: 通过题目给出的例子分析条件, 若满足选出的数的个数为3, 并且这三个数之和为素数, 即可视为1种情况
先写出判断素数的函数(这里不用欧拉线性筛也能过)
然后再考虑如何从n个数中选择k个数使这k个数的和为素数
想起了(李白打酒), 于是采用递归的策略, 传递三个参数(当前数组的下标, 当前和, 选择的第几个数)
递归时注意要分选择这个数, 不选择这个数两种情况, 若选择该数, 则当前数组下标+1, 当前和+该数值, 选择的个数+1, 若不选择该数, 则当前数组下标+1, 当前和不变, 选择的个数不变
通过递归来计算出total(总方案数)
#include<iostream>
#include<cmath>
using namespace std; int n, k, total, a[30]; bool is_prime(int x)
{
for(int i = 2; i <= sqrt(x); ++i)
if(x % i == 0)
return false;
return true;
} void dfs(int step, int sum, int count)
{
if(step == n + 1 || count == k)
{
if(is_prime(sum) && count == k)
total++;
return ;
}
dfs(step + 1, sum + a[step], count + 1);
dfs(step + 1, sum, count);
return ;
} int main()
{
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
dfs(1, 0, 0);
cout << total << endl;
return 0;
}
最新文章
- 使用jenkins配置.net mvc网站进行持续集成三
- 数组,集合分割函数,join()
- Lintcode 85. 在二叉查找树中插入节点
- Xcode相关整理
- window2008 r2 负载均衡
- 20160621-BAPI 更改外向DN&;更改拣配
- HtmlAgilityPack下载开启压缩的页面乱码
- 在myeclipse文件中如何创建properties类型的文件,从而连接数据库
- Linux系统批量化安装部署之Cobbler
- 20155224聂小益 - 我的技能与C语言学习
- UVALive 6124 Hexagon Perplexagon 题解
- Struts2.x jsp页面无法使用jsp:forward跳转到action
- java高级:weakReference
- 100个linux站点
- 【转载】python 模块 - random生成随机数模块
- php-GD库的函数(二)
- 设计模式 State模式 机器的情况下用自己的主动性
- E: 无法获取锁 /var/lib/apt/lists/lock - open (11: Resource temporarily unavailable)解决方法
- Web 前台优化
- 了解Vue.js
热门文章
- 导入json文件报错,TypeError expected string or buffer
- vue.js入门环境搭建
- 如何 安装Yii2的高级应用程序模板
- python17 多线程学习
- 数据结构---Java---有序数组
- Spring集成Quartz的3种方式
- jquery mobile - select and input - horizontal - in same line
- 提交表单之前对表单进行检查的方法 onsubmit=";return checkSubmit();";
- Hadoop学习笔记(3) Hadoop文件系统一
- GitKraken使用教程-基础部分(1)