国内做网站建设好的,wordpress收发邮件功能,网站开发背景图片,我是这样做网站的米课P1036 [NOIP 2002 普及组] 选数
题目描述
已知 nnn 个整数 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_nx1,x2,⋯,xn#xff0c;以及 111 个整数 kkk#xff08;knknkn#xff09;。从 nnn 个整数中任选 kkk 个整数相加#xff0c;可分别得到一系列的和。例如当 n4n…P1036 [NOIP 2002 普及组] 选数
题目描述
已知 nnn 个整数 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_nx1,x2,⋯,xn以及 111 个整数 kkkknknkn。从 nnn 个整数中任选 kkk 个整数相加可分别得到一系列的和。例如当 n4n4n4k3k3k3444 个整数分别为 3,7,12,193,7,12,193,7,12,19 时可得全部的组合与它们的和为
371222371222371222
371929371929371929
712193871219387121938
312193431219343121934
现在要求你计算出和为素数共有多少种。
例如上例只有一种的和为素数371929371929371929。
输入格式
第一行两个空格隔开的整数 n,kn,kn,k1≤n≤201 \le n \le 201≤n≤20knknkn。
第二行 nnn 个整数分别为 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_nx1,x2,⋯,xn1≤xi≤5×1061 \le x_i \le 5\times 10^61≤xi≤5×106。
输出格式
输出一个整数表示种类数。
输入输出样例 #1
输入 #1
4 3
3 7 12 19输出 #1
1说明/提示
【题目来源】
NOIP 2002 普及组第二题
本题在前面已经用好几种方法做过了。这里用递归的方式来做。
#includecstdio
#includevector
using namespace std;
int n,k;
vectorint a;
int cnt;
bool isPrime(int sum)
{if(sum1) return false;for(int i2;i*isum;i){if(sum%i0)return false;}return true;} void dfs(int u,int cnt_n,int sum){if(cnt_nk){if(isPrime(sum))cnt;return ;}if(un) return;dfs(u1,cnt_n1,suma[u]);dfs(u1,cnt_n,sum);} int main(){scanf(%d%d,n,k);a.resize(n);for(int i0;in;i)scanf(%d,a[i]);cnt0; dfs(0,0,0);printf(%d\n,cnt);return 0;}if(un) return; 这一句话很重要。
