当前位置: 首页 > 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;构成…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...