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

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

题目链接&#xff1a;Problem - G - Codeforces 题目大意&#xff1a;给你一个n长的序列&#xff0c; 其中你可以将a[i] XOR a[j] 的值 严格小于4的数对进行交换。 你可以操作任何几次&#xff0c; 让最后的数列最小。如果在 x 和 y 不同的第一个位置&#xff0c; xi<yi &…...

有没有个性化的UML图例

绿萝小绿萝 (53****338) 2012-05-10 11:55:45 各位大虾&#xff0c;有没有个性化的UML图例 绿萝小绿萝 (53****338) 2012-05-10 11:56:03 例如部署图或时序图的图例 潘加宇 (35***47) 2012-05-10 12:24:31 "个性化"指的是&#xff1f; 你的意思使用你自己的图标&…...

【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 介绍&#xff1a;什么是node.js Node.js就是运行在服务端的JavaScript。 Node.js是一个事件驱动I/O服务端JavaScript环境&#xff0c;基于Google的V8引擎。 作用 1 运行java需要安装JDK&#xff0c;而Node.js是JavaScript的运行环…...

Spring Boot + Facade Pattern : 通过统一接口简化多模块业务

文章目录 Pre概述在编程中&#xff0c;外观模式是如何工作的&#xff1f;外观设计模式 UML 类图外观类和子系统的关系优点案例外观模式在复杂业务中的应用实战运用1. 项目搭建与基础配置2. 构建子系统组件航班服务酒店服务旅游套餐服务 3. 创建外观类4. 在 Controller 中使用外…...

牛客周赛 Round 78

题目目录 A-时间表查询&#xff01;解题思路参考代码 B-一起做很甜的梦&#xff01;解题思路参考代码 C-翻之解题思路参考代码 D-乘之解题思路参考代码 E-在树上游玩解题思路参考代码 A-时间表查询&#xff01; \hspace{15pt} 今天是2025年1月25日&#xff0c;今年的六场牛客寒…...

【机器学习】自定义数据集 ,使用朴素贝叶斯对其进行分类

一、贝叶斯原理 贝叶斯算法是基于贝叶斯公式的&#xff0c;其公式为&#xff1a; 其中叫做先验概率&#xff0c;叫做条件概率&#xff0c;叫做观察概率&#xff0c;叫做后验概率&#xff0c;也是我们求解的结果&#xff0c;通过比较后验概率的大小&#xff0c;将后验概率最大的…...

02.01 生产者消费者

请使用条件变量实现2生产者2消费者模型&#xff0c;注意1个生产者在生产的时候&#xff0c;另外一个生产者不能生产。 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&#xff0c;可以尝试以下解决方案。根据你提供的错误信息&#xff0c;问题可能出在测试阶段&#xff08;make test&#xff09;&#xff0c;我们可以尝试跳过测试或修复测试失败的原因。 --- ### **解决方案&#xff1a…...

kamailio-ACC_JSON模块详解【后端语言go】

要确认 ACC_JSON 模块是否已经成功将计费信息推送到消息队列&#xff08;MQueue&#xff09;&#xff0c;以及如何从队列中取值&#xff0c;可以按照以下步骤进行操作&#xff1a; 1. 确认 ACC_JSON 已推送到队列 1.1 配置 ACC_JSON 确保 ACC_JSON 模块已正确配置并启用。以下…...

ArkTS语言介绍

文章目录 一、基本知识声明类型运算符语句函数函数声明可选参数Rest参数返回类型函数的作用域函数调用函数类型箭头函数(又名Lambda函数)闭包函数重载类字段方法构造函数可见性修饰符对象字面量抽象类接口接口属性接口继承抽象类和接口泛型类型和函数泛型类和接口泛型约束泛型…...

海外问卷调查之渠道查,企业经营的指南针

海外问卷调查&#xff0c;是企业调研最常用到的方法&#xff0c;有目的、有计划、有系统地收集研究对象的现实状况或历史状况的一种有效手段&#xff0c;是指导企业经营的有效手段。 海外问卷调查充分运用历史法、观察法等方法&#xff0c;同时使用谈话、问卷、个案研究、测试…...

spring和Mybatis的逆向工程

在现代企业级开发中&#xff0c;使用Spring和MyBatis进行快速、高效的数据库操作是非常常见的。本文将深入探讨如何使用Spring和MyBatis进行逆向工程&#xff0c;帮助开发者自动生成数据库相关的代码&#xff0c;提高开发效率和代码质量。 一、什么是逆向工程 逆向工程是指从…...

【Android】问deepseek存储访问

这些天deepseek爆火&#xff0c;我们来问问android问题看看&#xff0c;如果问android中的应用怎么访问外部存储&#xff0c;回答的很清楚&#xff0c;但是如果问的深入一些&#xff0c;比如Android中是怎么控制让应用不能读取其他应用的外部存储文件的&#xff0c;回答的比较抽…...

Android记事本App设计开发项目实战教程2025最新版Android Studio

平时上课录了个视频&#xff0c;从新建工程到打包Apk&#xff0c;从头做到尾&#xff0c;没有遗漏任何实现细节&#xff0c;欢迎学过Android基础的同学参加&#xff0c;如果你做过其他终端软件开发&#xff0c;也可以学习&#xff0c;快速上手Android基础开发。 Android记事本课…...

python学习——函数的返回值

在 Python 中&#xff0c;函数的返回值决定了调用该函数后得到的结果。默认情况下&#xff0c;如果函数没有使用 return 语句或没有明确返回一个值&#xff0c;函数将返回 None。为了实现更复杂的逻辑&#xff0c;可以通过 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&#xff0c;并且想通过一个有趣的小项目来巩固所学知识&#xff0c;那么“猜数字游戏”是一个绝佳的选择&#xff01;这个游戏的逻辑非常简单&#xff1a;程序会随机生成一个数字&#xff0c;玩家需要猜测这个数字是多少&#xff0c;程序会告诉玩家猜大了还…...

JavaFX - 3D 形状

在前面的章节中&#xff0c;我们已经了解了如何在 JavaFX 应用程序中的 XY 平面上绘制 2D 形状。除了这些 2D 形状之外&#xff0c;我们还可以使用 JavaFX 绘制其他几个 3D 形状。 通常&#xff0c;3D 形状是可以在 XYZ 平面上绘制的几何图形。它们由两个或多个维度定义&#…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...