G. XOUR
题目链接:Problem - G - Codeforces
题目大意:给你一个n长的序列, 其中你可以将a[i] XOR a[j] 的值 严格小于4的数对进行交换。 你可以操作任何几次, 让最后的数列最小。如果在 x 和 y 不同的第一个位置, xi<yi ,那么数组 x 在词法上比数组 y 小。 具体题目见链接。
输入:
第一行包含一个整数 t ( 1≤t≤1e4 ) - 测试用例数。
每个测试用例的第一行包含一个整数 n (1≤n≤2⋅1e5 ) - 数组的长度。
每个测试用例的第二行包含 n 个整数 ai ( 0≤ai≤1e9 ) - 数组的元素。
保证所有测试用例中 n 的总和不超过 2⋅1e5
考察知识点: 并查集, 容器map的使用,位运算(a^b==c c^b==a)。
1.首先可以交换的条件可以看出, 我们可以将 可以交换的数字放在一起,有此功能的算法,不难想到并查集, 然后为了方便使用 并 可以方便取出数据, 采用map, 收集。
2.可以合并的条件:两数 XOR < 4 , 此处, 暴力枚举 0,1,2,3 XOR回取在map里查找是否出现了该数, 如果出现,将该数的下标与次数合并。 最后在到map里标记次数,记录下标。
3. 在并查集使用完过后, 又采用 map<int, multiset<int>> q; 收集每一个下标上的值, 方便在于最后的重新赋值。 利用了multiset的自动排序不去重。 q的键实质上就是每个联通块的根。
#include<bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;const int N = 2e5+9;
int tr[N];
int n;
void innt(){for(int i=0; i<n; i++) tr[i] = i;
}//并查集
int find(int x) {if(tr[x] != x) {tr[x] = find(tr[x]);}return tr[x];
}
void mger_(int a, int b){a = find(a);b = find(b);if(a==b)return;tr[b] = a;
}
map<int,int> mp;
map<int, multiset<int>> q;
void solve(){cin >> n;vector<int> a(n);for(int i=0; i<n; i++) {cin >> a[i];}innt();mp.clear();//初始化q.clear();for(int i=0; i<n; i++) {for(int k=0; k<4; k++) { //枚举0,1,2,3int u = a[i] ^ k;if(mp.count(u)) {mger_(i, mp[u]);}//有就连起来}mp[a[i]] = i;//标记} for(int i=0; i<n; i++) {q[find(i)].insert(a[i]); //分组到q}for(int i=0; i<n; i++) {int u = find(i);a[i] = *q[u].begin();q[u].erase(q[u].begin());//使用过后删除}for(int i=0; i<n; i++) {cout << a[i] << " ";}cout << "\n";
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while(t--) {solve();}
}
感谢收看与点赞, 欢迎大佬指正。
相关文章:
G. XOUR
题目链接:Problem - G - Codeforces 题目大意:给你一个n长的序列, 其中你可以将a[i] XOR a[j] 的值 严格小于4的数对进行交换。 你可以操作任何几次, 让最后的数列最小。如果在 x 和 y 不同的第一个位置, xi<yi &…...
有没有个性化的UML图例
绿萝小绿萝 (53****338) 2012-05-10 11:55:45 各位大虾,有没有个性化的UML图例 绿萝小绿萝 (53****338) 2012-05-10 11:56:03 例如部署图或时序图的图例 潘加宇 (35***47) 2012-05-10 12:24:31 "个性化"指的是? 你的意思使用你自己的图标&…...
【RAG】SKLearnVectorStore 避免使用gpt4all会connection err
gpt4all 列表中包含了多个开源的大模型,如 Qwen2.5、Llama 3、DeepSeek、Mistral 等,但 不包含 OpenAI 的 GPT-4o。GPT-4o 是 OpenAI 提供的闭源模型,目前只能通过 OpenAI API 或 ChatGPT 官方应用(网页版、移动端)访问,并不支持本地运行,也没有 GGUF 量化格式的模型文件…...
vue框架技术相关概述以及前端框架整合
vue框架技术概述及前端框架整合 1 node.js 介绍:什么是node.js Node.js就是运行在服务端的JavaScript。 Node.js是一个事件驱动I/O服务端JavaScript环境,基于Google的V8引擎。 作用 1 运行java需要安装JDK,而Node.js是JavaScript的运行环…...
Spring Boot + Facade Pattern : 通过统一接口简化多模块业务
文章目录 Pre概述在编程中,外观模式是如何工作的?外观设计模式 UML 类图外观类和子系统的关系优点案例外观模式在复杂业务中的应用实战运用1. 项目搭建与基础配置2. 构建子系统组件航班服务酒店服务旅游套餐服务 3. 创建外观类4. 在 Controller 中使用外…...
牛客周赛 Round 78
题目目录 A-时间表查询!解题思路参考代码 B-一起做很甜的梦!解题思路参考代码 C-翻之解题思路参考代码 D-乘之解题思路参考代码 E-在树上游玩解题思路参考代码 A-时间表查询! \hspace{15pt} 今天是2025年1月25日,今年的六场牛客寒…...
【机器学习】自定义数据集 ,使用朴素贝叶斯对其进行分类
一、贝叶斯原理 贝叶斯算法是基于贝叶斯公式的,其公式为: 其中叫做先验概率,叫做条件概率,叫做观察概率,叫做后验概率,也是我们求解的结果,通过比较后验概率的大小,将后验概率最大的…...
02.01 生产者消费者
请使用条件变量实现2生产者2消费者模型,注意1个生产者在生产的时候,另外一个生产者不能生产。 1>程序代码 #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include <sys/types.h>…...
mac 手工安装OpenSSL 3.4.0
如果你希望继续安装 openssl-3.4.0 而不是降级到 3.1.1,可以尝试以下解决方案。根据你提供的错误信息,问题可能出在测试阶段(make test),我们可以尝试跳过测试或修复测试失败的原因。 --- ### **解决方案:…...
kamailio-ACC_JSON模块详解【后端语言go】
要确认 ACC_JSON 模块是否已经成功将计费信息推送到消息队列(MQueue),以及如何从队列中取值,可以按照以下步骤进行操作: 1. 确认 ACC_JSON 已推送到队列 1.1 配置 ACC_JSON 确保 ACC_JSON 模块已正确配置并启用。以下…...
ArkTS语言介绍
文章目录 一、基本知识声明类型运算符语句函数函数声明可选参数Rest参数返回类型函数的作用域函数调用函数类型箭头函数(又名Lambda函数)闭包函数重载类字段方法构造函数可见性修饰符对象字面量抽象类接口接口属性接口继承抽象类和接口泛型类型和函数泛型类和接口泛型约束泛型…...
海外问卷调查之渠道查,企业经营的指南针
海外问卷调查,是企业调研最常用到的方法,有目的、有计划、有系统地收集研究对象的现实状况或历史状况的一种有效手段,是指导企业经营的有效手段。 海外问卷调查充分运用历史法、观察法等方法,同时使用谈话、问卷、个案研究、测试…...
spring和Mybatis的逆向工程
在现代企业级开发中,使用Spring和MyBatis进行快速、高效的数据库操作是非常常见的。本文将深入探讨如何使用Spring和MyBatis进行逆向工程,帮助开发者自动生成数据库相关的代码,提高开发效率和代码质量。 一、什么是逆向工程 逆向工程是指从…...
【Android】问deepseek存储访问
这些天deepseek爆火,我们来问问android问题看看,如果问android中的应用怎么访问外部存储,回答的很清楚,但是如果问的深入一些,比如Android中是怎么控制让应用不能读取其他应用的外部存储文件的,回答的比较抽…...
Android记事本App设计开发项目实战教程2025最新版Android Studio
平时上课录了个视频,从新建工程到打包Apk,从头做到尾,没有遗漏任何实现细节,欢迎学过Android基础的同学参加,如果你做过其他终端软件开发,也可以学习,快速上手Android基础开发。 Android记事本课…...
python学习——函数的返回值
在 Python 中,函数的返回值决定了调用该函数后得到的结果。默认情况下,如果函数没有使用 return 语句或没有明确返回一个值,函数将返回 None。为了实现更复杂的逻辑,可以通过 return 语句返回多个值、错误信息或其他数据类型。 返…...
【竞技宝】裂变天地S1:BB0-2PARI淘汰出局
北京时间2月1日,DOTA2裂变天地S1继续进行,昨日共进行三场比赛,第三场比赛迎来败者组第二轮PARI对阵BB。以下是本场比赛的详细战报。 第一局: 首局比赛,BB在天辉方,PARI在夜魇方。阵容方面,BB点出了圣堂、卡尔、玛尔斯、奶绿、亚巴顿,PARI则是拿到小娜迦、凤凰、大圣、玛西、萨…...
数据分析系列--⑨RapidMiner训练集、测试集、验证集划分
一、数据集获取 二、划分数据集 1.导入和加载数据 2.数据集划分 2.1 划分说明 2.2 方法一 2.3 方法二 一、数据集获取 点击下载数据集 此数据集包含538312条数据. 二、划分数据集 1.导入和加载数据 2.数据集划分 2.1 划分说明 2.2 方法一 使用Filter Example Range算子. …...
实践Rust:编写一个猜数字游戏
如果你正在学习Rust,并且想通过一个有趣的小项目来巩固所学知识,那么“猜数字游戏”是一个绝佳的选择!这个游戏的逻辑非常简单:程序会随机生成一个数字,玩家需要猜测这个数字是多少,程序会告诉玩家猜大了还…...
JavaFX - 3D 形状
在前面的章节中,我们已经了解了如何在 JavaFX 应用程序中的 XY 平面上绘制 2D 形状。除了这些 2D 形状之外,我们还可以使用 JavaFX 绘制其他几个 3D 形状。 通常,3D 形状是可以在 XYZ 平面上绘制的几何图形。它们由两个或多个维度定义&#…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。
2024 年,高端封装市场规模为 80 亿美元,预计到 2030 年将超过 280 亿美元,2024-2030 年复合年增长率为 23%。 细分到各个终端市场,最大的高端性能封装市场是“电信和基础设施”,2024 年该市场创造了超过 67% 的收入。…...
