Shell脚本 HTML框架 Apache Pivot教程 iic api csv datetime struct uiviewcontroller 3d stream vb6 mysql小数用什么类型 一兆等于多少字节 leach算法 centos7安装gcc vue与html5 pyhton中异常和模块 python环境搭建 python开发环境 python运算符优先级 python匹配字符串 java使用 java基础教学 怎么配置java环境 java基本数据结构 java单继承 javalist数组 怎么装linux系统 php语言入门 js选项卡 云管家 英雄联盟崩溃 dnf瞎子传说套选择 pr动态字幕 cf小号 js给标签添加属性 jquery手册 快递电子面单打印软件 色阶快捷键
当前位置: 首页 > 学习教程  > 编程语言

Acwing---1118. 分成互质组 (Java)_/DFS模板

2021/2/13 20:13:32 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

1118. 分成互质组 ①. 题目②. 思路③. 学习点④. 代码实现原题链接 ①. 题目 ②. 思路 这题和小猫爬山思路好像,同样是进行分组操作,枚举每一组可以放哪些元素。为了取得更少的组,按组为单位来枚举,如果当前组能填充下一个元素&…

1118. 分成互质组

  • ①. 题目
  • ②. 思路
  • ③. 学习点
  • ④. 代码实现

原题链接

①. 题目

在这里插入图片描述

②. 思路

  • 这题和小猫爬山思路好像,同样是进行分组操作,枚举每一组可以放哪些元素。为了取得更少的组,按组为单位来枚举,如果当前组能填充下一个元素, 就填充下一个元素,如果当前组不能填充下一个元素, 就新建一个组。使用欧几里得模板判断两个数得最大公约数是否大于1,检验新的数和组中的数是否互斥,当全部的数放完,更新组数量的最小值。 static void dfs(int u ,int k)放第u个数,共有k个组。遍历前面创建的集合 看当前数能否放进去,否则新开一个组,再进行DFS深搜,我使用一个集合当作一个组,回溯的时候直接remove最后一个添加进来的元素。

③. 学习点

欧几里得模板 || DFS爆搜模板

④. 代码实现

import java.util.ArrayList;
import java.util.Scanner;

public class _1118_分成互质组_DFS {
	/*
	 * 按组为单位来枚举,
	    如果当前组能填充下一个元素, 就填充下一个元素
	    如果当前组不能填充下一个元素, 就新建一个组
	 */
	static int N=11;
	static int n;
	static int[] a=new int[N]; //存放全部的数
	static boolean[] st=new boolean[N]; //标记是否访问过
	static ArrayList[] g=new ArrayList[N]; //使用一个集合数组,来分组
	static int res=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 n = sc.nextInt();
		 for (int i = 0; i <n; i++) {
			a[i]=sc.nextInt();
		}
		 //根据数据范围 直接创建10个组
		for(int i = 0;i <= 10;i ++) g[i] = new ArrayList<Integer>();
		dfs(0,0);
		System.out.println(res);
	}
	
	//欧几里得求两个数的最大公约数
	static int gcd(int a,int b) {
		return b==0?a:gcd(b,a%b);
	}
	//放第u个数,共有k个组
	static void dfs(int u ,int k) {
		if(u==n) {
			res=Math.min(res, k);
			return;
		}
		//遍历前面创建的集合 看当前数能否放进去
		for (int i = 0; i <k; i++) {
			if(check(a[u],g[i])) {
				g[i].add(a[u]);
				dfs(u+1,k);
				//回溯
				g[i].remove(g[i].size()-1);
			}
		}
		//新开一个组
		g[k].add(a[u]);
		dfs(u+1,k+1); //下一个数 组数+1
		//回溯
		g[k].remove(g[k].size()-1);
	}
	//检查x数能否在t集合中存活
	static boolean check(int x,ArrayList<Integer> list) {
		int len=list.size();
		for (int i = 0; i < len; i++) {
			if(gcd(x, list.get(i))>1) return false;
		}
		return true;
	}
}

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_700415.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?