洛谷—— P1036 选数 || Vijos——选数
2024-08-31 14:35:57
https://vijos.org/p/1128||
https://www.luogu.org/problem/show?pid=1036#sub
描述
已知 n 个整数 x1,x2,…,xn,以及一个整数 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)
x1,x2,…,xn (1<=xi<=5000000)
输出格式
一个整数(满足条件的种数)。
样例1
样例输入1
4 3
3 7 12 19
样例输出1
1
限制
每个测试点1s
来源
noip2002普及组第二题
水一下普及组
#include <cstdio> using namespace std; int n,k,sum,ans;
int num[]; bool jud(int x)
{
for(int i=;i*i<=x;i++)
if(x%i==) return false;
return true;
} void DFS(int pos,int cnt)
{
if(cnt==k&&jud(sum))
{
ans++;
return ;
}
for(int i=pos+;i<=n;i++)
{
sum+=num[i];
DFS(i,cnt+);
sum-=num[i];
}
} int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++) scanf("%d",num+i);
DFS(,);
printf("%d",ans);
return ;
}
最新文章
- 设计模式--观察者模式初探和java Observable模式
- JDBC连接各种数据库的地址名称
- 当display=none时,元素和子元素高度为0的解决办法
- css3 filter属性在项目中的应用
- enum与typedef enum的用法
- Android IOS WebRTC 音视频开发总结(二九)-- 安卓噪声消除交流
- Win+R快速打开你的应用程序
- 济南学习 Day 3 T1 am
- substring函数——sql
- CBQW ---分组表单展示
- perl正则表达式第二周笔记
- 【LeetCode题意分析&;解答】39. Combination Sum
- 分享一个javascript alert精简框架
- WinForm笔记
- Deep Q-Network 学习笔记(一)—— Q-Learning 学习与实现过程中碰到的一些坑
- 一个简单的ruby生成器例子(用连续体Continuation实现)
- mysql百万级全文索引及match快速查找
- jQuery_$方法、属性、点击切换
- HDFS的命令
- TCP/IP 数据包报文格式(IP包、TCP报头、UDP报头)(转)