The XOR Largest Pair(Tire字典树应用)
2024-08-27 06:16:56
题目链接:传送门
思路:建立一个32位的字典树,对每一个要插入的数字查找它异或的最大值(就是尽量全部二进制的值都相反),
然后获得两个数异或的最大值。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+;
int ch[maxn*][],tot;
void Insert(int x)
{
int i,u=,c;
for(i=;i>=;i--)
{
c=(x>>i)&;
if(!ch[u][c]) ch[u][c]=++tot;
u=ch[u][c];
}
}
int search(int x)
{
int i,u=,c,o,ans=;
for(i=;i>=;i--)
{
c=(x>>i)&;
o=c^;
if(ch[u][o]) u=ch[u][o],ans=ans<<|;
else u=ch[u][c],ans=ans<<;
}
return ans;
}
int MAX(int x,int y)
{
return x>y?x:y;
}
int main(void)
{
int n,i,x,ans;
while(~scanf("%d",&n))
{
ans=;
memset(ch,,sizeof(ch));
tot=;
for(i=;i<n;i++)
{
scanf("%d",&x);
ans=MAX(ans,search(x));
Insert(x);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- python 学习第二十一天,django知识(三)
- 16083001(古墓丽影GPA)
- MySQL之MySQL5.7安装包(msi文件)在Windows8下安装
- 让32位Eclipse和64位Eclipse同时在64的Windows7上运行
- 【leetcode】Find Peak Element ☆
- 如何使用GCD(ZZ)
- 【Perl学习笔记】2. perl中的bless理解
- Log Collect
- QQ音乐产品经理黄楚雄:产品与用户的情感联系
- PHP xdebug的安装
- 软考论文的六大应对策略V1.0
- javascript、ruby和C性能一瞥(3) :上汇编
- 17-Flink消费Kafka写入Mysql
- GMA Round 1 新程序
- Class.forName的作用?为什么要用?
- Windows7下安装、部署Weblogic和发布war项目
- C盘清理(安装Visual Studio 或者Office后)
- JAVA记录-JDBC介绍
- js函数作用域
- .NET Core 中 IOptions 有什么用