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

信息学奥赛一本通 1390:食物链【NOI2001】| 洛谷 P2024 [NOI2001] 食物链

【题目链接】

ybt 1390:食物链【NOI2001】
洛谷 P2024 [NOI2001] 食物链

【题目考点】

1. 种类并查集
2. 带权并查集

【解题思路】

解法1:种类并查集

已知有三类动物A、B、C。A吃B,B吃C,C吃A。
对于B类动物来说,A类动物是B类动物的天敌,C类动物是B类动物的猎物。
共有n个动物,对于动物 i i i,假设 i + n i+n i+n i i i的一个天敌,假设 i + 2 n i+2n i+2n i i i的一个猎物。( i + n i+n i+n i + 2 n i+2n i+2n是我们人为假设出来的并非1~n中任何动物的其他动物)
那么 i i i i + n i+n i+n i + 2 n i+2n i+2n分别可能是A、B、C中的哪类动物?有以下几种情况。

A类动物B类动物C类动物
i+nii+2n
ii+2ni+n
i+2ni+ni

设存在A、B、C三个集合,使用并查集表示这三个集合。那么调用find(i), find(i+n), find(i+2*n)就可以得到代表这三个集合的根结点的编号。

对于输入的动物编号x或y,如果x或y大于n,则该描述一定是假话

1. 如果输入1 x y,说x与y是同类
那么首先判断x与y是否是天敌与猎物的关系。

  • 判断x是否是y的天敌,也就是判断 x x x y + n y+n y+n是否在同一集合中find(x) == find(y+n)
  • 判断x是否是y的猎物,也就是判断 x x x y + 2 n y+2n y+2n是否在同一集合中find(x) == find(y+2*n)

只要满足上述两条件之一,那么x与y不可能是同类,这句话是假话。
如果不满足上述条件,那么x与y是同类,二者所在集合合并merge(x, y)
同时x的天敌与y的天敌是同类merge(x+n, y+n),x的猎物与y的猎物是同类merge(x+2*n, y+2*n)
2. 如果输入2 x y,表示x吃y,也就是x是y的天敌,y是x的猎物
如果x是y的猎物,或x与y是同类,则这句话是假话

  • 判断x是否y的猎物,也就是判断 x x x y + 2 n y+2n y+2n是否在同一集合中find(x) == find(y+2*n)
  • 判断x与y是否同类,也就是判断 x x x y y y是否在同一集合中find(x) == find(y)

只要满足上述两条件之一,那么x不可能是y的天敌,这句话是假话。
如果不满足上述条件,那么x与y的天敌是同类merge(x, y+n),x的天敌与y的猎物是同类merge(x+n, y+2*n),x的猎物与y是同类merge(x+2*n, y)

统计并输出假话的数量,即为最终结果。

解法2:带权并查集(待完善)

【题解代码】

解法1:种类并查集
#include<bits/stdc++.h>
using namespace std;
#define N 50005
int fa[3*N], ans;//fa[i]:i的双亲,下标1~3*n。 
void initFa(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{fa[find(x)] = find(y);
}
int main()
{int n, k, op, x, y;cin >> n >> k;initFa(3*n);while(k--){cin >> op >> x >> y;if(x > n || y > n){ans++;continue;}if(op == 1)//x和y同类 {if(find(x) == find(y+n) || find(x) == find(y+2*n))ans++;else{merge(x, y);merge(x+n, y+n);merge(x+2*n, y+2*n);}}else//op == 2 x吃y {if(find(x) == find(y+2*n) || find(x) == find(y))ans++;else{merge(x, y+n);merge(x+n, y+2*n);merge(x+2*n, y);}}}cout << ans;return 0;
}

相关文章:

信息学奥赛一本通 1390:食物链【NOI2001】| 洛谷 P2024 [NOI2001] 食物链

【题目链接】 ybt 1390&#xff1a;食物链【NOI2001】 洛谷 P2024 [NOI2001] 食物链 【题目考点】 1. 种类并查集 2. 带权并查集 【解题思路】 解法1&#xff1a;种类并查集 已知有三类动物A、B、C。A吃B&#xff0c;B吃C&#xff0c;C吃A。 对于B类动物来说&#xff0c…...

Linux网络之序列化和反序列化

目录 序列化和反序列化 上期我们学习了基于TCP的socket套接字编程接口&#xff0c;并实现了一个TCP网络小程序&#xff0c;本期我们将在此基础上进一步延伸学习&#xff0c;实现一个网络版简单计算器。 序列化和反序列化 在生活中肯定有这样一个情景。 上图大家肯定不陌生&a…...

【Django教程】用户管理系统

Get Started With Django User Management 开始使用Django用户管理 By the end of this tutorial, you’ll understand that: 在本教程结束时&#xff0c;您将了解&#xff1a; Django’s user authentication is a built-in authentication system that comes with pre-conf…...

万字长文总结前端开发知识---JavaScriptVue3Axios

JavaScript学习目录 一、JavaScript1. 引入方式1.1 内部脚本 (Inline Script)1.2 外部脚本 (External Script) 2. 基础语法2.1 声明变量2.2 声明常量2.3 输出信息 3. 数据类型3.1 基本数据类型3.2 模板字符串 4. 函数4.1 具名函数 (Named Function)4.2 匿名函数 (Anonymous Fun…...

React基础

前言 &#xff08;2021年笔记&#xff09;补充记录 React基础 前言React讲义一、create-react-app二、关于React1、React的起源和发展2、React与传统MVC的关系3、React高性能的体现&#xff1a;虚拟DOM4、React的特点和优势 三、编写第一个react应用程序四、元素与组件1、函数…...

读书笔记:《华为突围ERP封锁全纪实》

文章背景&#xff1a; 2019年5月&#xff0c;华为被美国制裁&#xff0c;其ERP系统面临断供风险。ERP系统是企业核心管理软件&#xff0c;一旦中断&#xff0c;华为的全球业务将陷入瘫痪。面对这一生死存亡的危机&#xff0c;华为启动了“突围”计划&#xff0c;历经数年艰苦奋…...

Linux的udev详解、安装和使用(dev下的设备每次开机的名称不固定怎么办?)

前言&#xff08;问题与需求&#xff09;&#xff1a; 在传统的devfs 1&#xff1a;设备映射的不确定&#xff1a;一个设备多次加载设备的设备文件可能不同&#xff0c;比如一个hub有可能是ttyUSB0或ttyUSB2或ttyUSB3 2&#xff1a;devfs没有足够的主辅设备号&#xff0c;当设…...

单向循环链表的概念+单向循环链表的结点插入+单向循环链表的结点删除+程序设计与笔试题分析

单向循环链表的原理与应用 思考&#xff1a;对于单向链表而言&#xff0c;想要遍历链表&#xff0c;则必须从链表的首结点开始进行遍历&#xff0c;请问有没有更简单的方案实现链表中的数据的增删改查&#xff1f; 回答&#xff1a;是有的&#xff0c;可以使用单向循环的链表…...

【蓝桥杯嵌入式入门与进阶】2.与开发板之间破冰:初始开发板和原理图2

个人主页&#xff1a;Icomi 专栏地址&#xff1a;蓝桥杯嵌入式组入门与进阶 大家好&#xff0c;我是一颗米&#xff0c;本篇专栏旨在帮助大家从0开始入门蓝桥杯并且进阶&#xff0c;若对本系列文章感兴趣&#xff0c;欢迎订阅我的专栏&#xff0c;我将持续更新&#xff0c;祝你…...

Jetson Xavier NX 安装 CUDA 支持的 PyTorch 指南

本指南将帮助开发者完成在 Jetson Xavier NX 上安装 CUDA 支持的 PyTorch。 安装方法 在 Jetson 上安装 Pytorch 只有两种方法。 一种是直接安装他人已经编译好的 PyTorch 轮子&#xff1b;一种是自己从头开始开始构建 PyTorch 轮子并且安装。 使用轮子安装 可以从我的 Gi…...

“harmony”整合不同平台的单细胞数据之旅

其实在Seurat v3官方网站的Vignettes中就曾见过该算法&#xff0c;但并没有太多关注&#xff0c;直到看了北大张泽民团队在2019年10月31日发表于Cell的《Landscap and Dynamics of Single Immune Cells in Hepatocellular Carcinoma》&#xff0c;为了同时整合两类数据&#xf…...

[权限提升] 操作系统权限介绍

关注这个专栏的其他相关笔记&#xff1a;[内网安全] 内网渗透 - 学习手册-CSDN博客 权限提升简称提权&#xff0c;顾名思义就是提升自己在目标系统中的权限。现在的操作系统都是多用户操作系统&#xff0c;用户之间都有权限控制&#xff0c;我们通过 Web 漏洞拿到的 Web 进程的…...

大模型本地部署流程介绍

大模型本地部署流程介绍 随着人工智能技术的快速发展&#xff0c;大模型&#xff08;如大型语言模型、图像识别模型等&#xff09;的应用越来越广泛。然而&#xff0c;由于这些模型通常体积庞大且计算资源要求高&#xff0c;如何在本地环境中高效部署成为了一个重要的议题。以…...

浅析百度AOI数据与高德AOI数据的差异性

目录 前言 一、AOI属性数据 1、百度AOI数据 2、高德AOI数据 二、AOI矢量边界 1、百度AOI空间范围 2、高德AOI空间范围 三、数据获取频次和难易程度 1、接口限制 2、数据转换成本 四、总结 前言 在当今数字化时代&#xff0c;地理信息数据的精准性和丰富性对于城市规划…...

LeetCode 119. 杨辉三角 II

题意&#xff1a;求杨辉三角&#xff08;帕斯卡三角&#xff09;的第n行&#xff08;n从0开始&#xff09; 杨辉三角的每一行是二项式排列组合的展开式 第n行为: C n 0 , C n 1 , C n 2 , … , C n n C_{n}^{0}, C_{n}^{1}, C_{n}^{2}, \dots, C_{n}^{n} Cn0​,Cn1​,Cn2​,……...

机器学习-K近邻算法

文章目录 一. 数据集介绍Iris plants dataset 二. 代码三. k值的选择 一. 数据集介绍 鸢尾花数据集 鸢尾花Iris Dataset数据集是机器学习领域经典数据集&#xff0c;鸢尾花数据集包含了150条鸢尾花信息&#xff0c;每50条取自三个鸢尾花中之一&#xff1a;Versicolour、Setosa…...

设计模式Python版 原型模式

文章目录 前言一、原型模式二、原型模式示例三、原型管理器 前言 GOF设计模式分三大类&#xff1a; 创建型模式&#xff1a;关注对象的创建过程&#xff0c;包括单例模式、简单工厂模式、工厂方法模式、抽象工厂模式、原型模式和建造者模式。结构型模式&#xff1a;关注类和对…...

centos安装mysql

下面的方法不行&#xff0c;最后还是通过我自己的博客中的 https://blog.csdn.net/qq_21237549/article/details/133759503 CentOS 安装MySQL 详细教程 安装成功的 通过网盘分享的文件&#xff1a;服务器部署 链接: https://pan.baidu.com/s/12QwjIMgwHcwVeVoal-BKrg 提取码:…...

java 判断Date是上午还是下午

我要用Java生成表格统计信息&#xff0c;如下图所示&#xff1a; 所以就诞生了本文的内容。 在 Java 里&#xff0c;判断 Date 对象代表的时间是上午还是下午有多种方式&#xff0c;下面为你详细介绍不同的实现方法。 方式一&#xff1a;使用 java.util.Calendar Calendar 类…...

Jenkins安装部署(以及常见报错解决方案),jdk版本控制器sdkman

目录 零、环境介绍 一、Jenkins安装 1、插件安装以及更换插件源 2、修改jenkins时区 二、sdkman安装&#xff08;可选&#xff09; 1、sdkman常用方法 2、sdkman常用方法演示 2.1、查看可用的jdk 2.2、下载jdk并切换版本 三、jenkins报错解决 1、下载sdkman后systemc…...

【Linux】gdb——Linux调试器

gdb使用背景 程序的发布方式有两种&#xff0c;debug模式和release模式 Linux gcc/g出来的二进制程序&#xff0c;默认是release模式 要使用gdb调试&#xff0c;必须在源代码生成二进制程序的时候, 加上 -g 选项 gdb使用方法 首先进入gdb gdb test_glist显示代码 断点 b 行…...

978.最长湍流子数组

目录 题目过程解法收获 题目 给定一个整数数组 arr &#xff0c;返回 arr 的 最大湍流子数组的长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转&#xff0c;则该子数组是 湍流子数组 。 更正式地来说&#xff0c;当 arr 的子数组 A[i], A[i1], …, A[j] 满足仅满足…...

LLM - 大模型 ScallingLaws 的指导模型设计与实验环境(PLM) 教程(4)

欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/145323420 免责声明:本文来源于个人知识与公开资料,仅用于学术交流,欢迎讨论,不支持转载。 Scaling Laws (缩放法则) 是大模型领域中,用于描述 模型性能(Loss) 与…...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】1.19 排序革命:argsort的十大高阶用法

1.19 排序革命&#xff1a;argsort的十大高阶用法 目录 #mermaid-svg-Qu8PcmLkIc1pOQJ7 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-Qu8PcmLkIc1pOQJ7 .error-icon{fill:#552222;}#mermaid-svg-Qu8PcmLkIc1pOQJ…...

记忆力训练day07

逻辑分类联想记忆法 一 课程目标 &#xff08;1&#xff09;掌握如何分类信息 &#xff08;2&#xff09;掌握如何运用逻辑分类方法进行记忆 小试牛刀&#xff1a; 核心的内容&#xff1a; 文字逻辑分类记忆&#xff1a;把文字分类后转换成画面连接记忆。 玫瑰 大树 太阳…...

RK3588平台开发系列讲解(ARM篇)ARM64底层中断处理

文章目录 一、异常级别二、异常分类2.1、同步异常2.2、异步异常三、中断向量表沉淀、分享、成长,让自己和他人都能有所收获!😄 一、异常级别 ARM64处理器确实定义了4个异常级别(Exception Levels, EL),分别是EL0到EL3。这些级别用于管理处理器的特权级别和权限,级别越高…...

算法1-1 模拟与高精度

目录 一 阶乘数码 二 麦森数 三 模拟题 一 阶乘数码 本题中n<1000,1000的阶乘为以下这么大&#xff0c;远超long的范围 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901…...

(四)线程 和 进程 及相关知识点

目录 一、线程和进程 &#xff08;1&#xff09;进程 &#xff08;2&#xff09;线程 &#xff08;3&#xff09;区别 二、串行、并发、并行 &#xff08;1&#xff09;串行 &#xff08;2&#xff09;并行 &#xff08;3&#xff09;并发 三、爬虫中的线程和进程 &am…...

Tensor 基本操作2 理解 tensor.max 操作,沿着给定的 dim 是什么意思 | PyTorch 深度学习实战

前一篇文章&#xff0c;Tensor 基本操作1 | PyTorch 深度学习实战 本系列文章 GitHub Repo: https://github.com/hailiang-wang/pytorch-get-started 目录 Tensor 基本操作torch.max默认指定维度 Tensor 基本操作 torch.max torch.max 实现降维运算&#xff0c;基于指定的 d…...

[牛客]公交线路(dijkstra+链式前向星)

登录—专业IT笔试面试备考平台_牛客网 #include<bits/stdc.h> using namespace std; #define endl \n typedef long long ll; const int N1e65,M1e85; int cnt0,head[N]; int n,m,s,t; struct node {int v,w,next; }edge[M]; void addedge(int u,int v,int w) {cnt;edge…...

面试被问的一些问题汇总(持续更新)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

RocketMQ原理—5.高可用+高并发+高性能架构

大纲 1.RocketMQ的整体架构与运行流程 2.基于NameServer管理Broker集群的架构 3.Broker集群的主从复制架构 4.基于Topic和Queue实现的数据分片架构 5.Broker基于Pull模式的主从复制原理 6.Broker层面到底如何做到数据0丢失 7.数据0丢失与写入高并发的取舍 8.RocketMQ读…...

适配器模式——C++实现

目录 1. 适配器模式简介 2. 角色组成 3. 代码示例 4. 适配器模式、装饰器模式、外观模式的辨析 1. 适配器模式简介 适配器模式是一种结构型模式。 适配器模式的定义&#xff1a;适配器模式将一个类的接口&#xff0c;转换成客户期望的另一个接口。适配器让原本接口不可兼容…...

C语言自定义数据类型详解(一)——结构体类型(上)

什么是自定义数据类型呢&#xff1f;顾名思义&#xff0c;就是我们用户自己定义和设置的类型。 在C语言中&#xff0c;我们的自定义数据类型一共有三种&#xff0c;它们分别是&#xff1a;结构体(struct)&#xff0c;枚举(enum)&#xff0c;联合(union)。接下来&#xff0c;我…...

C语言基础4

sizeof和strlen的区别 ①sizeof是运算符而strlen是函数 ②sizeof可以用类型做参数&#xff0c;strlen只能用char*做参数 ③数组做sizeof参数不退化&#xff0c;而传递给strlen则退化成指针 ④strlen结果是运行时候才能计算出来&#xff0c;而且计算出来的是字符串的长度不是内…...

【Elasticsearch】Elasticsearch的查询

Elasticsearch的查询 DSL查询基础语句叶子查询全文检索查询matchmulti_match 精确查询termrange 复合查询算分函数查询bool查询 排序分页基础分页深度分页 高亮高亮原理实现高亮 RestClient查询基础查询叶子查询复合查询排序和分页高亮 数据聚合DSL实现聚合Bucket聚合带条件聚合…...

第 5 章:声音与音乐系统

5.1 声音效果的应用 在游戏中&#xff0c;声音效果是增强游戏沉浸感和趣味性的重要元素。Pygame 提供了强大的音频处理功能&#xff0c;使得添加各种声音效果变得相对简单。声音效果可以包括角色的动作音效&#xff0c;如跳跃、攻击、受伤时的声音&#xff1b;环境音效&#x…...

第十四讲 JDBC数据库

1. 什么是JDBC JDBC&#xff08;Java Database Connectivity&#xff0c;Java数据库连接&#xff09;&#xff0c;它是一套用于执行SQL语句的Java API。应用程序可通过这套API连接到关系型数据库&#xff0c;并使用SQL语句来完成对数据库中数据的查询、新增、更新和删除等操作…...

2024年除夕

多少年前的除夕&#xff0c;一如今天这样的除夕&#xff1b;多少年后的除夕&#xff0c;也一如多少年前的除夕。 无数个这样的除夕下午&#xff0c;我打开电脑&#xff0c;望着窗外安静的小区&#xff0c;车声渐渐稀疏的马路&#xff0c;想写下一些新的感受时&#xff0c;多少…...

虚幻基础07:蓝图接口

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 作用原理事件函数 作用 实现对象间的通知。 A 通知 B 做什么。 原理 将接口抽象为蓝图&#xff0c;使得任意蓝图都能直接访问。 只需要再传入对象地址&#xff0c;就能执行对象的功能。 事件 黄色&#xff1a;…...

7. 马科维茨资产组合模型+金融研报AI长文本智能体(Qwen-Long)增强方案(理论+Python实战)

目录 0. 承前1. 深度金融研报准备2. 核心AI函数代码讲解2.1 函数概述2.2 输入参数2.3 主要流程2.4 异常处理2.5 清理工作2.7 get_ai_weights函数汇总 3. 汇总代码4. 反思4.1 不足之处4.2 提升思路 5. 启后 0. 承前 本篇博文是对前两篇文章&#xff0c;链接: 5. 马科维茨资产组…...

如何在本地部署deepseek r1模型?

DeepSeek&#xff08;深度求索&#xff09;正式发布了其最新推理模型DeepSeek-R1&#xff0c;引发业界广泛关注。这款模型不仅在性能上与OpenAI的GPT-4相媲美&#xff0c;更以其开源策略和创新的训练方法&#xff0c;为AI发展带来了新的可能性。DeepSeek-R1 在后训练阶段大规模…...

HarmonyOS:状态管理最佳实践

一、概述 在声明式UI编程范式中&#xff0c;UI是应用程序状态的函数&#xff0c;应用程序状态的修改会更新相应的UI界面。ArkUI采用了MVVM模式&#xff0c;其中ViewModel将数据与视图绑定在一起&#xff0c;更新数据的时候直接更新视图。如下图所示&#xff1a; ArkUI的MVVM模式…...

当AI风暴来袭:中美科技商业版图的迥异走向

当AI风暴来袭:中美科技商业版图的迥异走向 美国科技巨头的 AI 豪赌:Stargate 公司的诞生 2025 年,科技界被一则重磅消息所震动:软银、NVIDIA、Oracle 与 OpenAI 共同组建了 Stargate 公司。这一合作堪称豪华阵容,软银作为全球知名的投资巨头,拥有雄厚的资金实力和广泛的…...

马尔科夫模型和隐马尔科夫模型区别

我用一个天气预报和海藻湿度观测的比喻来解释&#xff0c;保证你秒懂&#xff01; 1. 马尔可夫模型&#xff08;Markov Model, MM&#xff09; 特点&#xff1a;状态直接可见 场景&#xff1a;天气预报&#xff08;晴天→雨天→阴天…&#xff09;核心假设&#xff1a; 下一个…...

面向对象设计原则 - SOLID原则 (基于C++)

SOLID 是面向对象编程中的一组五个设计原则&#xff0c;这些原则旨在帮助开发者创建更灵活、可维护和可扩展的软件系统。它们最初由 Robert C. Martin 提出&#xff0c;并在 2000 年左右被广泛接受。每个字母代表一个不同的原则&#xff1a; 单一职责原则 (Single Responsibil…...

ChatGPT 搜索测试整合记忆功能

据 TestingCatalog 报道&#xff0c;OpenAI 正在测试 ChatGPT 搜索的整合记忆功能&#xff0c;被命名为 “Memory in search”2。以下是关于该功能的具体情况123&#xff1a; 功能特点 个性化搜索&#xff1a;启用该功能后&#xff0c;ChatGPT 能利用存储的记忆数据&#xff0…...

PWM频率测量方法

测量PWM&#xff08;脉宽调制&#xff09;信号的频率是嵌入式系统中的常见需求&#xff0c;尤其是在电机控制、LED调光、传感器信号处理等场景中。 在这里介绍两种测量PWM频率的方法&#xff1a;测频法与测周法。 1、测频&#xff08;率&#xff09;法 原理&#xff1a;在闸门…...

【B站保姆级视频教程:Jetson配置YOLOv11环境(一)镜像下载与烧录】

b站同步视频教程&#xff1a;https://www.bilibili.com/video/BV11r6oYkEFb/ 一、引言 在人工智能与计算机视觉快速发展的当下&#xff0c;Jetson系列开发板凭借强大的性能&#xff0c;成为众多开发者进行深度学习项目的热门选择。YOLOv11作为目标检测领域的先进算法&#xf…...

使用QSqlQueryModel创建交替背景色的表格模型

class UserModel(QSqlQueryModel):def __init__(self):super().__init__()self._query "SELECT name, age FROM users"self.refresh()def refresh(self):self.setQuery(self._query)# 重新定义data()方法def data(self, index, role): if role Qt.BackgroundRole…...