当前位置: 首页 > news >正文

并查集模板:食物链详解


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {static int N = 50010;static int n,m; //n个动物,m局判断static int[] p = new int[N];    //p[i]是i的根节点static int[] d = new int[N];    //d[i]表示i到其父节点的距离,通过find函数会路径压缩变成到根节点的具体static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));public static int find(int x){  //返回根节点if (p[x] != x){ //如果你要找的节点不仅仅只有自己,就要往上找,去找自己的祖宗//先递归得到根节点//假设此时已经形成了一段树,p[x] = N,从p[1]开始找,一直让x增到N即p[N] = N;int t = find(p[x]);//调用结束的x是 根节点N - 1,根节点的d[N]不需要更新//从根节点开始的孩子开始,回溯,路径压缩更新该节点到根节点的距离//再调用find方法前,会设置d[p[x]]为1d[x] += d[p[x]];p[x] = t;   //最后再更新find(x)~find(N-1)的父节点为N}//最后返回根节点Nreturn p[x];}public static void main(String[] args) throws IOException {String[] init = in.readLine().split(" ");n = Integer.parseInt(init[0]);m = Integer.parseInt(init[1]);//初始化并查集for (int i = 0; i < n; i++) {p[i] = i;}int res = 0;    //说谎话的个数while (m-- > 0){init = in.readLine().split(" ");int t= Integer.parseInt(init[0]);int x= Integer.parseInt(init[1]);int y= Integer.parseInt(init[2]);if (x > n || y > n) res ++;else {int px = find(x),py = find(y);  //找到这两个树的根节点if (t == 1)//同类{//作为同类如果再一个集合关系里,他们的等级相差%3!= 0if (px == py &&  (d[x] - d[y]) % 3 != 0) res ++;else if (px != py){ //这里要用else if 不能直接用else,同类也可能走到这//不同类,把它俩放在一个集合里p[px] = py; //py作为px的父亲d[px] = (d[y] - d[x]) % 3;}}else {//吃,如果在一个集合里,同类的化,x 吃 y//x在%3的情况下要比y多一个等级if (px == py && (d[x] - d[y] - 1) % 3 != 0) res ++;else if (px != py){//不同一个集合,把他们放在一起,x比y高一个等级p[px] = p[y];//在调用find之前会先走这里,把根节点的到它的孩子距离设置成1d[px] = (d[y] - d[x] + 1) % 3;}}}}System.out.println(res);}
}

相关文章:

并查集模板:食物链详解

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class Main {static int N 50010;static int n,m; //n个动物,m局判断static int[] p new int[N]; //p[i]是i的根节点static int[] d new int[N]; //d[i]表示i到…...

使用WAF防御网络上的隐蔽威胁之反序列化攻击

​ 什么是反序列化 反序列化是将数据结构或对象状态从某种格式转换回对象的过程。这种格式通常是二进制流或者字符串&#xff08;如JSON、XML&#xff09;&#xff0c;它是对象序列化&#xff08;即对象转换为可存储或可传输格式&#xff09;的逆过程。 反序列化的安全风险 反…...

05. 交换机的基本配置

文章目录 一. 初识交换机1.1. 交换机的概述1.2. Ethernet_ll格式1.3. MAC分类1.4. 冲突域1.5. 广播域1.6. 交换机的原理1.7. 交换机的3种转发行为 二. 初识ARP2.1. ARP概述2.2. ARP报文格式2.3. ARP的分类2.4. 免费ARP的作用 三. 实验专题3.1. 实验1&#xff1a;交换机的基本原…...

yolo将标签数据打到原图上形成目标框

第一章 目标&#xff1a;为了查看自己在标注标签时是否准确&#xff0c;写了这段代码来将标注的框打到原图上 第二章 步骤&#xff1a;进行反归一化得到坐标画出矩形框 第二行是目标图片对应的txt,第三行是目标图片 第三章 全部代码如下&#xff1a; import cv2 import …...

002-00-02【大红ai源码】dolphinscheduler3.2.0 源码环境搭建------by孤山村头王大爷家女儿大红

【ai阅读源码-dolphinscheduler】 DolphinScheduler 开发手册1、软件要求2、克隆代码库3、编译打包4、代码风格5、新建数据库&#xff0c;导入元数据。6&#xff0c; 启动后端6.1 启动api-server 6.2 启动master-server6.3 启动worker-server 7 启动前端 DolphinScheduler 开发…...

python-自动化篇-运维-监控-如何使⽤Python处理和解析⽇志⽂件?-实操记录

文章目录 1. 选择日志文件格式&#xff1a; 确定要处理的日志文件的格式。不同的日志文件可能具有不同的格式&#xff0c;如文本日志、CSV、JSON、XML等。了解日志文件的格式对解析⾮常重要。2. 打开日志文件&#xff1a; 使⽤Python的文件操作功能打开日志文件&#xff0c;以便…...

代码随想录算法训练营DAY6 | 哈希表(1)

DAY5休息一天&#xff0c;今天重启~ 哈希表理论基础&#xff1a;代码随想录 Java hash实现 &#xff1a;java 哈希表-CSDN博客 一、LeetCode 242 有效的字母异位词 题目链接&#xff1a;242.有效的字母异位词 思路&#xff1a;设置字典 class Solution {public boolean isAnag…...

【嵌入式学习】C++QT-Day3-C++基础

笔记 见我的博客&#xff1a;https://lingjun.life/wiki/EmbeddedNote/19Cpp 作业 设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函…...

表贴式PMSM的直接转矩控制(DTC)MATLAB仿真模型

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 模型简介 表贴式PMSM的直接转矩控制(DTC),直接使用滞环控制对转矩和磁链进行控制&#xff0c;相对于传统的FOC控制而言&#xff0c;其不需要进行解耦变换&#xff0c;在此次的有以下几点需要注意&#xff1a…...

详解OpenHarmony各部分文件在XR806上的编译顺序

大家好&#xff0c;今天我们来谈一谈编程时一个很有趣的话题——编译顺序。我知道&#xff0c;一提到编译可能大家会感到有点儿头疼&#xff0c;但请放心&#xff0c;我不会让大家头疼的。我们要明白&#xff0c;在开始写代码之前&#xff0c;了解整个程序的编译路径是十分有必…...

【美团】无人机-大数据开发工程师

更新时间&#xff1a;2024/01/29 工作地点&#xff1a;北京市 事业群&#xff1a;到家事业群 工作经验&#xff1a;3年 部门介绍 为了更好地提升城市即时配送的效率与体验&#xff0c;美团于2017年启动了无人机配送服务的探索&#xff0c;通过科技创新推动履约工具变革&#x…...

微服务系统设计:横向扩展和纵向扩展的对比

微服务扩展性&#xff1a;水平扩展 vs 垂直扩展 特点水平扩展垂直扩展扩展单位增加微服务实例增加单个实例的资源 (CPU&#xff0c;内存)方向向外&#xff0c;增加节点向上&#xff0c;增加单个节点的资源复杂性随着实例数量的增加&#xff0c;管理难度更大管理更简单&#xf…...

Java基于SpringBoot+Vue的网上超市管理系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

HTTP中POST、GET、PUT、DELETE方式的区别

GET请求会向数据库发索取数据的请求&#xff0c;从而来获取信息&#xff0c;该请求就像数据库的select操作一样&#xff0c;只是用来查询一下数据&#xff0c;不会修改、增加数据&#xff0c;不会影响资源的内容&#xff0c;即该请求不会产生副作用。无论进行多少次操作&#x…...

77.Go中interface{}判nil的正确姿势

文章目录 一&#xff1a;interface{}简介二、interface{}判空三&#xff1a;注意点四&#xff1a;实际案例 一&#xff1a;interface{}简介 在go中的nil只能赋值给指针、channel、func、interface、map或slice类型的变量 interface 是否根据是否包含有 method&#xff0c;底层…...

ES实战回顾

1、你用的集群节点情况&#xff1f; 一个ES集群&#xff0c;18个节点&#xff0c;其中3个主节点&#xff0c;15个数据节点&#xff0c;500G左右的索引数据量&#xff0c;没有单独的协调节点&#xff0c;它的每个节点都可以充当协调功能&#xff1b; 2、你们常用的索引有哪些&a…...

Mysql 删除数据

从数据表中删除数据使用DELETE语句&#xff0c;DELETE语句允许WHERE子句指定删除条件。DELETE语句基本语法格式如下&#xff1a; DELETE FROM table_name [WHERE <condition>]; table_name指定要执行删除操作的表&#xff1b;“[WHERE <condition>]”为可选参数&a…...

CSS设置单行文字水平垂直居中的方法

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>单行文字水平垂直居中</title><style>div {/* 给div设置宽高 */width: 400px;height: 200px;margin: 100px auto;background-color: red;/…...

数论与图论

数论&#x1f388; 筛质数 最普通的筛法O(nlogn)&#xff1a; void get_primes2(){for(int i2;i<n;i){if(!st[i]) primes[cnt]i;//把素数存起来for(int ji;j<n;ji){//不管是合数还是质数&#xff0c;都用来筛掉后面它的倍数st[j]true;}} } 诶氏筛法 O(nloglogn)&#…...

海外云手机三大优势

在全球化潮流下&#xff0c;企业因业务需求对海外手机卡等设备的需求不断攀升&#xff0c;推动了海外云手机业务的蓬勃发展。相较于自行置备手机设备&#xff0c;海外云手机不仅能够降低成本&#xff0c;还具备诸多优势&#xff0c;让我们深入探讨其中的三大黄金优势。 经济实惠…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...