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

【食物链】

题目

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int n, k;
int p[N], d[N];
int find(int x)
{if(p[x] != x){int root = find(p[x]);d[x] += d[p[x]];p[x] = root;}return p[x];
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) p[i] = i;int res = 0;cin >> k;while(k--){int t, a, b;cin >> t >> a >> b;if(a > n || b > n){res++;continue;}int pa = find(a), pb = find(b);if(t == 1){if(pa == pb && (d[a] - d[b]) % 3) res++;else if(pa != pb){p[pa] = pb;d[pa] = d[b] - d[a];}}else{if(pa == pb && (d[a] - d[b] - 1) % 3) res++;else if(pa != pb){p[pa] = pb;d[pa] = d[b] - d[a] + 1;}}}cout << res;return 0;
}

注意

1.边界判断别漏

2.涉及到distance的问题,pa == pb且不矛盾的情况不能简单归类为else,不然d[pa]会发生实际变化

思考

关于存储

策略为通过相对距离存储关系

对于a, b

d[a] = d[b]

对应d[pa] = d[b] - d[a];

首先pa和b距离pb同一长度,然后减小pa与a的间距d[a],导致a与b同一权重(别管pa,pa肯定离pb更近了)

同理

对于a, b

d[a] = d[b] + 1

对应d[pa] = d[b] - d[a] + 1

一句话:最主要是在相对距离的玩法下,增加pa距离父节点的距离,就等于增加a距离根节点的距离。

关于使用

pa与pb不相等,说明a, b关系此前不存在(即便间接a, x    x,y也没有)

因此将pa树纳入pb下,并对于a, b进行距离调整

最后可预见的是一片关系森林,每个size > 1树上的元素a, b都有一个基本的性质(pa == pb)

size = 1的树肯定找不到pa == pb的情况,由此区分有旧关系,和新关系。

举例判定2类型矛盾的代码

在有旧关系的基础上,不满足(d[a] - d[b] - 1) % 3的情况(之前有关系,和现在的不矛盾)只有当d[a] - d[b]的差模3余1(代表a吃b)。

也即考虑加粗部分在不矛盾的情况下模3余0即可得到代码。

相关文章:

【食物链】

题目 代码 #include<bits/stdc.h> using namespace std; const int N 5e410; int n, k; int p[N], d[N]; int find(int x) {if(p[x] ! x){int root find(p[x]);d[x] d[p[x]];p[x] root;}return p[x]; } int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)…...

【RN】实现markdown文本简单解析

需求 支持文本插入&#xff0c;比如 xxx {product_name} xxx &#xff0c;如果提供了product_name变量的值为feedback&#xff0c;则可以渲染出 xxx feedback xxx。支持链接解析&#xff0c;比如 [baidu](https://www.baidu.com/)&#xff0c;可以直接渲染成超链接的形式。支持…...

webpack plugin

webpack plugin webpack完成的复杂炫酷的功能依赖于插件机制&#xff0c;webpack的插件机制依赖于核心的库&#xff0c; tapable tapable是一个类似于nodejs的eventEmitter的库&#xff0c; 主要是控制钩子函数的发布喝定于&#xff0c;当时&#xff0c;tapable提供您的hook机…...

【busybox记录】【shell指令】date

目录 内容来源&#xff1a; 【GUN】【date】指令介绍 【busybox】【date】指令介绍 【linux】【date】指令介绍 使用示例&#xff1a; 打印前天的日期: 打印三个月零一天后的日期: 打印当年圣诞节的年数: 打印当前的全月名称和月的日期: 要打印一个没有前导零的日期&…...

同态加密和SEAL库的介绍(八)性能

本篇会对比三种加密方案&#xff0c;同时每种方案配置三种参数。即九种情况下的各个操作的性能差异&#xff0c;为大家选择合适的方案和合适的参数提供参考。表格中所有时长的单位均为微妙&#xff0c;即 。 当然数据量比较大&#xff0c;为了方便大家查找&#xff0c…...

华为OD-D卷数的分解

给定一个正整数n&#xff0c;如果能够分解为m(m > 1)个连续正整数之和&#xff0c;请输出所有分解中&#xff0c;m最小的分解。 如果给定整数无法分解为连续正整数&#xff0c;则输出字符串"N"。 输入描述: 输入数据为一整数&#xff0c;范围为&#xff08;1, 2^3…...

rk3588 low_delay_net_display注意事项

low_delay_net_display例子默认只支持YUV420和RGB888,如果需要支持YUV422&#xff0c;请添加下面部分&#xff1a; rk3588_nvr/build/app/low_delay_net_display$ git diff v4l2HdmiRX.cpp diff --git a/app/low_delay_net_display/v4l2HdmiRX.cpp b/app/low_delay_net_displa…...

Spring Boot 快速入门样例【后端 3】

Spring Boot 入门&#xff1a;从零到一构建你的第一个应用 Spring Boot 作为一个流行的Java框架&#xff0c;以其“习惯优于配置”的理念极大地简化了Spring应用的开发和部署过程。本文将带你一步步创建一个简单的Spring Boot应用&#xff0c;从环境准备到项目创建&#xff0c;…...

Linux云计算 |【第二阶段】NETWORK-DAY2

主要内容&#xff1a; VLAN技术、TRUNK模式、链路聚合、路由器 一、VLAN技术应用 广播域指接受同样广播消息的节点的集合&#xff0c;如在该集合中的任何一个节点传输一个广播帧&#xff0c;则所有其它能收到这个帧的节点都被认为是该广播帧的一部分&#xff1b; 交换机的所有…...

Java面试题(基础篇)③

目录 一&#xff0c; 与 equals 的区别&#xff1f; 二&#xff0c;接口和抽象类的区别&#xff1f; 三&#xff0c;请说出几个常见的异常&#xff1f; 四&#xff0c;请问你对Java 反射有了解吗&#xff1f; 五&#xff0c;浅拷贝和深拷贝区别&#xff1f; 一&#xff0c…...

Qt动态调用 - QMetaObject::invokeMethod

QMetaObject::invokeMethod 动态调用是 Qt 的元对象系统的一项强大功能&#xff0c;它允许在运行时通过名称调用槽函数、信号和普通成员函数。 这种能力对于构建灵活和可扩展的应用程序非常有用&#xff0c;比如插件系统或脚本接口。 动态调用方法 Qt 提供了 QMetaObject::i…...

html+css+js网页设计 星享咖啡6个页面(带js) ui还原度90%

htmlcssjs网页设计 星享咖啡6个页面&#xff08;带js&#xff09; ui还原度90% 网页作品代码简单&#xff0c;可使用任意HTML编辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等…...

docker上传镜像至阿里云

1、安装wsl2 WSL2安装&#xff08;详细过程&#xff09; 2、安装docker Docker在Windows下的安装及使用 3、创建私人阿里云镜像库 如何创建私人阿里云镜像仓库&#xff1f;&#xff08;保姆级&#xff09; 4、如何删除容器 (1) 查找正在使用该图像的容器 docker ps -a --filte…...

POS刷卡开发源码之语音播报-CyberWinApp-SAAS 本地化及未来之窗行业应用跨平台架构

一、终端语音提醒的好处 1. 增强信息传递的有效性&#xff1a;在人们忙碌或者注意力分散时&#xff0c;语音提醒能够直接穿透噪音和干扰&#xff0c;确保重要信息被准确接收。 2. 提高操作的便捷性&#xff1a;用户无需停下手中的工作去查看屏幕或阅读文字&#xff0c;直接通过…...

jupyter notebook魔法命令

%xmode 魔法命令来控制异常报告&#xff1a; 输入魔法命令&#xff1a;在 IPython 或 Jupyter Notebook 的一个新单元格中&#xff0c;输入以下命令之一来设置异常报告模式&#xff1a; 切换到 Plain 模式&#xff08;简洁输出&#xff09;&#xff1a; %xmode Plain切换回 Con…...

Mysql事件

1&#xff1a;查询全局事件开关是否启动 SHOW VARIABLES LIKE %sche%; 关闭状态&#xff01;&#xff01;&#xff01;去开启如果已开启忽略 set global event_scheduler ON; ojbk 2&#xff1a;创建事件 step1&#xff1a; 链接打开自己的数据库 step2&#xff1a; 找…...

Unity Console 窗口输出对齐

起因&#xff1a;做了个工具在console窗口罗列一些信息&#xff0c;基本结构是 [ 文件名 &#xff1a;行号 ]&#xff0c;因为文件&#xff0c;行号长度不一&#xff0c;想要做到如下效果。 初步尝试&#xff0c;用以下方法&#xff1a; string format "{0,-10} …...

leetcode198_打家劫舍

思路 动态规划 func rob(nums []int) int {if len(nums) < 2 {return nums[0]}// dp[i] 表示到第i家为止&#xff0c;小偷能够偷窃到的最高金额dp : make([]int, len(nums))dp[0] nums[0]dp[1] max(nums[0], nums[1])for i:2; i<len(nums); i {if nums[i] dp[i-2] &…...

C# 串口通讯怎么防止数据丢失

串口通信&#xff08;Serial Communication&#xff09;是计算机与设备之间进行数据交换的一种方式。在C#中进行串口通信时&#xff0c;防止数据丢失可以采取以下一些措施&#xff1a; 1.校验和&#xff08;Checksum&#xff09;&#xff1a;在发送数据时&#xff0c;计算数据的…...

【机器学习】BP神经网络中的链式法则:解开智能背后的数学奥秘

在浩瀚的机器学习领域中&#xff0c;BP&#xff08;反向传播&#xff09;神经网络如同一座桥梁&#xff0c;连接着复杂的数据世界与智能的彼岸。而这座桥梁的基石之一&#xff0c;便是链式法则&#xff08;Chain Rule&#xff09;——一个看似简单却蕴含无限智慧的数学原理。今…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

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

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

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...