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

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

对WWDC 2025 Keynote 内容的预测

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

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...