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

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】

【解题思路】 并查集把三类动物划分成三个域&#xff0c;同类域&#xff08;1-n&#xff09;、捕食域〈n1-2n&#xff09;、天敌域&#xff08;2n1-3n&#xff09;。把x放入同类域&#xff0c;xn放入其捕食域&#xff0c;x2n放入其天敌域。给在其他集合内安插两个“虚拟代表”…...

ICMAN液位检测——WS003B管道检测模组

ICMAN液位检测之WS003B管道检测模组 体积小&#xff0c;成本低&#xff0c; 液位检测精度高&#xff0c; 有水输出低电平无水高电平&#xff0c; 适用于饮水机、咖啡机、扫地机器人、洗地机等&#xff0c; 有需要朋友快联系我吧&#xff01; AWE展会不容错过的ICMAN检测模组…...

YOLOv10使用教程及导读

首先推荐一下我的YOLOv8/v10项目&#xff0c;仅需一个v8的钱&#xff08;69.9&#xff09;&#xff0c;付费进群&#xff0c;即可获取v8/v10的全部改进&#xff0c;欢迎进群。 1 YOLOv10简介 论文链接&#xff1a;https://arxiv.org/pdf/2405.14458 官方代码链接&#xff1a;ht…...

AIGC 在前端流式获取内容SSE

AIGC 在前端流式获取内容SSE 简介具体实现 简介 在 OpenAI 的 API 中&#xff0c;SSE 通常用于实现实时数据传输。例如&#xff0c;在聊天模型&#xff08;如 ChatGPT&#xff09;中&#xff0c;使用 SSE 可以让客户端实时接收到生成的对话内容&#xff0c;而不需要等待整个响…...

深度解析安全阀检测技术:方法与挑战

在工业生产中&#xff0c;安全阀作为防止压力容器和管道发生过压事故的关键部件&#xff0c;其性能和可靠性对于保证设备安全和人员安全具有重要意义。随着工业化进程的不断深入&#xff0c;对安全阀的检测和维护工作也日益受到重视。 接下来&#xff0c;佰德旨在探讨安全阀检…...

网络安全--安全设备(一)Dos

安全设备--Dos 一、Dos 是什么二、DDos是什么三、Dos&DDos的区别四、产品防御Dos&DDos方式五、常见的DDoS攻击类型包括但不限于以下几种&#xff1a; 一、Dos 是什么 Dos(拒绝服务攻击,Denial-of-Service)&#xff0c;是一种试图通过压倒网络或服务器来阻止合法用户访…...

<电力行业> - 《第3课:国家电网公司100条名词解释》

序号术语解 释1十不干一、无票的不干&#xff1b;二、工作任务、危险点不清楚的不干&#xff1b;三、危险点控制措施未落实的不干&#xff1b;四、超出作业范围未经审批的不干&#xff1b;五、未在接地保护范围内的不干&#xff1b;六、现场安全措施布置不到位、安全工器具不合…...

“论数据访问层设计技术及其应用”写作框架,系统架构设计师

论文真题 在信息系统的开发与建设中&#xff0c;分层设计是一种常见的架构设计方法&#xff0c;区分层次的目的是为了实现“高内聚低耦合”的思想。分层设计能有效简化系统复杂性&#xff0c;使设计结构清晰&#xff0c;便于提高复用能力和产品维护能力。一种常见的层次划分模…...

Docker部署前端,动态配置后端地址

本文介绍了使用Docker环境变量动态配置nginx。采用的是通过docker run -e xxxxxxx先往容器注入环境变量&#xff0c;然后进一步通过envsubst指令将环境变量写入到conf文件中&#xff0c;实现动态配置文件内容。 背景 前后端分离的架构下&#xff0c;经常会用到nginx反向代理来…...

k8s强制删除一个 Pod

在Kubernetes&#xff08;K8s&#xff09;中强制删除一个Pod&#xff0c;通常是因为Pod处于错误状态或无法正常终止。以下是强制删除Pod的步骤和相关信息&#xff1a; ### 步骤一&#xff1a;获取Pod的名称 首先&#xff0c;你需要知道要删除的Pod的名称。可以使用kubectl get …...

docker的安装配置及使用

一.Docker的由来 Docker 最初是 dotCloud 公司创始人Solomon Hykes 在法国期间发起的一个公司内部项目。 2010年的专门做PAAS平台&#xff0c;但是到了2013年的时候&#xff0c;像亚马逊&#xff0c;微软&#xff0c;Google都开始做PAAS平台。 到了2013年&#xff0c;公司资金链…...

初阶 《操作符详解》 10. 逗号表达式

10. 逗号表达式 exp1, exp2, exp3, …expN 注&#xff1a; 1.逗号表达式&#xff0c;就是用逗号隔开的多个表达式 2.逗号表达式&#xff0c;从左向右依次执行&#xff0c;整个表达式的结果是最后一个表达式的结果 代码1 #include <stdio.h> int main() {int a 1;int b…...

【区分vue2和vue3下的element UI Loading 加载组件,分别详细介绍属性,事件,方法如何使用,并举例】

首先&#xff0c;需要澄清的是&#xff0c;Element UI 是为 Vue 2 设计的&#xff0c;而 Element Plus 是 Element UI 的 Vue 3 版本。在 Element UI 和 Element Plus 中&#xff0c;并没有一个直接名为 “Loading 加载” 的独立组件。相反&#xff0c;加载效果通常是通过指令、…...

数据结构:栈(stack)详解 c++信息学奥赛基础知识讲解

目录 一、栈的定义 二、栈的操作 三、代码实操 四、栈的实现 1、string实现stack 2、vector实现stack 3、deque实现栈 一、栈的定义 stack是一个比较简单易用的数据结构&#xff0c;stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff…...

电商返利系统的高并发处理与性能优化

电商返利系统的高并发处理与性能优化 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 在电子商务平台中&#xff0c;返利系统是吸引用户和提升用户粘性的重要功…...

NPM 常用命令

NPM 常用命令 NPM&#xff08;Node Package Manager&#xff09;是 JavaScript 生态系统中最流行的包管理工具&#xff0c;它不仅可以管理 Node.js 项目的依赖&#xff0c;还提供了丰富的命令来管理和发布你的代码。本文将从不同角度&#xff0c;深入浅出地介绍 NPM 的常用命令…...

C++进修——C++核心编程

内存分区模型 C程序在执行时&#xff0c;将内存大方向划分为4个区域 代码区&#xff1a;存放函数体的二进制编码&#xff0c;由操作系统进行管理全局区&#xff1a;存放全局变量和静态变量以及常量栈区&#xff1a;由编译器自动分配释放&#xff0c;存放函数的参数值&#xff…...

【信息系统项目管理师知识点速记】项目文档管理

19.3 项目文档管理 信息系统相关信息(文档)是指某种数据媒体和其中所记录的数据。文档具有永久性,并可以由人或机器阅读,通常用于描述人工可读的内容。在软件工程中,文档常常用来表示对活动、需求、过程或结果进行描述、定义、规定、报告或认证的任何书面或图示的信息(包…...

服务器硬件,raid配置

文章目录 服务器硬件RAID磁盘阵列RAID 0RAID 1RAID 5RAID 6RAID 10 阵列卡&#xff0c;阵列卡的缓存阵列卡阵列卡的缓存 软RAID磁盘阵列RAID阵列的管理及设备恢复mdadm 服务器硬件 处理器(CPU)&#xff1a;服务器的核心组件&#xff0c;负责执行计算和指令操作。服务器常使用多…...

fc-list命令使用指南

fc-list命令使用指南 一、什么是fc-list? fc-list是FontConfig库的一部分&#xff0c;最初为Linux和其他Unix-like系统开发。我们可以用这个命令行快速查询和列出系统中安装的字体。 现在&#xff0c;Windows用户也集成了这个工具&#xff0c;所以我们来讲解一下用法。 二、…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...