P1036 [NOIP2002 普及组] 选数
题目描述
已知 nn 个整数 x_1,x_2,\cdots,x_nx1,x2,⋯,xn,以及 11 个整数 kk(k<nk<n)。从 nn 个整数中任选 kk 个整数相加,可分别得到一系列的和。例如当 n=4n=4,k=3k=3,44 个整数分别为 3,7,12,193,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29。
输入格式
第一行两个空格隔开的整数 n,kn,k(1 \le n \le 201≤n≤20,k<nk<n)。
第二行 nn 个整数,分别为 x_1,x_2,\cdots,x_nx1,x2,⋯,xn(1 \le x_i \le 5\times 10^61≤xi≤5×106)。
输出格式
输出一个整数,表示种类数。
输入输出样例
输入 #1复制
4 3
3 7 12 19
输出 #1复制
1
说明/提示
【题目来源】
NOIP 2002 普及组第二题
解题思路:
这题我看网上主要是就是通过dfs,比如输入
4 3
3 7 12 19
在dfs哪里,m代表现在加了几次,sum代表加的和,statrt,代表他下一个要加的索引位置,比如第一组数组就是:
1 3 2
1 7 3
1 12 4
1 19 5
会进行这4次递归,我通过第一组递归讲1 3 2,那么他第二次就是2 10 3,其中的10—>3+7,为什么要加7,因为1 3 2最后一个要代表他加的位置,那就是2,进行这次递归后就是2 10 3—>3 22 4,此时m是3,然后代表已经加3次了,可以进行素数判断了,跳出递归,这只是1 3 2里的其中一组数据,还有一组就是2 10 3->3 29 4,此时m=3,可以进行素数判断了
废话不多说,上代码
import java.util.Scanner;
public class Main {
static int ans = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = in.nextInt();
}
dfs(0, 0, 1, arr, k);
System.out.println(ans);
}
public static void dfs(int m, int sum, int start, int[] arr, int k) {
if (m == k) {
if (isPrime(sum)) {
ans++;
}
return;
}
for (int i = start; i < arr.length; i++) {
dfs(m + 1, sum + arr[i], i + 1, arr, k);
}
}
public static boolean isPrime(int num)//判断质数
{
for (int i = 2 ; i <= Math.sqrt(num) ; i++)
{
if (num % i == 0)
{
return false;
}
}
return true;
}
}
空空如也!