143. 最大异或对
2022/3/4 23:45:18
本文主要是介绍143. 最大异或对,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
143. 最大异或对
在给定的 \(N\) 个整数 \(A_1,A_2……A_N\) 中选出两个进行 \(xor\)(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 \(N\)。
第二行输入 \(N\) 个整数 \(A_1~A_N\)。
输出格式
输出一个整数表示答案。
数据范围
\(1≤N≤10^5,\)
\(0≤A_i<2^{31}\)
输入样例:
3 1 2 3
输出样例:
3
解题思路
字典树
按位考虑,对数从高位开始建立一棵01tire,从前往后遍历,对一个数的一位尽量走位相反的方向,这样走到最后可以找到前面跟该数异或值最大的数
- 时间复杂度:\(O(30\times n)\)
代码
// Problem: 最大异或对 // Contest: AcWing // URL: https://www.acwing.com/problem/content/description/145/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } int n,tr[2][3000005],idx=1; void insert(int x) { int p=1; for(int i=30;~i;i--) { int t=x>>i&1; if(tr[t][p]==0)tr[t][p]=++idx; p=tr[t][p]; } } int find(int x) { int res=0,p=1; for(int i=30;~i;i--) { int t=x>>i&1; if(tr[t^1][p])res|=1<<i,p=tr[t^1][p]; else if(!tr[t][p])break; else p=tr[t][p]; } return res; } int main() { int res=0; cin>>n; while(n--) { int x; cin>>x; res=max(res,find(x)); insert(x); } cout<<res; return 0; }
这篇关于143. 最大异或对的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署