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

算法(食物链)

240. 食物链

  •    题目

动物王国中有三类动物 A,B,C𝐴,𝐵,𝐶,这三类动物的食物链构成了有趣的环形。

A𝐴 吃 B𝐵,B𝐵 吃 C𝐶,C𝐶 吃 A𝐴。

现有 N𝑁 个动物,以 1∼N1∼𝑁 编号。

每个动物都是 A,B,C𝐴,𝐵,𝐶 中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这 N𝑁 个动物所构成的食物链关系进行描述:

第一种说法是 1 X Y,表示 X𝑋 和 Y𝑌 是同类。

第二种说法是 2 X Y,表示 X𝑋 吃 Y𝑌。

此人对 N𝑁 个动物,用上述两种说法,一句接一句地说出 K𝐾 句话,这 K𝐾 句话有的是真的,有的是假的。

当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

  1. 当前的话与前面的某些真的话冲突,就是假话;
  2. 当前的话中 X𝑋 或 Y𝑌 比 N𝑁 大,就是假话;
  3. 当前的话表示 X𝑋 吃 X𝑋,就是假话。

你的任务是根据给定的 N𝑁 和 K𝐾 句话,输出假话的总数。

输入格式

第一行是两个整数 N𝑁 和 K𝐾,以一个空格分隔。

以下 K𝐾 行每行是三个正整数 D,X,Y𝐷,𝑋,𝑌,两数之间用一个空格隔开,其中 D𝐷 表示说法的种类。

若 D=1𝐷=1,则表示 X𝑋 和 Y𝑌 是同类。

若 D=2𝐷=2,则表示 X𝑋 吃 Y𝑌。

输出格式

只有一个整数,表示假话的数目。

数据范围

1≤N≤500001≤𝑁≤50000,
0≤K≤100000

思路:

对于在同一颗树中的节点,根据节点和根节点之间的距离,在树内判断节点之间的关系。

对于不在同一个树内的节点,因为两个树当前没有相连,则代表两个树内的节点是没有任何关系的,则一定是真话,然后将两个树更新成一个大的树即可。

那么,是假话的可能有:

1.超过n

2.在同一个树里面,不满足对于规律(对于x吃x的情况,可以合并到其中)

本题要注意的点:

1.如何判断同一个树内的节点的关系,若x和y,(d[x]-d[y])%3=0,同类;=1(x吃y),=2(y吃x)

2.如何合并两个树:默认x的树合到y的树里。如果是x和y同类的情况,则此时x原本的跟px,要更新其到跟的距离,距离应该满足d[x]-d[y]+d[px]=0,则d[px]=d[y]-d[x]。对于捕食关系类似。

3.对于查找当前树的跟,同时更新点x到跟的距离:首先先跟新其父节点到跟的距离,然后d[x]+=d[p[x]],p[x]是x原本的父节点。

#include<iostream>
#include<cstring>
using namespace std;const int N=1000010;
int ph[N],dis[N];
int n,k;
int find(int x)
{   if(x!=ph[x]){   int t=find(ph[x]);//此处必须先求出ph[x]那个点到跟的距离,放到dis[ph[x]]中,才能去求dis[x],先后顺序要注意。dis[x]+=dis[ph[x]];ph[x]=t;}return ph[x];
}int main()
{   scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)ph[i]=i;int ans=0;while(k--){int d,x,y;scanf("%d%d%d",&d,&x,&y);if(x>n||y>n){ans++;}else{if(d==1){int px=find(x),py=find(y);if(px==py && (dis[x]-dis[y])%3)ans++;else if(px!=py){ph[px]=py;dis[px]=dis[y]-dis[x];}}else{   int px=find(x),py=find(y);if(px==py && (dis[x]-dis[y]-1)%3)ans++;else if(px!=py){ph[px]=py;dis[px]=dis[y]-dis[x]+1;}}}}printf("%d\n",ans);return 0;
}

相关文章:

算法(食物链)

240. 食物链 题目 动物王国中有三类动物 A,B,C&#x1d434;,&#x1d435;,&#x1d436;&#xff0c;这三类动物的食物链构成了有趣的环形。 A&#x1d434; 吃 B&#x1d435;&#xff0c;B&#x1d435; 吃 C&#x1d436;&#xff0c;C&#x1d436; 吃 A&#x1d434;。…...

ubuntu20.04系统安装zookeeper简单教程

Ubuntu系统中安装和配置Zookeeper的完整指南 Apache Zookeeper是一个开源的分布式协调服务&#xff0c;广泛用于分布式应用程序中管理配置、提供命名服务、分布式同步以及组服务等。在本教程中&#xff0c;我们将详细介绍如何在Ubuntu系统中安装Zookeeper&#xff0c;并进行相关…...

.NET Core 高性能并发编程

一、高性能大并发架构设计 .NET Core 是一个高性能、可扩展的开发框架&#xff0c;可以用于构建各种类型的应用程序&#xff0c;包括高性能大并发应用程序。为了设计和开发高性能大并发 .NET Core 应用程序&#xff0c;需要考虑以下几个方面&#xff1a; 1. 异步编程 异步编程…...

B 私域模式升级:开源技术助力传统经销体系转型

一、引言 1.1 研究背景 随着市场竞争加剧&#xff0c;传统经销代理体系面临挑战。同时&#xff0c;开源技术发展迅速&#xff0c;为 B 私域升级带来新机遇。在当今数字化时代&#xff0c;企业面临着日益激烈的市场竞争。传统的经销代理体系由于管理效率低下、渠道局限、库存压…...

vue之vuex的使用及举例

Vuex是专门为Vue.js设计的集中式状态管理架构&#xff0c;它允许你将所有的组件共享状态存储在一个单独的地方&#xff0c;即“store”&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化。以下是Vuex的基本使用方法&#xff1a; 一、安装Vuex 对于Vue 2项目&…...

使用 vite 快速初始化 shadcn-vue 项目

Vite 1. 创建项目 使用 vite 创建一个新的 vue 项目。 如果你正在使用 JS 模板&#xff0c;需要存在 jsconfig.json 文件才能正确运行 CLI。 # npm 6.x npm create vitelatest my-vue-app --template vue-ts# npm 7, extra double-dash is needed: npm create vitelatest m…...

微信小程序:一个小程序跳转至另一个小程序

一、微信小程序支持一个小程序跳转至另一个小程序吗&#xff1f; 支持。 1.1、目标小程序需开放被跳转&#xff1a;目标小程序需要在其 app.json 文件中配置 navigateToMiniProgramAppIdList&#xff0c;将源小程序的 AppID 加入其中。 1.2、用户授权&#xff1a;用户需要授…...

Java第二阶段---10方法带参---第二节 方法重载(Overloading)

1.概念 在同一个类中&#xff0c;方法名相同&#xff0c;参数列表不同的多个方法构造成方法重载 2.示例 public class Calculator{public int sum(int a,int b){return ab;}public int sum(int a,int b,int c){return abc;} } 3.误区 下面的方法是否属于方法重载&#xff…...

Java Web 之 Session 详解

在 JavaWeb 开发中&#xff0c;Session 就像网站的专属记忆管家&#xff0c;为每个用户保管着重要的信息和状态&#xff0c;确保用户在网站的旅程顺畅无阻。 场景一&#xff1a; 想象你去一家大型超市购物&#xff0c;推着购物车挑选商品。这个购物车就如同 Session&#xff…...

63.5 注意力提示_by《李沐:动手学深度学习v2》pytorch版

系列文章目录 文章目录 系列文章目录注意力提示生物学中的注意力提示查询、键和值注意力的可视化使用 show_heatmaps 显示注意力权重代码示例 代码解析结果 小结练习 注意力提示 &#x1f3f7;sec_attention-cues 感谢读者对本书的关注&#xff0c;因为读者的注意力是一种稀缺…...

vscode 的terminal 输出打印行数限制设置

修改 VSCODE 的 settings.json文件 "terminal.integrated.scrollback": 100000, {"extensions.ignoreRecommendations": true,"workbench.colorTheme": "Monokai","explorer.confirmDelete": false,"editor.fontSize…...

深入挖掘C++中的特性之一 — 继承

目录 1.继承的概念 2.举个继承的例子 3.继承基类成员访问方式的变化 1.父类成员的访问限定符对在子类中访问父类成员的影响 2.父类成员的访问限定符子类的继承方式对在两个类外访问子类中父类成员的影响 4.继承类模版&#xff08;注意事项&#xff09; 5.父类与子类间的转…...

Linux 下 poll 详解

在Linux系统编程中&#xff0c;poll 是一个强大的多路复用&#xff08;I/O 多路复用&#xff09;函数&#xff0c;用于同时监控多个文件描述符的事件&#xff0c;特别是在处理网络套接字或其他I/O设备时。相比于select&#xff0c;poll 支持监控更多的文件描述符&#xff0c;并…...

virtualbox配置为NAT模式后物理机和虚拟机互通

virtualbox配置为 NAT模式后&#xff0c;虚拟机分配到的 IP地址一般是 10.xx网段的&#xff0c;虚拟机可以通过网络地址转换访问物理机所在的网络&#xff0c;但若不做任何配置&#xff0c;则物理机无法直接访问虚拟机。 virtualbox在提供 NAT配置模式时&#xff0c;也提供了端…...

工程机械车辆挖掘机自卸卡车轮式装载机检测数据集VOC+YOLO格式2644张3类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;2644 标注数量(xml文件个数)&#xff1a;2644 标注数量(txt文件个数)&#xff1a;2644 标注…...

[Notepad++] 文本编辑器的下载及详细安装使用过程(附有下载文件)

程序员常用的文本编辑器Notepad&#xff0c;用于修改配置文件等 下载链接在文末 下载压缩包后解压 &#xff01;&#xff01;安装路径不要有中文 解压文件&#xff0c;得到 双击exe文件 选择简体中文&#xff0c;点击OK 点击下一步 点击“我接受” 更改安装目录&#xff0c;不…...

深入浅出Java多线程(六):Java内存模型

引言 大家好&#xff0c;我是你们的老伙计秀才&#xff01;今天带来的是[深入浅出Java多线程]系列的第六篇内容&#xff1a;Java内存模型。大家觉得有用请点赞&#xff0c;喜欢请关注&#xff01;秀才在此谢过大家了&#xff01;&#xff01;&#xff01; 在并发编程中&#xf…...

注册了个小趴菜999#it#com

注册了个 999#it#com 拿着玩玩吧 现在二级域名竟然也让注册了 不过cn.com的二级似乎早就可以了...

UE4 材质学习笔记02(数据类型/扭曲着色器)

一.什么是数据类型 首先为啥理解数据类型是很重要的。一些节点的接口插槽只接受特定类型的数据&#xff0c;如果连接了不匹配的数据就会出现错误&#xff0c;有些接口可以接受任何数据类型&#xff0c;但是实际上只会使用到其中的一些。并且有时可以将多个数据流合并成一个来编…...

Linux驱动开发(速记版)--设备树插件

第六十八章 设备树插件介绍 Linux 4.4之后引入了动态设备树&#xff0c;其中的设备树插件&#xff08;Device Tree Overlay&#xff09;是一种扩展机制&#xff0c;允许在运行时动态添加、修改或删除设备节点和属性。 设备树插件机制通过DTS&#xff08;设备树源文件&#xff0…...

Simulink双矢量MPC实战:从郭磊磊论文到可运行的Matlab Function代码(调制模型预测控制详解)

Simulink双矢量MPC实战&#xff1a;从理论到代码的完整实现路径 当我在实验室第一次尝试复现郭磊磊老师那篇经典论文时&#xff0c;面对12种矢量组合和复杂的PWM生成逻辑&#xff0c;完全不知从何下手。经过三个月的反复试验和代码调试&#xff0c;终于摸清了从论文公式到可运行…...

ECharts折线图入门学习:从基础到实战的完整指南

引言 折线图是数据可视化中最常用的图表类型之一&#xff0c;特别适合展示数据随时间变化的趋势。ECharts作为一款功能强大的JavaScript可视化库&#xff0c;提供了丰富的配置选项和交互功能&#xff0c;能够轻松创建出专业、美观的折线图。本文将带领大家从零开始学习ECharts折…...

一个月突变!Linux内核大佬懵了:上个月还是“AI垃圾”,这个月AI Bug报告却突然靠谱?

整理 | 郑丽媛出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09;最近在做开源项目维护的开发者&#xff0c;可能会有一种奇怪的错觉&#xff1a;Bug 似乎报告变多了&#xff0c;而且变准了——更准确地说&#xff0c;是 AI 报的 Bug&#xff0c;突然开始“靠谱了”。…...

嵌入式系统代码执行时间测量方法与优化

1. 嵌入式程序运行时间测量的必要性在嵌入式系统开发中&#xff0c;精确测量代码执行时间是每个工程师必备的技能。无论是优化算法效率、调试实时系统&#xff0c;还是验证硬件性能&#xff0c;时间测量都扮演着关键角色。以STM32为例&#xff0c;当我们需要确认一个延时函数是…...

从Simulink到实物:单闭环直流调速仿真如何指导真实的Arduino/STM32控制?

从Simulink到Arduino&#xff1a;如何将直流电机控制算法从仿真落地到真实硬件 当你第一次在Simulink中看到那个完美的电机转速响应曲线时&#xff0c;那种成就感是无可替代的。但很快&#xff0c;一个更迫切的问题出现了&#xff1a;这些漂亮的仿真结果&#xff0c;如何变成手…...

WSL+VSCode+Jupyter+R配置总结(2026年)

题记&#xff1a;网上相关的资料很多了&#xff0c;现阶段跟随AI也能少走很多弯路&#xff0c;但体验下来依旧有些细节没有被很好的提及&#xff0c;故写本文一方面作为自己的备忘录&#xff0c;一方面希望帮助更多像我一样的新手。 用了上述的配置跑了scanpy一年多了&#xf…...

Win11Debloat开源工具:焕新Windows系统体验的极简优化指南

Win11Debloat开源工具&#xff1a;焕新Windows系统体验的极简优化指南 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutter an…...

手把手教你用VSCode给Ai-WB2-12F烧录固件(含串口调试技巧)

手把手教你用VSCode给Ai-WB2-12F烧录固件&#xff08;含串口调试技巧&#xff09; 在物联网开发中&#xff0c;固件烧录是最基础也是最重要的环节之一。对于Ai-WB2-12F这款热门Wi-Fi/BLE双模模组&#xff0c;掌握高效的烧录方法能显著提升开发效率。本文将详细介绍如何利用VSC…...

ftools架构深度解析:Stata大数据处理的技术革命

ftools架构深度解析&#xff1a;Stata大数据处理的技术革命 【免费下载链接】ftools Fast Stata commands for large datasets 项目地址: https://gitcode.com/gh_mirrors/ft/ftools 在数据科学和经济学研究的实践中&#xff0c;Stata用户经常面临一个共同的挑战&#x…...

H5页面如何优雅跳转iOS App Store?解决点击后二次跳转的坑

H5页面如何优雅跳转iOS App Store&#xff1f;解决点击后二次跳转的坑 在移动互联网时代&#xff0c;H5页面与原生App的无缝衔接已经成为提升用户体验的关键环节。特别是对于电商、社交、内容平台等需要引导用户下载App的场景&#xff0c;如何实现从H5页面到iOS App Store的平…...