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

洛谷【P1955 [NOI2015] 程序自动分析】

反思:

  • 这道题一眼就是并查集 但是数据太大 mle和re都是有可能的
  • 我看了题解才知道是离散化数组加并查集
  • 离散化再两个月前我觉得好难啊 那道题跟本看不懂 现在觉得还行

离散化思路:

需要一个离散记录数组----ls[N]用来记录下出现的数
步骤:
先存数组
排序
unique去重得长度
然后用lower_bound迭代器赋值
unique用法是int len=unique(li+1,li+1+cnt)-li-1;  (start,start+总长度)-start  得到最后长度’ne[i].a=lower_bound(li+1,li+len+1,ne[i].a)-li-1;
lower_bound的用法:返回大于等于ne[i].a的最早位置
写法跟上面类似:(start,start+长度,数大小)-start

题目思路:

先离散化缩小区间 再进行并查集操作 结构体要排序 按0和1排 1在前面 对于循环中是0的进行判断祖先节点是否相等 相等就矛盾 打印no 直到循环结束flag还为1的话就打印yes

ac代码
#include<bits/stdc++.h>
using namespace std;
//离散化步骤:排序,去重,赋值
const int N=300000;
int li[N],fa[N];
void first(int x){for(int i=1;i<=x;i++) fa[i]=i;
}
int find(int x){if(fa[x]==x) return x;fa[x]=find(fa[x]);return fa[x];
}
void merge(int a,int b){int t1=find(a),t2=find(b);fa[t1]=t2;
}
struct node{int a,b,c;
}ne[100010];
bool cmp(node a,node b){return a.c>b.c;
}
int main(){int n;cin>>n;while(n--){memset(fa,0,sizeof(fa));memset(li,0,sizeof(li));int t;cin>>t;int cnt=0;for(int i=1;i<=t;i++){int x,y,z;cin>>x>>y>>z;ne[i]={x,y,z};li[++cnt]=x,li[++cnt]=y;//输入完成 开始离散}sort(li+1,li+cnt+1);//从1开始int len=unique(li+1,li+1+cnt)-li-1;// cout<<len<<endl;//len是用来  loow_bound里面的和初始化first的for(int i=1;i<=t;i++){//离散赋值ne[i].a=lower_bound(li+1,li+len+1,ne[i].a)-li-1;ne[i].b=lower_bound(li+1,li+len+1,ne[i].b)-li-1;}// for(int i=1;i<=t;i++){// //离散赋值// // ne[i].a=lower_bound(li+1,li+cnt+1,ne[i].a)-li-1;// // ne[i].b=lower_bound(li+1,li+cnt+1,ne[i].b)-li-1;// cout<<ne[i].a<<" "<<ne[i].b<<endl;// }first(len);bool flag=1;sort(ne+1,ne+1+t,cmp);// for(int i=1;i<=t;i++){// cout<<ne[i].a<<" "<<ne[i].b<<" "<<ne[i].c<<endl;// }'for(int i=1;i<=t;i++){if(ne[i].c==1){merge(ne[i].a,ne[i].b);}else if(ne[i].c==0){if(find(ne[i].a)==find(ne[i].b)){cout<<"NO"<<endl;flag=0;break;}}}if(flag==1) cout<<"YES"<<endl;}return 0;
}

相关文章:

洛谷【P1955 [NOI2015] 程序自动分析】

反思&#xff1a; 这道题一眼就是并查集 但是数据太大 mle和re都是有可能的我看了题解才知道是离散化数组加并查集离散化再两个月前我觉得好难啊 那道题跟本看不懂 现在觉得还行 离散化思路&#xff1a; 需要一个离散记录数组----ls[N]用来记录下出现的数 步骤&#xff1a; …...

Swift并发笔记

1.同步和异步 说到线程的执行方式&#xff0c;最基本的一组概念是同步和异步。所谓同步&#xff0c;就是在操作执行完成之前&#xff0c;运行操作的这个线程都会被占用&#xff0c;直到函数最终被抛出或返回。Swift5.5之前&#xff0c;func关键字声明的所有的函数都是同步的。…...

React 组件命名规范

在 React 项目中&#xff0c;如果希望保持组件命名的一致性&#xff0c;并防止在引入时出现不同名称的问题&#xff0c;可以遵循以下的组件规范&#xff1a; 1、默认导出组件&#xff1a; 所有特殊要求的组件&#xff08;如页面组件或根组件&#xff09;应该使用 export defau…...

eNSP网络配置指南:IP设置、DNS、Telnet、DHCP与路由表管理

1.eNSP基本操作和路由器IP配置命令 登录设备&#xff1a;通过Console口或通过eNSP的Telnet/SSH客户端登录到设备。进入特权模式&#xff1a;输入system-view进入系统视图。接口配置&#xff1a; 进入接口视图&#xff0c;例如interface GigabitEthernet0/0/0。配置IP地址和子网…...

初步认识产品经理

产品经理 思考问题的维度 1️⃣为什么要抓住核心用户&#xff1f; 所有和产品有关系的群体就是用户&#xff0c;存在共性和差异了解用户的付费点&#xff0c;更好的优化产品是否使用&#xff1a;&#xff08;目标用户-已使用产品&#xff1a;种子用户-尝鲜&#xff1b;核心用…...

web前端面试中拍摄的真实js面试题(真图)

web前端面试中拍摄的真实js面试题&#xff08;真图&#xff09; WechatIMG258.jpeg WechatIMG406.jpeg WechatIMG407.jpeg WechatIMG922.jpeg WechatIMG1063.jpeg © 著作权归作者所有,转载或内容合作请联系作者 喜欢的朋友记得点赞、收藏、关注哦&#xff01;&#xff01;…...

python 人工智能 机器学习 当损失函数的数值变成 `nan` 时,这通常意味着在模型训练过程中出现了数值不稳定性以及解决办法,数据分析

当损失函数的数值变成 nan 时&#xff0c;这通常意味着在模型训练过程中出现了数值不稳定性。以下是一些可能导致这个问题的原因以及相应的解决方法&#xff1a; 1. **学习率过高**&#xff1a;如果学习率设置得过高&#xff0c;可能会导致梯度爆炸&#xff0c;从而导致损失函…...

Kafka快速实战与基本原理详解

笔记:https://note.youdao.com/ynoteshare/index.html?id=b0357bdb4821ed2e35ecdbdacd65aa06&type=note&_time=1727570043631 启动kafka之前先启动zookper 看看ZK里面都有什么数据 : 刚开始什么数据都没有 接下来启动kafka,启动好后,日志在这里看: 启动好了kaf…...

tftp传文件被服务器拒绝进入tftp: server error: (768) Access to staonline.pcap denied

环境&#xff1a;测试一个ac下挂ap&#xff0c;ap下的抓包文件传出时&#xff0c;出现问题&#xff1a; ac的wan口ip是192.168.186.167/24&#xff0c;gw是192.168.186.1&#xff0c;下挂ap的ip是192.168.202.199/24&#xff0c;ac上开子接口192.168.202.1/24&#xff0c;ac上开…...

express,生成用户登录后的 token

在 Node.js 中使用 Express 框架生成用户登录后的 token&#xff0c;通常会涉及到以下几个步骤&#xff1a; 设置 Express 应用&#xff1a;首先&#xff0c;你需要有一个基本的 Express 应用。安装必要的中间件&#xff1a;例如 jsonwebtoken&#xff08;JWT&#xff09;用于…...

银河麒麟桌面操作系统修改默认Shell为Bash

银河麒麟桌面操作系统修改默认Shell为Bash &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 在银河麒麟桌面操作系统&#xff08;ARM版&#xff09;中&#xff0c;若要将默认Shell从Dash改为Bash&#xff0c;可执行以下步骤&#xff1a; 打开…...

卷积神经网络(Convolutional Neural Networks, CNN)

卷积神经网络&#xff08;Convolutional Neural Networks, CNN&#xff09;是深度学习领域中用于处理具有网格结构的输入&#xff08;如图像和视频&#xff09;的神经网络模型。下面以最简单、直观的方式概述CNN的主要流程及其基本概念&#xff1a; 1. 输入层 概念&#xff1a…...

SpringBoot系列 启动流程

文章目录 SpringApplicationSpringApplication#run 启动流程BootstrapContextSpringApplicationRunListenersprepareEnvironmentconfigureEnvironmentconfigurePropertySourcesconfigureProfiles 上下文初始化prepareContextrefreshContextprepareRefreshobtainFreshBeanFactor…...

vgg19提取特征

一般来说&#xff0c;大家使用VGG16&#xff0c;用的是第四列的网络架构&#xff0c;而使用VGG19&#xff0c;使用的就是第六列的网络架构。 使用vgg进行提取特征&#xff0c;在这个项目中&#xff0c;使用的就是每一块卷积层的第一层。 import torch.nn as nn from torchvis…...

Qt 中的 QChartView

深入理解 Qt 的 QChartView&#xff1a;图表展示与交互 QChartView 是 Qt Charts 模块中的一个核心类&#xff0c;它用于在 Qt 应用程序中显示图表&#xff0c;并支持多种用户交互方式。它继承自 QGraphicsView&#xff0c;通过封装 QChart&#xff0c;为用户提供了强大的图表…...

cheese安卓版纯本地离线文字识别插件

目的 cheese自动化平台是一款可以模拟鼠标和键盘操作的自动化工具。它可以帮助用户自动完成一些重复的、繁琐的任务&#xff0c;节省大量人工操作的时间。可以采用Vscode、IDEA编写&#xff0c;支持Java、Python、nodejs、GO、Rust、Lua。cheese也包含图色功能&#xff0c;识别…...

【C++】多肽

目录 一 多肽定义 1. 多肽的构成条件 1 例一 2 例二 2. 虚函数 3. 虚函数重写的两个意外 1 协变 2 析构函数的重写 二 关键字override 和 final 1. final 2.override 三 三重对比 1. 练习 四 多肽的原理 1. 多肽调用和普通调用 2.虚函数表 3. 分析 4. 原理 …...

Linux下Socket编程

1. Socket简介 Socket是什么&#xff1f; Socket是一种进程间通信的机制&#xff0c;通过它应用程序可以通过网络进行数据传输。Socket提供了一种跨平台的接口&#xff0c;使得同样的代码可以在不同的操作系统上运行。Socket类型 流式套接字&#xff08;SOCK_STREAM&#xff0…...

Scrapy 爬虫的大模型支持

使用 Scrapy 时&#xff0c;你可以轻松使用大型语言模型 (LLM) 来自动化或增强你的 Web 解析。 有多种使用 LLM 来帮助进行 Web 抓取的方法。在本指南中&#xff0c;我们将在每个页面上调用一个 LLM&#xff0c;从中抽取我们定义的一组属性&#xff0c;而无需编写任何选择器或…...

数据仓库简介(一)

数据仓库概述 1. 什么是数据仓库&#xff1f; 数据仓库&#xff08;Data Warehouse&#xff0c;简称 DW&#xff09;是由 Bill Inmon 于 1990 年提出的一种用于数据分析和挖掘的系统。它的主要目标是通过分析和挖掘数据&#xff0c;为不同层级的决策提供支持&#xff0c;构成…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

聊聊 Pulsar:Producer 源码解析

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

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...