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

Acwing 240. 食物链

Acwing 240. 食物链

  • 题目描述
  • 思路讲解
  • 代码展示

题目描述

在这里插入图片描述

思路讲解

这题多维护了一种额外信息

代码展示

#include <iostream>using namespace std;const int N = 50010;int n, m;
int p[N], d[N]; //p[]是并查集的father,d[]是距离int find(int x) {if (p[x] != x) {  //如果说x不是树根的话int t = find(p[x]);d[x] += d[p[x]];p[x] = t;}return p[x];
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) p[i] = i;  //初始化int res = 0;while (m--) {int t, x, y;scanf("%d%d%d", &t, &x, &y);if (x > n || y > n) res++;else {int px = find(x), py = find(y);if (t == 1) {if (px == py && (d[x] - d[y]) % 3) res++;else if (px != py) {p[px] = py;d[px] = d[y] - d[x];}} else {if (px == py && (d[x] - d[y] - 1) % 3) res++;else if (px != py) {p[px] = py;d[px] = d[y] + 1 - d[x];}}}}printf("%d\n", res);return 0;
}

相关文章:

Acwing 240. 食物链

Acwing 240. 食物链 题目描述思路讲解代码展示 题目描述 思路讲解 代码展示 #include <iostream>using namespace std;const int N 50010;int n, m; int p[N], d[N]; //p[]是并查集的father,d[]是距离int find(int x) {if (p[x] ! x) { //如果说x不是树根的话int t f…...

c++ 容器适配器

Container //创建一个命名空间&#xff0c;避免和库里的冲突 namespace chen {//写一个模版template<class T, class Container deque<T>>//开始写我们的类class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const …...

正则表达式的应用领域及基本语法解析

目录 一、正则表达式的应用领域 1. 文本搜索和替换 2. 表单验证 3. 数据提取和分析 4. 数据清洗和处理 5. URL路由和路由匹配 二、正则表达式的基本语法 1. 字符匹配 2. 元字符和字符类 3. 量词和边界 4. 分组和捕获 5. 转义字符 三、常见正则表达式示例 1. 邮箱…...

CIP或者EtherNET/IP中的PATH是什么含义?

目录 SegmentPATH举例 最近在学习EtherNET/IP&#xff0c;PATH不太明白&#xff0c;翻了翻规范&#xff0c;在这里记个笔记。下面的叙述可能是中英混合&#xff0c;有一些是规范中的原文我直接搬过来的。我翻译的不准确。 Segment PATH是CIP Segment中的一个分类。要了解PATH…...

使用lombok进行bulider之后调取HashMap的自定义方法进行对象操作报空指针异常(pojo也适用)

概论 这主要的问题就是bulider的特性的问题&#xff0c;就是他只能给你搭建了一个脚手架&#xff0c;里面的东西其实他没动你的&#xff0c;你得自己去给他实体化&#xff0c;如果你使用了类似HashMap等集合的话&#xff0c;你得自己去bulid一个在那个里面作为初始化对象你才可…...

矩阵-day14

...

上古神器:十六位应用程序 Debug 的基本使用

文章目录 参考环境上古神器 DebugBug 与 DebuggingDebugDebug 应用程序淘汰原因使用限制 DOSBox学习 Debug 的必要性DOSBox-X Debug 的基本使用命令 R查看寄存器的状态修改寄存器的内容 命令 D显示内存中的数据指定起始内存空间地址指定内存空间的范围 命令 A使用命令语法错误查…...

[学习笔记]ARXML - Data Format

参考AUTOSAR文档&#xff1a; https://www.autosar.org/fileadmin/standards/R22-11/FO/AUTOSAR_TPS_ARXMLSerializationRules.pdfhttps://www.autosar.org/fileadmin/standards/R22-11/FO/AUTOSAR_TPS_ARXMLSerializationRules.pdf 编码 arxml只允许使用UTF-8编码&#xff…...

Go_原子操作和锁

原子操作和锁 本文先探究并发问题&#xff0c;再探究锁和原子操作解决问题的方式&#xff0c;最后进行对比。 并发问题 首先&#xff0c;我们看一下程序 num该程序表面看上去一步就可以运行完成&#xff0c;但是实际上&#xff0c;在计算机中是分三步运行的&#xff0c;如下…...

初识Java 12-1 流

目录 Java 8对流的支持 流的创建 随机数流 int类型的区间范围 generate() iterate() 流生成器 Arrays 正则表达式 本笔记参考自&#xff1a; 《On Java 中文版》 ||| 流的概念&#xff1a;流是一个与任何特定的存储机制都没有关系的元素序列。 流与对象的成批处理有关…...

【软件工程_UML—StartUML作图工具】startUML怎么画interface接口

StartUML作图工具怎么画interface接口 初试为圆形 &#xff0c;点击该接口在右下角的设置中->Format->Stereotype Display->Label&#xff0c;即可切换到想要的样式 其他方式 在class diagram下&#xff0c;左侧有interface图标&#xff0c;先鼠标左键选择&#xff0…...

单片机之瑞萨RL78定时计数器

单片机之瑞萨RL78定时计数器 使用瑞萨RL78定时计数器的简单例程。这个例程使用定时器0来产生一个以秒为单位的定时器中断&#xff0c;并在中断服务程序中增加一个全局变量以跟踪中断的发生。 首先&#xff0c;我们需要了解RL78的定时器0是一个16位的定时器&#xff0c;它的时钟…...

手机号码格式校验:@Phone(自定义参数校验注解)

需求 新增接口 和 修改接口 中&#xff0c;手机号码的格式校验是普遍需要的。 在每个手机号码字段上添加正则表达式校验注解来实现校验&#xff0c;重复书写&#xff0c;容易出错&#xff1b;在不同的手机号码字段上&#xff0c;可能使用了不同的校验规则&#xff0c;无法有效…...

ORACLE Redo Log Buffer 重做日志缓冲区机制的设计

最近和朋友包括一些国产数据库的研发人员交流&#xff0c;很多程序员认为 Oracle 已经过时&#xff0c;开源数据库或者他们研发的国产数据库才代表数据库发展的未来。甚至在很多交流会议上拿出自家产品的某一个功能点和 Oracle 对比就觉得已经遥遥领先。 实际上数据库系统的发展…...

PWN Test_your_nc Write UP

目录 PWN 00 解题过程 总结归纳 PWN 01 解题过程 总结归纳 PWN 02 解题过程 总结归纳 PWN 03 解题过程 总结归纳 PWN 04 解题过程 总结归纳 CTF PWN 开始&#xff01; 冲就完了 PWN 00 解题过程 ssh远程链连接 ssh ctfshowpwn.challenge.ctf.show -p28151 输…...

Centos7配置firewalld防火墙规则

这里写自定义目录标题 欢迎使用Markdown编辑器一、简单介绍二、特点和功能2.1、区域&#xff08;Zone&#xff09;2.2、运行时和永久配置2.3、服务和端口2.4、动态更新2.5、连接跟踪2.6、D-Bus接口 三、设置规则3.1、启动防火墙服务3.2、新建防火墙规则的服务&#xff0c;添加端…...

【新版】系统架构设计师 - 未来信息综合技术

个人总结&#xff0c;仅供参考&#xff0c;欢迎加好友一起讨论 文章目录 架构 - 未来信息综合技术考点摘要信息物理系统CPS的体系架构CPS 的技术体系CPS应用场景 人工智能分类关键技术机器学习 机器人发展分类机器人4.0 边缘计算概念与特点边云协同安全应用场景 数字孪生关键技…...

CAD二次开发LineSegment2d

在C#的CAD二次开发中&#xff0c;LineSegment2d 是AutoCAD的.NET API中的一个类&#xff0c;用于表示二维空间中的线段。它包含了起点和终点的坐标信息&#xff0c;并提供了一些方法用于进行线段之间的计算和判断。 LineSegment2d 类具有以下常用属性和方法&#xff1a; Star…...

Linux shell编程学习笔记5:变量命名规则、变量类型、使用变量时要注意的事项

跟其他的高级开发语言一样&#xff0c;Linux Shell编程中使用的数据也需要保存在变量中。 Shell使用变量来控制其行为&#xff0c;并且可以通过更改变量值来更改Shell和其他程序的行为。 我们先来了解一下变量命令的规则、变量类型和使用变量时要注意的事项。 一、变量命名规…...

如何把word的页眉页脚改为图片

前言 亲戚A&#xff1a; 听说你是计算机专业&#xff1f; 沐风晓月&#xff1a; 是啊 亲戚A&#xff1a; 那正好&#xff0c;来看看我这个页眉怎么改成图片 沐风晓月&#xff1a; 一万匹马奔腾而过 亲戚B&#xff1a; 听说你是英语专业&#xff1f; 沐风晓月&#xff1a; 是啊…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...