首页 > 其他分享 >洛谷P1036

洛谷P1036

时间:2023-03-04 17:12:04浏览次数:53  
标签:arr return int 质数 P1036 param ++ 洛谷

P1036 [NOIP2002 普及组] 选数

典型的dfs,建议书写递归代码时层次应与形参列表中自己所标志的层次相对应,否则很容易混乱

import java.util.Scanner;

public class P1036 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			dfs(arr, k, 1, arr[i], i);
		}
		System.out.println(num);
	}

	static int num = 0;// 质数的个数       java中的全局变量

	/**
	 * @param arr   存放数据的数组
	 * @param k     挑选 k 个整数
	 * @param count 表示递归层数,也就是选择数据的个数
	 * @param sum   表示上层递归所选数字之和与此层所选数字之和
	 * @param index 所选数字索引
	 */
	private static void dfs(int[] arr, int k, int count, int sum, int index) {
		if (count == k) {
			if (isPrime(sum)) {
				num++;
			}
			return;
		}
		for (int i = index + 1; i < arr.length; i++) {
			dfs(arr, k, count + 1, sum + arr[i], i);
		}
	}

	/**
	 * 判断一个数是否为质数
	 * 
	 * @param n 待判断数字
	 * @return 是质数返回 true 否则返回 false
	 */
	public static boolean isPrime(int n) {
		if (n == 1) {
			return false;
		}
		for (int i = 2; i < n; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

所涉及到的还有质数筛的内容

测试案例:

4 3
10 11 12 13
0

image-20230304165936019

标签:arr,return,int,质数,P1036,param,++,洛谷
From: https://www.cnblogs.com/ChuenSan/p/17178599.html

相关文章

  • 洛谷P1030
    P1030[NOIP2001普及组]求先序排列思路:由后序遍历序列求出根由中序遍历序列求出左右子树递归上述12直到中序/后续遍历序列为空publicclassP1030{//已......
  • 洛谷P1149 [NOIP2008 提高组] 火柴棒等式
    这道题就是一个经典的暴力枚举题意是输出一共有的火柴根数,输出这些火柴棒用完可以有多少拼法下面,我们来数一数拼成十个数和两个符号(’+‘&&’=‘)各用几根火柴棒0要用......
  • 洛谷P1149 [NOIP2008 提高组] 火柴棒等式
    这道题其实很简单只是个暴力枚举!!!题目大致意思是说给你一堆火柴棒,两个符号(‘+’&&‘-’)。第一个数字‘0’用了6根火柴棒,‘1’用了2根火柴棒,依此类推......这样,我们就能......
  • 洛谷 P4048更新题面
    [JSOI2010]冷冻波题目描述WJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能FrozenNova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成......
  • 洛谷P4051 [JSOI2007]字符加密 题解 后缀数组sa的应用
    题目链接:https://www.luogu.com.cn/problem/P4051题目大意:给定一个长度为\(n\)的字符串\(s\),每次将\(s\)的首字符取出放到末尾……这样能得到\(n\)个字符串。将......
  • 位运算-洛谷P1469 找筷子
    位运算的符号:与(&) and当两个数在二进制下对应位数上均为 11 时,得到的结果为 11.或(|) or当两个数在二进制下对应位数上有一个为 11 时,得到的结果为 11.......
  • [洛谷]P5401 [CTS2019] 珍珠 题解
    [洛谷]P5401[CTS2019]珍珠题解题意概述有\(D\)种珍珠,每种有无限颗,现在等概率的从\(D\)种珍珠中抽\(n\)次珍珠,每次抽\(1\)个珍珠,记第\(i\)种珍珠最后一共抽......
  • 【LGR-(-17)】洛谷入门赛 #8 个人赛后总结
    【LGR-(-17)】洛谷入门赛#8个人赛后总结前言这是本蒟蒻的第一篇博客,也是对第一次参加洛谷比赛的总结,如果有错误请指出。引子本蒟蒻第一次看到比赛时就迫不及待的报了......
  • 洛谷P1149
    [洛谷P1149]([P1149NOIP2008提高组]火柴棒等式-洛谷|计算机科学教育新生态(luogu.com.cn))publicclassP1149{ publicstaticvoidmain(String[]args){ S......
  • 洛谷P8471 [Aya Round 1 F] 琪露诺的选择题
    原题传送门题目描述有2⋅n道选择题,每题有A和B两个选项。正确答案可以表示为一个长度为2⋅n的字符串。现在你要构造出一份作答(长度同样为2⋅n的字符串),其中恰好......