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

集合问题(并查集)

本题链接:登录—专业IT笔试面试备考平台_牛客网

题目:

样例1:

输入
4 5 9
2 3 4 5

输出
YES
0 0 1 1

 样例2:

输入
3 3 4
1 2 4

输出
NO

思路:

        这道题关键点在于。

        当集合中有一个元素均存在于集合 A 和集合 B 的时候是 NO。

        并且 P_{i} 的范围是 1 ~ 1e9 所以,当 P_{i} >= max(a,b) 的时候也是 NO。

        我们同时可以指定一个 元素范围外的 一个元素作为 根元素集合 A,B

        其次,我们可以将 下标 作为对应的每一个元素,最后进行合并求结果即可。

代码详解如下:

#include <iostream>
#include <vector>
#include <unordered_map>
#define umap unordered_map
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;umap<int,int>pos;	// 存储元素对应的下标// 存储元素集合,至于为什么也用 umap ,由于 Pi 的数据范围上限是 1e9
// 我们要将数组无法开辟这么大,所以我们只能弄个映射 来存储对应的 A,B 根元素
umap<int,int>father;	// 并查集查找函数
inline int Finds(int x)
{int t = x;	// 记录其实查找结点while(x != father[x]) x = father[x];	// 开始查找father[t] = x;	// 路径压缩查找return x;	// 返回结果
}// 并查集合并操作
inline void Union(int a,int b)
{a = Finds(a),b = Finds(b);	// 查找对应根节点father[a] = b;	// 合并对应根节点
}inline void solve()
{int n,a,b;cin >> n >> a >> b;int maxs = max(a,b);	// 获取对应 a b 最大值int A = maxs + 1;	// 根据对应的最大值,赋值一个元素范围外的元素作为 集合 A 的根节点int B = maxs + 2;	// 根据对应的最大值,赋值一个元素范围外的元素并且不同于集合A的根元素的元素作为 集合 B 的根节点father[A] = A,father[B] = B;	// 集合根节点初始化vector<int>v(n + 2,0);	// 存储对应元素for(int i = 1;i <= n;++i){cin >> v[i];if(v[i] >= maxs)	// 如果存在 元素 大于 a 和 b ,那么放不了 任意集合,无解输出 NO{cout << "NO" << endl;return ;}pos[v[i]] = i;	// 映射对应的下标father[i] = i;	// 对应下标 根节点初始化}for(int i = 1;i <= n;++i){// 如果对应的元素存在的话,我们将其元素的下标与当前的下标进行操作合并对应的集合if(pos[b - v[i]]) Union(i,pos[b - v[i]]);	// 另一元素存在 集合 b 那么我们合并对应下标 else Union(A,i);	//如果不符合那么合并另一个集合if(pos[a - v[i]]) Union(i,pos[a - v[i]]);	// 另一元素存在 集合 a 那么我们合并对应下标 else Union(B,i);	//如果不符合那么合并另一个集合}A = Finds(A),B = Finds(B);	// 根据对应的 结合 根节点元素查找;if(A == B) cout << "NO" << endl;	// 如果最终集合 A 和 集合 B 的根节点也给合并了,说明无解 NOelse{cout << "YES" << endl;for(int i = 1;i <= n;++i){
// 			cout << bool(Finds(i) == B) << ' ';		// 这样输出是错误的,有可能这里没考虑一个情况,就是 A == B 的时候,也有可能返回值的原因if(Finds(i) == A) cout << "0 ";else cout << "1 ";}cout << endl;}
}signed main()
{IOS;int ___t = 1;while(___t--) solve();	return 0;
}

最后提交:

相关文章:

集合问题(并查集)

本题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例1&#xff1a; 输入 4 5 9 2 3 4 5 输出 YES 0 0 1 1 样例2&#xff1a; 输入 3 3 4 1 2 4 输出 NO 思路&#xff1a; 这道题关键点在于。 当集合中有一个元素均存在于集合 A 和集合 B 的时…...

Ubuntu文件系统结构

Ubuntu文件系统结构 介绍 Ubuntu是一种备受欢迎的Linux发行版&#xff0c;其文件系统结构以及组织方式是每个使用者和系统管理员都应该了解的重要主题。本篇博客将带您深入探索Ubuntu文件系统的结构&#xff0c;以便更好地理解Linux操作系统的工作原理。 1. 根目录&#xff…...

vue element 组件 form深层 :prop 验证失效问题解决

此图源自官网 借鉴。 当我们简单单层验证的时候发现是没有问题的&#xff0c;但是有的时候可能会涉及到深层prop&#xff0c;发现在去绑定的时候就不生效了。例如我们在form单里面循环验证&#xff0c;在去循环数据验证。 就如下图的写法了 :prop"pumplist. i .device…...

前端开发:入门(一)

当我们开始学习前端开发时&#xff0c;首先接触到的是HTML&#xff08;超文本标记语言&#xff09;。HTML是构建网页结构的基础。 1. HTML&#xff08;超文本标记语言&#xff09; 介绍和基础语法 HTML&#xff0c;即超文本标记语言&#xff0c;是一种用于创建网页结构的标记…...

简单实验 java spring cloud 自定义负载均衡

1.概要 1.1 说明 这个是在前一个测试上的修改&#xff0c;所以这里只体现修改的内容。前一个测试的地址&#xff1a;检查实验 spring cloud nacos nacos-server-2.3.0-CSDN博客 1.2 记忆要点 1.2.1 引入对象 Autowired DiscoveryClient discoveryClient; 1.2.2 获取服务实…...

简单说说redis分布式锁

什么是分布式锁 分布式锁&#xff08;多服务共享锁&#xff09;在分布式的部署环境下&#xff0c;通过锁机制来让多客户端互斥的对共享资源进行访问/操作。 为什么需要分布式锁 在单体应用服务里&#xff0c;不同的客户端操作同一个资源&#xff0c;我们可以通过操作系统提供…...

什么是 Java 中的 IO 和 NIO?它们之间有什么区别?什么是 Java 中的内存管理和垃圾回收?常见的垃圾回收算法有哪些?

什么是 Java 中的 IO 和 NIO&#xff1f;它们之间有什么区别&#xff1f; 在 Java 中&#xff0c;IO&#xff08;Input/Output&#xff09;和NIO&#xff08;New IO&#xff09;都是用于处理输入输出操作的API。它们之间有以下区别&#xff1a; IO&#xff08;传统IO&#xff…...

【图论】基环树

基环树其实并不是树&#xff0c;是指有n个点n条边的图&#xff0c;我们知道n个点n-1条边的连通图是树&#xff0c;再加一条边就会形成一个环&#xff0c;所以基环树中一定有一个环&#xff0c;长下面这样&#xff1a; 由基环树可以引申出基环内向树和基环外向树 基环内向树如…...

如何快速捕获和验证用户软件需求,实现快速迭代

在软件开发过程中&#xff0c;快速捕获和验证用户需求&#xff0c;以及迅速迭代功能&#xff0c;是保持项目敏捷性和用户满意度的关键。下面将介绍一些建议&#xff0c;帮助你在软件开发过程中更有效地满足用户需求。 1. 深入沟通与用户互动 要捕获用户需求&#xff0c;必须与…...

爱上算法:每日算法(24-2月4号)

&#x1f31f;坚持每日刷算法&#xff0c;&#x1f603;将其变为习惯&#x1f91b;让我们一起坚持吧&#x1f4aa; 文章目录 [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/)思路CodeJavaC 复杂度 [225. 用队列实现栈](https://leetcode.cn/…...

【Node系列】创建第一个服务器应用

文章目录 一、node介绍二、node创建应用三、node创建应用步骤四、相关链接 一、node介绍 Node.js是一个基于Chrome V8引擎的JavaScript运行环境&#xff0c;可以用于构建高性能的网络应用程序。它采用事件驱动、非阻塞I/O模型&#xff0c;使得程序可以以高效地方式处理并发请求…...

Linux命令基础学习 (2月4日打卡

1. ls - 列出目录内容 命令格式&#xff1a;ls [选项] [文件/目录] 常用选项&#xff1a; -l&#xff1a;以详细列表格式显示-a&#xff1a;显示所有文件&#xff0c;包括以.开头的隐藏文件 2. mkdir - 创建新目录 命令格式&#xff1a;mkdir [选项] 目录名 常用选项&…...

Python 基础知识概览

Python是一种简洁、易学、强大的编程语言&#xff0c;广泛应用于各种领域&#xff0c;包括Web开发、数据分析、人工智能等。本文将介绍一些Python的基础知识&#xff0c;帮助初学者建立对这门语言的基本了解。 1. Python 的简介 Python是一种高级、面向对象、解释型的编程语言…...

Adobe Camera Raw for Mac v16.1.0中文激活版

Adobe Camera Raw for Mac是一款强大的RAW格式图像编辑工具&#xff0c;它能够处理和编辑来自各种数码相机的原始图像。以下是关于Adobe Camera Raw for Mac的一些主要特点和功能&#xff1a; 软件下载&#xff1a;Adobe Camera Raw for Mac v16.1.0中文激活版 RAW格式支持&…...

zabbix自定义监控项

zabbix自定义监控项 1.安装zabbix_get软件 [rootchang local]# yum install zabbix-get2.编辑自定义监控项文件 [rootchang ~]# vim /etc/zabbix/zabbix_agentd.d/cpu.conf UserParametercheck_cpu,top -bn 1 -i -c |grep id |cut -d , -f 4 | tr -d id #UserParameter表示…...

使用Pycharm在本地调用chatgpt的接口

目录 1.安装环境 2.建立多轮对话的完整代码&#xff08;根据自己使用的不同代理需要修改端口&#xff08;port&#xff09;&#xff09; 3.修改代码在自己的Pycharm上访问chagpt的api并实现多轮对话&#xff0c;如果不修改是无法成功运行的。需要确定秘钥和端口以保证正常访…...

HarmonyOS远程真机调试方法

生成密钥库文件 打开DevEco Studio&#xff0c;点击菜单栏上的build&#xff0c; 填一些信息点击&#xff0c;没有key的话点击new一个新的key。 生成profile文件 AppGallery Connect (huawei.com) 进入该链接网站&#xff0c;点击用户与访问将刚生成的csr证书提交上去其中需…...

基于SpringBoot的后端导出Excel文件

后端导出Excel&#xff0c;前端下载。 系列文章指路&#x1f449; 系列文章-基于SpringBoot3创建项目并配置常用的工具和一些常用的类 文章目录 后端导出Excel引入依赖写入响应 前端下载后端导出失败和成功返回的内容类型不同&#xff0c;因此需要分别判断。 工具类ServletUti…...

2 月 5 日算法练习- 动态规划

DP&#xff08;动态规划&#xff09;全称Dynamic Programming&#xff0c;是运筹学的一个分支&#xff0c;是一种将复杂问题分解成很多重叠的子问题、并通过子问题的解得到整个问题的解的算法。 在动态规划中有一些概念&#xff1a; n<1e3 [][] &#xff0c;n<100 [][][…...

SpringBoot整合EasyCaptcha图形验证码

简介 EasyCaptcha&#xff1a;https://github.com/ele-admin/EasyCaptcha Java图形验证码&#xff0c;支持gif、中文、算术等类型&#xff0c;可用于Java Web、JavaSE等项目。 添加依赖 <dependency><groupId>com.github.whvcse</groupId><artifactId…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...

虚幻基础:角色旋转

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 移动组件使用控制器所需旋转&#xff1a;组件 使用 控制器旋转将旋转朝向运动&#xff1a;组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转&#xff1a;必须移动才能旋转&#xff0c;不移动不旋转控制器…...