1216: 异或最大值

Time Limit: 2 Sec  Memory Limit: 128 MB Submit: 98  Solved: 29 [Submit][Status][Web Board]

Description

给定一些数,求这些数中两个数的异或值最大的那个值

Input

第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

Output

任意两数最大异或值

Sample Input

3
3
7
9

Sample Output

14

HINT

这道题,我学到了一些新的知识。

没有写过字典树。这题用01字典树。

构建树,和树形dp是一样的,都是树。

思路:

  暴力会超时。

  用字典树,01字典树。

 #include<stdio.h>
#include<stdlib.h>
#include<string.h> typedef struct
{
int a[];
int num;
}Tril;
Tril f[<<];
int root,ans; void insert(int x,int u,int num)
{
int i,k;
for(i=num;i>=;i--)
{
k=(<<i&x)?:;
if(f[u].a[k]==-)
f[u].a[k]=root++;
u=f[u].a[k];
}
f[u].num=x;
}
void query(int x,int u,int num)
{
int i,j,k;
for(i=num;i>=;i--)
{
k=(<<i&x)?:;
if(f[u].a[k]!=-)
u=f[u].a[k];
else
u=f[u].a[k^];
}
j=f[u].num^x;
if(j>ans)
ans=j;
}
int main()
{
int n,i,x;
while(scanf("%d",&n)>)
{
memset(f,-,sizeof(Tril)*((n+)<<));
ans=;
root=;
for(i=;i<=n;i++)
{
scanf("%d",&x);
insert(x,,);
query(x,,);
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. 前端可视化开发-livereload
  2. python3练习-杨辉三角/帕斯卡三角形
  3. Android属性(property)机制
  4. 离散系统频响特性函数freqz()
  5. QRTZ_表注释
  6. ubuntu apache2 wsgi 部署django
  7. Mac android 开发 sdk配置和手机连接
  8. SCSF智能客户端学习笔记(一)
  9. ThreadPoolTaskExecutor异步的处理报警发送邮件短信比较耗时的东东
  10. WinCE5.0中文模拟器SDK(VS2005)的配置
  11. 利用Spring.Net技术打造可切换的分布式缓存读写类
  12. oracle 存储过程 动态sql语句
  13. 返回List的分页方法
  14. BHO多线程中实现右键菜单
  15. 关于mysql的安装
  16. Android Bitmap与DrawAble与byte[]与InputStream之间的转换工具类【转】
  17. static与final的区别
  18. 用Maxima画出一些有趣的图
  19. Armstrong公理
  20. qhfl-5 redis 简单操作

热门文章

  1. Mac下显示和隐藏“隐藏文件”
  2. 【BZOJ1296】[SCOI2009]粉刷匠 (DP+背包)
  3. js中的类和对象以及自定义对象
  4. 简明依赖注入(Dependency Injection)
  5. SQL数据库Truncate的相关用法
  6. grep练习
  7. vue使用nprogress页面加载进度条
  8. APP开发的三种技术对比
  9. 纯Python给ulaw wav文件加头
  10. C++析构函数(转)