P8686 [蓝桥杯 2019 省 A] 修改数组--并查集 or Set--lower_bound()的解法!!!
P8686 [蓝桥杯 2019 省 A] 修改数组--并查集
- 题目
- 并查集解析
- 代码【并查集解】
- Set 解法解析
- lower_bound
- 代码
题目

并查集解析
首先先让所有的f(i)=i,即每个人最开始的祖先都是自己,然后就每一次都让轮到那个数的父亲+1(用过后的标记),第二次出现的时候就直接用父亲替换掉
并查集的作用:并查集用于快速查找元素的根节点,并进行路径压缩以提高效率。
并查集适用场景
1.快速合并与查询:需要频繁合并集合(如标记某个数已被占用)和查询根节点(找下一个可用位置)。
2.路径压缩优化:通过压缩查找路径,使得后续查询接近常数时间复杂度。
3.动态维护连续区间:每个数字的父节点指向下一个可用位置,天然维护了一个动态递增的区间。
代码【并查集解】
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits> // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n, f[100010];int find(int x) {if (f[x] == x)return x;return f[x] = find(f[x]);
}int main() {cin >> n;for (int i = 1; i <= 1e5; i++)f[i] = i;for (int i = 0; i < n; i++) {int x;cin >> x;x = find(x);cout << x << ' ';f[x] += 1;//为下一次重复做准备}return 0;
}
Set 解法解析
这道题我们可以利用set 的有序性和高效查找特性,直接找到每个元素的最小可用值。
代码思路:
先将1~1e6的值依次存入set中,然后利用lower_bound()找到第一个大于等于x的值,使用过后再利用erase()删除
【这个代码的思路完全符合我们脑中所想】
lower_bound
是一个用于在有序序列中【有序序列set】查找特定元素的函数。它返回指向第一个不小于给定值的元素的迭代器。结合set(有序集合),可以高效解决需要动态维护有序数据并快速查找的问题。
lower_bound 的核心功能
1.作用:在有序序列中找到第一个不小于目标值的位置。
2.返回值:
i 如果存在符合条件的元素,返回指向该元素的迭代器。
ii如果所有元素都小于目标值,返回容器的end()迭代器。
在 set 中使用 lower_bound
set 的特性:
1.元素唯一且按升序自动排序。
2.插入、删除和查找操作的时间复杂度为 O(log N)。
调用方式:
auto it = s.lower_bound(x); // it 是迭代器,指向第一个 >=x 的元素
cout << *it; // *it 是该元素的实际值
s.erase(it); // 直接传递迭代器删除元素(不需要 *)
lower_bound 下界 & upper_bound上界

为什么不用 vector 替代 set?
vector 的插入、删除和查找效率较低,适合静态数据。
vector 的查找必须遍历或使用 find 算法,效率低。
代码
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits> // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n;
set<int> s;int main() {cin >> n;for (int i = 1; i <= 1e6; i++)s.insert(i);for (int i = 0; i < n; i++) {int x;cin >> x;auto a = s.lower_bound(x); //lower_bound返回第一个大于等于x的值,在有序集合set中能完美解决该问题cout << *a << ' ';s.erase(a);}return 0;
}
相关文章:
P8686 [蓝桥杯 2019 省 A] 修改数组--并查集 or Set--lower_bound()的解法!!!
P8686 [蓝桥杯 2019 省 A] 修改数组--并查集 题目 并查集解析代码【并查集解】 Set 解法解析lower_bound代码 题目 并查集解析 首先先让所有的f(i)i,即每个人最开始的祖先都是自己,然后就每一次都让轮到那个数的父亲1(…...
HTML 编辑器推荐与 VS Code 使用教程
在进行 HTML 编程时,选择一款合适的 HTML 编辑器能极大地提高开发效率。以下为大家推荐几款常用且功能强大的 HTML 编辑器,同时详细介绍如何使用 VS Code 创建和预览 HTML 文件。 一、HTML 编辑器推荐 VS Code:由微软开发,是一款…...
MyBatis增删改查:静态与动态SQL语句拼接及SQL注入问题解析
MyBatis 是一个优秀的持久层框架,它支持定制化 SQL、存储过程以及高级映射。MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集的工作。本文将深入探讨 MyBatis 中的增删改查操作,重点讲解静态与动态 SQL 语句的拼接,并分析 S…...
在运维工作中,Lvs、nginx、haproxy工作原理分别是什么?
在运维工作中,LVS、NGINX和HAProxy都是常用的负载均衡和反向代理工具,它们在高可用性和负载均衡场景中发挥重要作用。以下是其原理和应用场景详解: LVS(Linux Virtual Server) 工作原理 LVS是基于Linux内核的负载均…...
linux学习(五)(服务器审查,正常运行时间负载,身份验证日志,正在运行的服务,评估可用内存)
服务器审查 在 Linux 中审查服务器的过程包括评估服务器的性能、安全性和配置,以确定需要改进的领域或任何潜在问题。审查的范围可以包括检查安全增强功能、检查日志文件、审查用户帐户、分析服务器的网络配置以及检查其软件版本。 Linux 以其稳定性和安全性而闻名…...
Java在小米SU7 Ultra汽车中的技术赋能
目录 一、智能驾驶“大脑”与实时数据 场景一:海量数据的分布式计算 场景二:实时决策的毫秒级响应 场景三:弹性扩展与容错机制 技术隐喻: 二、车载信息系统(IVI)的交互 场景一:Android Automo…...
开发环境搭建-02.后端环境搭建-熟悉项目结构
一.后端环境搭建...
js实现pdf文件路径预览和下载
预览 直接浏览器窗口打开默认就是预览 window.open(文件路径)下载 function downloadPDF(url, filename) {fetch(url).then(response > response.blob()).then(blob > {const link document.createElement(a);link.href URL.createObjectURL(blob);link.download fi…...
【RAG】基于向量检索的 RAG (BGE示例)
RAG机器人 结构体 文本向量化: 使用 BGE 模型将文档和查询编码为向量。 (BGE 是专为检索任务优化的开源 Embedding 模型,除了本文API调用,也可以通过Hugging Face 本地部署BGE 开源模型) 向量检索: 从数据库中找到与查询相关的文…...
Vue源码解析之mustache模板引擎
个人简介 👀个人主页: 前端杂货铺 🙋♂️学习方向: 主攻前端方向,正逐渐往全干发展 📃个人状态: 研发工程师,现效力于中国工业软件事业 🚀人生格言: 积跬步…...
python: DDD using postgeSQL and SQL Server
postgreSQL 注意: # psycopg 2 驱动的连接字符串 #engine create_engine(postgresql://post:geovindulocalhost:5433/TechnologyGame) #Session sessionmaker(bindengine)# 使用 psycopg3 驱动的连接字符串 #engine create_engine(postgresqlpsycopg://user:g…...
Python实例:PyMuPDF实现PDF翻译,英文翻译为中文,并按段落创建中文PDF
基于PyMuPDF与百度翻译的PDF翻译处理系统开发:中文乱码解决方案与自动化排版实践 一 、功能预览:将英文翻译为中文后创建的PDF 二、完整代码 from reportlab.lib.pagesizes import letter from reportlab.lib.styles import getSampleStyleSheet, ParagraphStyle...
IntelliJ IDEA 2021版创建springboot项目的五种方式
第一种方式,通过https://start.spring.io作为spring Initializr的url来创建项目。 第二种方式,通过https://start.spring.io官网来直接创建springboot项目压缩包,然后导入至我们的idea中。 点击generate后,即可生成压缩包…...
c#面试题整理6
1.String类能否被继承,为什么 可以看到String类的修饰符是sealed,即是密封类,故不可被继承 2.一个对象的方法是否只能由一个线程访问 不是,但是可通过同步机制,确保同一个时间只有一个线程访问 3.计算2*8ÿ…...
跟着 Lua 5.1 官方参考文档学习 Lua (12)
文章目录 5.7 – Input and Output Facilities补充内容io.input ([file])io.read ()io.write ()io.output ([file])io.lines ([filename])io.flush ()io.close ([file])io.open (filename [, mode])io.popen (prog [, mode])io.tmpfile ()io.type (ob)file:read ()file:lines (…...
大语言模型中的归一化技术:LayerNorm与RMSNorm的深入研究
在LLama等大规模Transformer架构的语言模型中,归一化模块是构建网络稳定性的关键组件。本文将系统分析归一化技术的必要性,并详细阐述为何原始Transformer架构中的LayerNorm在LLama模型中被RMSNorm所替代的技术原理。 归一化技术的基础原理 归一化的核…...
nodejs使用WebSocket实现聊天效果
在nodejs中使用WebSocket实现聊天效果(简易实现) 安装 npm i ws 实现 创建 server.js /*** 创建一个 WebSocket 服务器,监听指定端口,并处理客户端连接和消息。** param {Object} WebSocket - 引入的 WebSocket 模块,…...
【仿muduo库one thread one loop式并发服务器实现】
文章目录 一、项目介绍1-1、项目总体简介1-2、项目开发环境1-3、项目核心技术1-4、项目开发流程1-5、项目如何使用 二、框架设计2-1、功能模块划分2-1-1、SERVER模块2-1-2、协议模块 2-2、项目蓝图2-2-1、整体图2-2-2、模块关系图2-2-2-1、Connection 模块关系图2-2-2-2、Accep…...
10.2 继承与多态
文章目录 继承多态 继承 继承的作用是代码复用。派生类自动获得基类的除私有成员外的一切。基类描述一般特性,派生类提供更丰富的属性和行为。在构造派生类时,其基类构造函数先被调用,然后是派生类构造函数。在析构时顺序刚好相反。 // 基类…...
Go红队开发—格式导出
文章目录 输出功能CSV输出CSV 转 结构体结构体 转 CSV端口扫描结果使用CSV格式导出 HTML输出Sqlite输出nmap扫描 JSONmap转json结构体转jsonjson写入文件json编解码json转结构体json转mapjson转string练习:nmap扫描结果导出json格式 输出功能 在我们使用安全工具的…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
