【食物链】
题目

代码
#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文本简单解析
需求 支持文本插入,比如 xxx {product_name} xxx ,如果提供了product_name变量的值为feedback,则可以渲染出 xxx feedback xxx。支持链接解析,比如 [baidu](https://www.baidu.com/),可以直接渲染成超链接的形式。支持…...
webpack plugin
webpack plugin webpack完成的复杂炫酷的功能依赖于插件机制,webpack的插件机制依赖于核心的库, tapable tapable是一个类似于nodejs的eventEmitter的库, 主要是控制钩子函数的发布喝定于,当时,tapable提供您的hook机…...
【busybox记录】【shell指令】date
目录 内容来源: 【GUN】【date】指令介绍 【busybox】【date】指令介绍 【linux】【date】指令介绍 使用示例: 打印前天的日期: 打印三个月零一天后的日期: 打印当年圣诞节的年数: 打印当前的全月名称和月的日期: 要打印一个没有前导零的日期&…...
同态加密和SEAL库的介绍(八)性能
本篇会对比三种加密方案,同时每种方案配置三种参数。即九种情况下的各个操作的性能差异,为大家选择合适的方案和合适的参数提供参考。表格中所有时长的单位均为微妙,即 。 当然数据量比较大,为了方便大家查找,…...
华为OD-D卷数的分解
给定一个正整数n,如果能够分解为m(m > 1)个连续正整数之和,请输出所有分解中,m最小的分解。 如果给定整数无法分解为连续正整数,则输出字符串"N"。 输入描述: 输入数据为一整数,范围为(1, 2^3…...
rk3588 low_delay_net_display注意事项
low_delay_net_display例子默认只支持YUV420和RGB888,如果需要支持YUV422,请添加下面部分: 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 入门:从零到一构建你的第一个应用 Spring Boot 作为一个流行的Java框架,以其“习惯优于配置”的理念极大地简化了Spring应用的开发和部署过程。本文将带你一步步创建一个简单的Spring Boot应用,从环境准备到项目创建,…...
Linux云计算 |【第二阶段】NETWORK-DAY2
主要内容: VLAN技术、TRUNK模式、链路聚合、路由器 一、VLAN技术应用 广播域指接受同样广播消息的节点的集合,如在该集合中的任何一个节点传输一个广播帧,则所有其它能收到这个帧的节点都被认为是该广播帧的一部分; 交换机的所有…...
Java面试题(基础篇)③
目录 一, 与 equals 的区别? 二,接口和抽象类的区别? 三,请说出几个常见的异常? 四,请问你对Java 反射有了解吗? 五,浅拷贝和深拷贝区别? 一,…...
Qt动态调用 - QMetaObject::invokeMethod
QMetaObject::invokeMethod 动态调用是 Qt 的元对象系统的一项强大功能,它允许在运行时通过名称调用槽函数、信号和普通成员函数。 这种能力对于构建灵活和可扩展的应用程序非常有用,比如插件系统或脚本接口。 动态调用方法 Qt 提供了 QMetaObject::i…...
html+css+js网页设计 星享咖啡6个页面(带js) ui还原度90%
htmlcssjs网页设计 星享咖啡6个页面(带js) ui还原度90% 网页作品代码简单,可使用任意HTML编辑软件(如:Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等…...
docker上传镜像至阿里云
1、安装wsl2 WSL2安装(详细过程) 2、安装docker Docker在Windows下的安装及使用 3、创建私人阿里云镜像库 如何创建私人阿里云镜像仓库?(保姆级) 4、如何删除容器 (1) 查找正在使用该图像的容器 docker ps -a --filte…...
POS刷卡开发源码之语音播报-CyberWinApp-SAAS 本地化及未来之窗行业应用跨平台架构
一、终端语音提醒的好处 1. 增强信息传递的有效性:在人们忙碌或者注意力分散时,语音提醒能够直接穿透噪音和干扰,确保重要信息被准确接收。 2. 提高操作的便捷性:用户无需停下手中的工作去查看屏幕或阅读文字,直接通过…...
jupyter notebook魔法命令
%xmode 魔法命令来控制异常报告: 输入魔法命令:在 IPython 或 Jupyter Notebook 的一个新单元格中,输入以下命令之一来设置异常报告模式: 切换到 Plain 模式(简洁输出): %xmode Plain切换回 Con…...
Mysql事件
1:查询全局事件开关是否启动 SHOW VARIABLES LIKE %sche%; 关闭状态!!!去开启如果已开启忽略 set global event_scheduler ON; ojbk 2:创建事件 step1: 链接打开自己的数据库 step2: 找…...
Unity Console 窗口输出对齐
起因:做了个工具在console窗口罗列一些信息,基本结构是 [ 文件名 :行号 ],因为文件,行号长度不一,想要做到如下效果。 初步尝试,用以下方法: string format "{0,-10} …...
leetcode198_打家劫舍
思路 动态规划 func rob(nums []int) int {if len(nums) < 2 {return nums[0]}// dp[i] 表示到第i家为止,小偷能够偷窃到的最高金额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# 串口通讯怎么防止数据丢失
串口通信(Serial Communication)是计算机与设备之间进行数据交换的一种方式。在C#中进行串口通信时,防止数据丢失可以采取以下一些措施: 1.校验和(Checksum):在发送数据时,计算数据的…...
【机器学习】BP神经网络中的链式法则:解开智能背后的数学奥秘
在浩瀚的机器学习领域中,BP(反向传播)神经网络如同一座桥梁,连接着复杂的数据世界与智能的彼岸。而这座桥梁的基石之一,便是链式法则(Chain Rule)——一个看似简单却蕴含无限智慧的数学原理。今…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
