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

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...