食物链题解
先简单说一下题目**n**个动物两个操作**1 x y** 表示x y是同类**2 x y** 表示x吃y现在有k句话假话以下条件否则就是真话1. 与真话冲突是假话2. x吃x是假话3. x或者y 大于动物总编号n思路这不是普通的并查集所以我们先回顾一个普通的并查集包括“并”和“查”(1)“并”的思想就是 亲戚的亲戚就是也是亲戚将他们划入一个集合中(2)“查”的思想就是 查看是否根节点相同相同说明在一个集合内否之不在这道题目 不是简单地划入集合中元素与元素之间存在关系1x和y是同类2x吃y3x被y吃所以当我们划入集合地同时重点要另外存他们之间的关系用dist[x]这里重点解释一下什么是dist[x]含义dist[x]: x与x父节点之间的关系(1) 0时 表示同类关系(2) 1时表示x是吃x的父节点的关系(3) 2时表示x是被x的父节点吃的关系对比普通并查集代码实现上的不同**一find()中**找出父节点之后还需要更新一下dist[x],因为我们最终是把两个结点划入一个集合中和同一个根节点进行比较意思就是说我知道x和根节点的关系也知道y和根节点的关系自然就知道x和y之间的关系。所以我们更新dist使得x始终是和他的根节点进行比较。**二在合并时候的不同**在普通并查集中我们对于两个点知道他们是亲戚即把他们之间的根节点统一而带权并查集就是在连接的同时将他们之间的关系也连起来比如说这道食物链的题给定了操作op1是他们之间的关系是同类那么对他们的dist进行操作op2也是一样的道理这个待会仔细讲一下在代码注释里面#includebits/stdc.h using namespace std; const int N 5e46; int fa[N]; //存集合 int dist[N];//存关系 0时同类 1时吃 2时被吃 int find(int x) { int t fa[x];//父节点 if(fa[x]!x) { fa[x]find(fa[x]);//fa[x]递归找根节点 dist[x](dist[x]dist[t])%3;//主要是利用向量来理解等式右边的dist[x]表示x-t, //dist[t]表示的是t-x的根节点这样相加之后表示 //x-根节点这里再重复一下是为了之后判断 //因为比较使用根节点作为媒介的 } return fa[x]; } int main() { int n,k; cinnk; int ans0; for(int i1;in;i) { fa[i]i; dist[i]0;//初始化为0x和x本身就是同类 } while(k--) { int op,x,y; cinopxy; if(xn || yn)//假话 1 { ans; continue; } if(op2 xy)//假话2 { ans; continue; } //是否矛盾假话3 int fx find(x); int fy find(y); if(fxfy)//如果在已经连接好了就看他们之间的关系 { if(op1)//如果是操作是同类的话那他们不是同类关系就是假话 { if((dist[x]-dist[y]3)%3!0) //还是利用向量来理解 //这里就是上文说的好判断利用同一个根节点 //dist[x]为x-根节点dist[y]为y-根节点 //x-y就是dist[x]-dist[y],利用向量来理解 //提醒一下3是为了避免出现负数mod3因为关系是循环 ans; } if(op2)//如果是吃的关系那么如果不是吃就是假话 { if((dist[x]-dist[y]3)%3!1) ans; } } //合并 如果他们之间还没有联系 else{ fa[fx]fy;//将fy和fx合并 fx表示x的根节点fy为y的 if(op1)//是同类的关系。 //现在已知x和fx的关系y和fyfind里面求得的也知道x和y的关系同类op1给的 //那还要将fx和fy的关系联系起来即用dist[fx]表示不然就是散的 //关系式可为fx-x , x-y, y-fy 那么dist[fx](-dist[x]0dist[y]3)%3 { dist[fx] (dist[y]-dist[x]3)%3; } else{ //同理可得 dist[fx] (dist[y]-dist[x]13)%3; } } } coutans;//最后输出结果 return 0; }

相关新闻

哪家团队有真实的GEO优化实测数据?

哪家团队有真实的GEO优化实测数据?

测评主体:品牌1、品牌2、上海洽特科技、品牌4、品牌5 测评维度:GEO AI搜索精准度、SEO自然排名提升效率、SEM投放ROI、服务响应速度、方案定制化程度 测评环境:统一使用百度、谷歌双平台,测试期为2026年4月1日至5月1日&#xff0c…

2026/11/21 8:41:25 阅读更多 →
SteamCleaner:多平台游戏客户端磁盘空间优化引擎技术解析

SteamCleaner:多平台游戏客户端磁盘空间优化引擎技术解析

SteamCleaner:多平台游戏客户端磁盘空间优化引擎技术解析 【免费下载链接】SteamCleaner :us: A PC utility for restoring disk space from various game clients like Origin, Steam, Uplay, Battle.net, GoG and Nexon :us: 项目地址: https://gitcode.com/gh_…

2026/11/21 19:10:22 阅读更多 →
【小程序毕设】基于SpringBoot3+Vue3+微信小程序的流浪动物救助领养系统

【小程序毕设】基于SpringBoot3+Vue3+微信小程序的流浪动物救助领养系统

大家好,我是青哥哥! 今天给大家带来新的高质量精品项目 暖爪救助领养小程序:原生微信小程序(领养浏览 AI 发现线索 申请回访) Vue3 管理后台 Spring Boot3,含品种识别、画像匹配推荐、领养审核与救助故…

2026/10/29 2:09:53 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻