首页 > 代码库 > 1008 选数 2002年NOIP全国联赛普及组
1008 选数 2002年NOIP全国联赛普及组
1008 选数
2002年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
已知 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)。
输入描述 Input Description
键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)
输出描述 Output Description
屏幕输出,格式为:
一个整数(满足条件的种数)。
样例输入 Sample Input
4 3
3 7 12 19
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
(1<=n<=20,k<n)
(1<=xi<=5000000)
注意:可以用记录前驱结点的方法来判重
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=10001; 7 int a[MAXN]; 8 int tot=0; 9 int ans[MAXN];10 int vis[MAXN];11 int now=1;12 int n,m;13 int num;14 int flag[MAXN];15 int pd(int n)16 {17 for(int i=2;i<=sqrt(n);i++)18 {19 if(n%i==0)20 return 0;21 }22 return 1;23 }24 void dfs(int p,int ed)25 {26 if(p==m)27 {28 int maxn=0;29 for(int i=1;i<=m;i++)30 {31 maxn=maxn+ans[i];32 }33 if(pd(maxn)==1)34 {35 num++;36 }37 return ;38 }39 for(int i=ed;i<=n;i++)40 {41 ans[now]=a[i];42 now++;43 flag[i]=1;44 dfs(p+1,i+1);45 now--;46 ans[now]=0;47 flag[i]=0;48 }49 }50 int main()51 {52 scanf("%d%d",&n,&m);53 for(int i=1;i<=n;i++)54 {55 scanf("%d",&a[i]);56 tot=tot+a[i];57 }58 /*for(int i=2;i<=sqrt(tot);i++)59 {60 if(vis[i]==0)61 {62 for(int j=i*i;j<=tot;j=j+i)63 {64 vis[j]=1; 65 } 66 67 }68 }*/69 dfs(0,1);70 printf("%d",num);71 return 0;72 }
1008 选数 2002年NOIP全国联赛普及组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。