题目链接：LOJ10050 The XOR Largest Pair
题意：给定 n n n 个非负整数，任取两个数，使得这两个数的异或结果最大，求这个最大值
肯定不是朴素枚举啊qwq
直接用Trie存每个数的二进制就可以了（注：把二进制看作字符串）
根据异或的定义，对于每个 a j a_j aj ，我们从最高位开始，尽可能取与 a i a_i ai 这一位相反的那一条路，一定可以得到最大值
至于最高位，我们只要不够的补 0 0 0 即可
因为它题目中说了每个数最大不大于 2 31 − 1 2^{31}-1 231−1 ，那么我们直接保存为30位二进制即可
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e5+5)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>inline void read(T &k)
{
char ch=getchar();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){
putchar('-');k=-k;}
if(k>9)write(k/10);
putchar(k%10+'0');
}
int n,ans=0;
int a[MAXN];
struct Trie
{
int trie[MAXN*32][3],tot=1; // trie的大小要注意
void insert(int x)
{
int p=0;
for(int i=31; i>=0; --i) // 其实只要30就可以了
{
int k=(x>>i)&1;
if(!trie[p][k])trie[p][k]=++tot;
p=trie[p][k];
}
}
int qry(int x)
{
int ans=0,p=0;
for(int i=31; i>=0; --i)
{
int k=(x>>i)&1;
if(trie[p][k^1])p=trie[p][k^1],ans|=(1<<i); // 尽可能选择这一位相反的
else p=trie[p][k];
}
return ans;
}
}t[1]; // 这个[1]并没有什么用 qwq
signed main()
{
read(n);
for(int i=1; i<=n; i++)
{
read(a[i]);
t[0].insert(a[i]);
ans=max(ans,t[0].qry(a[i]));
}
write(ans);putchar('\n');
return 0;
}
转载请说明出处
文章浏览阅读1.1k次，点赞8次，收藏15次。完整PPT请于 相关滤波目标跟踪算法以及评价 下载1.背景VOT2018最新结果：2.OTB评价指标3.VOT评价指标4.基于相关滤波的目标跟踪算法完整PPT请于相关滤波目标跟踪算法以及评价下载..._vot2019 相关滤波
文章浏览阅读1.2k次，点赞22次，收藏13次。openEuler 22.03 LTS SP2安装部署+配置_openeuler配置
文章浏览阅读3.2k次，点赞2次，收藏20次。嵌入式--ADC实验原理及相关库函数功能_嵌入式adc实验
文章浏览阅读2.5k次。Can't open a connection to site 'SYB_BACKUP'. See the error log file in the ASE boot directory. Msg 7205_can't open a connection to site 'syb_backup'. see the error log file in the
文章浏览阅读2.6k次。下面说下yum安装tomcat1. 安装在linux下部署java开发的web应用，一般采用Tomact+jre环境（可不需要apache），在RHEL和CentOS下，可以采用yum在线自动安装方式安装，具体操作如下：可以先查看tomcat在服务器上面的版本：yum search tomcat 可以看到需要安装的tomcat版本号为tomcat6安装命令：yum install tomcat6（ 执行以上命令系统会自动安装tomcat和所关联的jdk）2. 安装位置具体说明结束安装系统_yum tomcat位置
文章浏览阅读708次。硬件配置规模：Sca是一个单独的hadoop集群（24个节点，每个节点的配置：412core CPU,101T硬盘，64G/128G内存）Tas有一个单独的hadoop集群（部署了hive）（35节点）预处理ftp采集集群（6节点，上面部署了采集程序及zookeeper服务）Storm集群(单独)（手机位置实时分析&详单输出解析入hbase库）（10节点）kafka&zoo..._流量类的项目是什么
文章浏览阅读1k次。磁盘的使用详情，及磁盘的总容量、剩余容量和剩余可用容量。代码如下#include <windows.h>#include <QVector>struct DriveInfo{ QString sDriName; quint64 uiTotal; quint64 uiFree; quint64 uiFree2Caller;..._qt 获取磁盘占用时间
文章浏览阅读1.1k次。这边仅仅是从查询语句的角度进行分析，实际上缓存服务变慢的可能性很多，不仅仅是慢查询怎么分析（Slow Log、Explain命令）。还应该全面的分析原因，并给出处理方案，如 分析SQL脚本合理性、建立索引或优化索引、读写分离、垂直+水平分区）、多读少写/冷数据 做缓存、优化数据库的锁竞争、数据库配置调优、硬件资源升级 等等，后面几篇我们慢慢说。_mysql slowlog分析
文章浏览阅读601次，点赞12次，收藏8次。使用QChart模块前要声明宏 QT_CHARTS_USE_NAMESPACE 不然会报错。在.ui文件中选择容器，这里我们选择Widget，然后点击提升为，添加QChartView。所以我们学习用QChart和QTimer来完成曲线图的绘制。上位机页面需要根据用户设置的转速和时间，绘制曲线图。随后在.h文件中引入头文件并声明我们需要的用到的变量。首先我们需要在.pro文件中引入Qchart模块。根据自己的需求设置定时器，绘制曲线。（Qt6似乎没有这个问题）在.cpp中创建图表。_qt中绘制动态曲线
文章浏览阅读391次。将汉字转换为拼音在Android开发中是个很常见的问题。例如：在android手机应用开发中，要查询联系人的姓名，通常都是用拼音进行查询的。Pinyin4j是一个功能强悍的汉语拼音工具包，是sourceforge.net上的一个开源项目。主要的功能有： - 支持同一汉字有多个发音 - 支持拼音的格式化输出，比如第几声之类的 - 支持简体中文、繁体中文转换为拼音 首先_pinyin4j 阿拉伯数字转拼音
文章浏览阅读254次。#pragma -mark 检查更新-(void)CheckVersionUpdate{ NSDictionary *infoDic = [[NSBundlemainBundle] infoDictionary]; NSString *currentVersion = [infoDic objectForKey:_ios 无法检查更新
文章浏览阅读431次。《疯狂的程序员》里面boss绝的数据库老师说，“‘数据库原理与应用’，实际上就是数据库应用，像原理这种高深的东西，不能说，说了你们也无法理解。”想来教训得是，什么windows程序内部运行原理，其实就是教我们怎样编写一个窗口程序，一个简单的窗口程序。好，开始吧。一、程序编写函数预处理就不用说了：#include /*头文件，不解释*/#include Windows程序的入口函数，是WinMain，让我们查询MSDN。得到如下：int WINAPI WinMain( HINSTANC_笔记编程是怎么让别的东西远行原理