1390:食物链【NOI2001】
【解题思路】
并查集把三类动物划分成三个域,同类域(1-n)、捕食域〈n+1-2n)、天敌域(2n+1-3n)。把x放入同类域,x+n放入其捕食域,x+2n放入其天敌域。给×在其他集合内安插两个“虚拟代表”,从而实现关系传递。
×吃y,则×与y的天敌代表y+2n是同类,合并区y+2n);
×吃y,则×的捕食代表×+n与y是同类,合并(x+n,y);
x吃y,则×的天敌代表x+2n与y的捕食代表y+n是同类,合并(x+2n,y+n)。
例如,n=10,1吃2,2吃3,3吃4。
1吃2:(1,22)(11,2)(21,12)
2吃3:(2,23)(12,3)(22,13)
3吃4:〔3,24)(13,4)(23,14)
通过代表22和13,把1与4合并到一起。

【参考代码】
//示例代码
#include <iostream>
#include <cstdio>
using namespace std;const int N=150005; // 定义常量 N,表示数组大小
int n,k,F; // n 表示点的数量,k 表示操作数, F 表示不合法的操作数。
int f[N]; // 数组 f 存储点的祖先// 并查集中的查找操作,实现路径压缩
int find(int x){if(f[x]==x) return f[x];return f[x]=find(f[x]);
}// 并查集中的合并操作
void unionn(int x,int y){x=find(x);y=find(y);if(x!=y) f[y]=x;
}int main()
{scanf("%d %d",&n,&k); // 输入点的数量和操作数for(int i=1;i<=n*3;i++)f[i]=i; // 初始化并查集,每一个点是其自己的祖先。int d,x,y; // d 表示每个操作的类型,x、y 表示需要连接的两个点的编号。while(k--){scanf("%d %d %d",&d,&x,&y);if(x>n||y>n){ // 判断输入的点是否合法。如果一个点的编号大于 n,代表这个操作是不合法的。F++; continue;}else if(d==1){ // 如果操作类型为 1,x,y为同类if(find(x)==find(y+n) || find(x)==find(y+n*2)) F++; // 如果x的猎物是y或y的天敌 为假else{ // 否则,合并。unionn(x,y);//同类合并unionn(x+n,y+n);//x的天敌和y的天敌是同类unionn(x+2*n,y+2*n);//x的猎物也和y的猎物是同类} }else if(d==2){ // 如果操作类型为 2,x的猎物是y。if(find(x)==find(y) || find(x)==find(y+n*2)) F++; // 如果x,y同类 或 x的天敌是y 则假。else{ // 否则,合并。unionn(x,y+n);//x的猎物是yunionn(x+n,y+2*n);//x的天敌也是y的猎物unionn(x+2*n,y);//y的天敌是x} }}printf("%d",F); // 输出不合法操作的数量。return 0;
}
相关文章:
1390:食物链【NOI2001】
【解题思路】 并查集把三类动物划分成三个域,同类域(1-n)、捕食域〈n1-2n)、天敌域(2n1-3n)。把x放入同类域,xn放入其捕食域,x2n放入其天敌域。给在其他集合内安插两个“虚拟代表”…...
ICMAN液位检测——WS003B管道检测模组
ICMAN液位检测之WS003B管道检测模组 体积小,成本低, 液位检测精度高, 有水输出低电平无水高电平, 适用于饮水机、咖啡机、扫地机器人、洗地机等, 有需要朋友快联系我吧! AWE展会不容错过的ICMAN检测模组…...
YOLOv10使用教程及导读
首先推荐一下我的YOLOv8/v10项目,仅需一个v8的钱(69.9),付费进群,即可获取v8/v10的全部改进,欢迎进群。 1 YOLOv10简介 论文链接:https://arxiv.org/pdf/2405.14458 官方代码链接:ht…...
AIGC 在前端流式获取内容SSE
AIGC 在前端流式获取内容SSE 简介具体实现 简介 在 OpenAI 的 API 中,SSE 通常用于实现实时数据传输。例如,在聊天模型(如 ChatGPT)中,使用 SSE 可以让客户端实时接收到生成的对话内容,而不需要等待整个响…...
深度解析安全阀检测技术:方法与挑战
在工业生产中,安全阀作为防止压力容器和管道发生过压事故的关键部件,其性能和可靠性对于保证设备安全和人员安全具有重要意义。随着工业化进程的不断深入,对安全阀的检测和维护工作也日益受到重视。 接下来,佰德旨在探讨安全阀检…...
网络安全--安全设备(一)Dos
安全设备--Dos 一、Dos 是什么二、DDos是什么三、Dos&DDos的区别四、产品防御Dos&DDos方式五、常见的DDoS攻击类型包括但不限于以下几种: 一、Dos 是什么 Dos(拒绝服务攻击,Denial-of-Service),是一种试图通过压倒网络或服务器来阻止合法用户访…...
<电力行业> - 《第3课:国家电网公司100条名词解释》
序号术语解 释1十不干一、无票的不干;二、工作任务、危险点不清楚的不干;三、危险点控制措施未落实的不干;四、超出作业范围未经审批的不干;五、未在接地保护范围内的不干;六、现场安全措施布置不到位、安全工器具不合…...
“论数据访问层设计技术及其应用”写作框架,系统架构设计师
论文真题 在信息系统的开发与建设中,分层设计是一种常见的架构设计方法,区分层次的目的是为了实现“高内聚低耦合”的思想。分层设计能有效简化系统复杂性,使设计结构清晰,便于提高复用能力和产品维护能力。一种常见的层次划分模…...
Docker部署前端,动态配置后端地址
本文介绍了使用Docker环境变量动态配置nginx。采用的是通过docker run -e xxxxxxx先往容器注入环境变量,然后进一步通过envsubst指令将环境变量写入到conf文件中,实现动态配置文件内容。 背景 前后端分离的架构下,经常会用到nginx反向代理来…...
k8s强制删除一个 Pod
在Kubernetes(K8s)中强制删除一个Pod,通常是因为Pod处于错误状态或无法正常终止。以下是强制删除Pod的步骤和相关信息: ### 步骤一:获取Pod的名称 首先,你需要知道要删除的Pod的名称。可以使用kubectl get …...
docker的安装配置及使用
一.Docker的由来 Docker 最初是 dotCloud 公司创始人Solomon Hykes 在法国期间发起的一个公司内部项目。 2010年的专门做PAAS平台,但是到了2013年的时候,像亚马逊,微软,Google都开始做PAAS平台。 到了2013年,公司资金链…...
初阶 《操作符详解》 10. 逗号表达式
10. 逗号表达式 exp1, exp2, exp3, …expN 注: 1.逗号表达式,就是用逗号隔开的多个表达式 2.逗号表达式,从左向右依次执行,整个表达式的结果是最后一个表达式的结果 代码1 #include <stdio.h> int main() {int a 1;int b…...
【区分vue2和vue3下的element UI Loading 加载组件,分别详细介绍属性,事件,方法如何使用,并举例】
首先,需要澄清的是,Element UI 是为 Vue 2 设计的,而 Element Plus 是 Element UI 的 Vue 3 版本。在 Element UI 和 Element Plus 中,并没有一个直接名为 “Loading 加载” 的独立组件。相反,加载效果通常是通过指令、…...
数据结构:栈(stack)详解 c++信息学奥赛基础知识讲解
目录 一、栈的定义 二、栈的操作 三、代码实操 四、栈的实现 1、string实现stack 2、vector实现stack 3、deque实现栈 一、栈的定义 stack是一个比较简单易用的数据结构,stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中ÿ…...
电商返利系统的高并发处理与性能优化
电商返利系统的高并发处理与性能优化 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在电子商务平台中,返利系统是吸引用户和提升用户粘性的重要功…...
NPM 常用命令
NPM 常用命令 NPM(Node Package Manager)是 JavaScript 生态系统中最流行的包管理工具,它不仅可以管理 Node.js 项目的依赖,还提供了丰富的命令来管理和发布你的代码。本文将从不同角度,深入浅出地介绍 NPM 的常用命令…...
C++进修——C++核心编程
内存分区模型 C程序在执行时,将内存大方向划分为4个区域 代码区:存放函数体的二进制编码,由操作系统进行管理全局区:存放全局变量和静态变量以及常量栈区:由编译器自动分配释放,存放函数的参数值ÿ…...
【信息系统项目管理师知识点速记】项目文档管理
19.3 项目文档管理 信息系统相关信息(文档)是指某种数据媒体和其中所记录的数据。文档具有永久性,并可以由人或机器阅读,通常用于描述人工可读的内容。在软件工程中,文档常常用来表示对活动、需求、过程或结果进行描述、定义、规定、报告或认证的任何书面或图示的信息(包…...
服务器硬件,raid配置
文章目录 服务器硬件RAID磁盘阵列RAID 0RAID 1RAID 5RAID 6RAID 10 阵列卡,阵列卡的缓存阵列卡阵列卡的缓存 软RAID磁盘阵列RAID阵列的管理及设备恢复mdadm 服务器硬件 处理器(CPU):服务器的核心组件,负责执行计算和指令操作。服务器常使用多…...
fc-list命令使用指南
fc-list命令使用指南 一、什么是fc-list? fc-list是FontConfig库的一部分,最初为Linux和其他Unix-like系统开发。我们可以用这个命令行快速查询和列出系统中安装的字体。 现在,Windows用户也集成了这个工具,所以我们来讲解一下用法。 二、…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
