牛客小白月赛88

news/2024/4/15 4:58:01/文章来源:https://blog.csdn.net/Xing_ke/article/details/136572821

E.多重映射

解题思路

  • 对集合进行整体操作,集合大小只增不减,问最后集合标号
  • 维护集合,考虑并查集
  • 但直接用并差集维护会有以下问题:
  • 当前集合变标号,可能会和之前标号相同,则进行并查集find操作时,会接上之前的变换
  • 为消除其影响,考虑加入时间戳,后面新产生的标号与之前的不同
  • 进行操作时,若x没有则跳过
  • y没有,则产生新的y集合,y对应的时间戳++
  • 若有,则合并集合,时间戳不变
  • fa[Node(x,tim_x)]=Node(y,tim_y)
  • find时,带上时间戳
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;//implements Runnable
public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int N=2000000;static int n=0;static int m=0;static class Node{int x;int y;public Node(int u,int v) {x=u;y=v;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Node may = (Node) o;return x == may.x && y==may.y;}@Overridepublic int hashCode() {return Objects.hash(x, y);}}static HashMap<Node, Node> fa=new HashMap<Node, Node>();static Node find(Node x) {//跟正常并查集一样if(x.x==fa.get(x).x&&x.y==fa.get(x).y)return x;else {Node f=fa.get(x);Node ff=find(f);fa.put(f, ff);return ff;}}static int[] a=new int[N+1];static int[] x=new int[N+1];static int[] y=new int[N+1];static boolean[] hs=new boolean[N+1];static int[] t=new int[N+1];public static void main(String[] args) throws Exception{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));	int T=input.nextInt();while(T>0) {n=input.nextInt();m=input.nextInt();for(int i=1;i<=n;++i) {a[i]=input.nextInt();Node ro=new Node(a[i], 0);fa.put(ro, ro);//初始化,重复添无影响hs[a[i]]=true;}for(int i=1;i<=m;++i) {x[i]=input.nextInt();y[i]=input.nextInt();Node lo=new Node(x[i], 0);Node ro=new Node(y[i], 0);fa.put(lo, lo);fa.put(ro, ro);//初始化,重复添无影响}
//			out.print(fa.get(new Node(1, 0)));for(int i=1;i<=m;++i) {int l=x[i];int r=y[i];if(!hs[l])continue;if(!hs[r]) {//与之前区别t[r]++;}hs[l]=false;hs[r]=true;Node lo=new Node(l, t[l]);Node ro=new Node(r, t[r]);fa.put(lo, ro);
//				out.print(fa.get(ro));fa.put(ro, ro);//集合头自己指自己,初始化,重复添无影响}//			out.print(fa.get(new Node(1, 0)));for(int i=1;i<=n;++i) {Node fx=find(new Node(a[i], 0));out.print(fx.x+" ");}out.println();//清空for(int i=1;i<=n;++i) {hs[a[i]]=false;t[a[i]]=0;}for(int i=1;i<=m;++i) {hs[x[i]]=false;t[x[i]]=0;hs[y[i]]=false;t[y[i]]=0;}fa.clear();T--;}out.flush();out.close();}
//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Main(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_998835.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++ 智能指针深度剖析

文章目录 1. 前言2. 为什么需要智能指针&#xff1f;3. 内存泄漏3.1 内存泄漏的概念及危害3.2 内存泄漏的分类3.3 如何检测内存泄漏3.4 如何避免内存泄漏 4. 智能指针的使用及原理4.1 RAII思想4.2 智能指针的原理4.3 C智能指针发展历史4.4 std::auto_ptr4.5 std::unique_ptr4.6…

驱动OLED SSD1306的笔记

这里用的OLED模块是SSD1306的 硬件 SSD1306只支持3.3V供电SSD1306支持4中接口&#xff1a;6800、 8080&#xff0c;SPI&#xff0c;IIC通过引脚BS1和BS2接口的模式。如果是IIC模式&#xff0c;SCL对应D0&#xff0c;SDA对应D1,D2(需要把D1和D2连在一起然后接入MCU的SDA) OLED…

AIOPS:Zabbix结合讯飞星火做自动化告警+邮件通知并基于人工智能提供解决方案

目前Zabbix官方已经提供Zabbix+ChatGPT的解决方案 ChatGPT一周年,你充分利用了吗?Zabbix+ChatGPT,轻松化解告警! 但是由于需要魔法等其他因素,比较不稳定,遂决定使用国内模型,这里我挑选的是讯飞星火,基于我之前的文档,在此基础上通过Zabbix的告警脚本实现调用AI模型…

二维码门楼牌管理系统应用场景:推动旅游与文化产业的智慧化升级

文章目录 前言一、二维码门楼牌管理系统在旅游领域的应用二、二维码门楼牌管理系统在文化产业的应用三、结语 前言 随着信息技术的不断发展&#xff0c;二维码门楼牌管理系统作为一种创新的信息化手段&#xff0c;正在逐渐渗透到旅游和文化领域。它通过为文化景点、旅游景点和…

2024 批量下载公众号文章内容/阅读数/在看数/点赞数/留言数/粉丝数导出pdf文章备份(带留言):公众号爱在冰川近3000篇历史文章在线查看,找文章方便了

关于公众号文章批量下载&#xff0c;我之前写过很多文章&#xff1a; 视频更新版&#xff1a;批量下载公众号文章内容/话题/图片/封面/音频/视频&#xff0c;导出html&#xff0c;pdf&#xff0c;excel包含阅读数/点赞数/留言数 2021陶博士2006/caoz的梦呓/刘备我祖/六神读金…

qnx启动中控屏黑屏

bmetrics_service boot metrics service, 用于记录统计启动性能信息,读取/dev/bmetrics可以获取到这些信息 # use memorydump memorydump Sets the debug cookies, copies MMU info into reset_info asinfo, sets the secure monitor(TZ) dump buffer, starts tracelogger Usa…

菜鸟笔记-14散点图标记形状

大家在学习Python科研绘图中&#xff0c;总会涉及散点图标记形状&#xff0c;为了方便大家学习应用&#xff0c;博主通过学习搜集&#xff0c;将这部分技巧总结如下。 14.1默认散点图 14.1.1图像呈现 14.1.2绘图代码 import numpy as np # 导入numpy库&#xff0c;用于处理…

CDN(内容分发网络):加速网站加载与优化用户体验

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

Vue | 基于 vue-admin-template 项目的跨域问题解决方法

目录 一、现存问题 二、解决方法 2.1 修改的第一个地方 2.2 修改的第二个地方 2.3 修改的第三个地方 自存 一、现存问题 报错截图如下&#xff1a; 二、解决方法 2.1 修改的第一个地方 在 .env.development 文件中&#xff1a; # base api # VUE_APP_BASE_API /d…

基于Jupyter快速入门Python,Numpy,Scipy,Matplotlib

文章目录 Jupyter 和 Colab 笔记本PythonPython 版本基础数据类型数字Numbers布尔值Booleans字符串Strings 容器列表List字典Dictionaries集合Sets元组Tuples 函数类 Numpy数组Array数组索引Array indexing数据类型DatatypesArray math广播Broadcasting Scipy图像操作MATLAB文件…

智慧城市中的数字孪生:构建城市管理的未来框架

目录 一、引言 二、数字孪生技术概述 三、数字孪生技术在智慧城市中的应用 1、实时监测与预警 2、模拟与优化 3、智能化决策 4、协同与共享 四、数字孪生技术构建城市管理的未来框架的价值 1、提高管理效率 2、优化资源配置 3、提升公共服务水平 4、增强应对突发事…

耐腐蚀特氟龙塑料材质PFA烧杯超纯试剂反应杯

PFA烧杯在实验过程中可作为储酸容器或涉及强酸强碱类实验的反应容器&#xff0c;用于盛放样品、试剂&#xff0c;也可搭配电热板加热、蒸煮、赶酸用。 外壁均有凸起刻度&#xff0c;直筒设计&#xff0c;带翻边&#xff0c;便于夹持和移动&#xff0c;边沿有嘴&#xff0c;便于…

springboot+xjar加密打包部署教程

需求背景 为了跟上时代的步伐&#xff0c;为了更好的生存。开个玩笑&#xff0c;就是心血来潮&#xff0c;使用xjar加密部署jar包&#xff0c;于是就测试一下。 xjar教程 1-maven配置文件修改 首先找到自己ideal配置的maven文件夹&#xff0c;然后找到apache-maven-3.9.3\co…

C# 多线程(3)——线程池

文章目录 1 定义2 线程池使用3 安全取消线程池中任务 1 定义 线程是计算机宝贵的资源&#xff0c;频繁的创建和销毁线程将会大量的占用计算机资源&#xff08;为每个线程单独分配内存空间&#xff0c;并且多线程下的CPU时间片的切换也会耗费一定的时间&#xff09;。为了充分利…

Supplementary Influence Maximization Problem in Social Networks

本论文发表于 IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS, VOL. 11, NO. 1, FEBRUARY 2024 Abstract 由于在病毒式营销中的重要应用&#xff0c;影响力最大化&#xff08;IM&#xff09;已成为一个经过充分研究的问题。它的目的是找到一小部分初始用户&#xff0c;以…

基于Python3的数据结构与算法 - 12 数据结构(列表和栈)

目录 一、引入 二、分类 三、列表 1. C语言中数组的存储方式 2. Python中列表的存储方式 四、栈 1. 栈的应用 -- 括号匹配问题 一、引入 定义&#xff1a;数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说&#x…

异常-Exception

文章目录 异常-Exception常见的运行时异常NullPointerException&#xff08;空指针异常&#xff09;ArithmeticException&#xff08;数学运算异常&#xff09;ArrayIndexOutOfBoundsException&#xff08;数组下标越界异常&#xff09;ClassCastException&#xff08;类型转换…

浏览器修改接口返回数据展示在页面上

前端自己调试&#xff0c;想修改接口返回来的数据&#xff0c;然后展示在页面上 举例 接口返回了数据&#xff0c;想要修改此数据 这时就可以修改数据了&#xff0c;修改完成保存 然后刷新页面就会使用本地保存的数据了

Linux第68步_旧字符设备驱动的一般模板

file_operations结构体中的函数就是我们要实现的具体操作函数。 注意&#xff1a; register_chrdev()和 unregister_chrdev()这两个函数是老版本驱动使用的。现在新字符设备驱动已经不再使用这两个函数&#xff0c;而是使用Linux内核推荐的新字符设备驱动API函数。 1、创建C…

“TXT文本编辑专家:一键查找,多关键字,高效办公新选择“

办公场景中&#xff0c;我们经常需要处理大量的TXT文本文件&#xff0c;从中筛选出包含特定关键字的内容。传统的文本编辑软件往往功能单一&#xff0c;无法满足多关键字、多文件的同时查找需求。现在&#xff0c;一款专为TXT文本编辑设计的办公软件应运而生&#xff0c;它将为…