中南oj 1216: 异或最大值 数据结构
2024-09-01 21:27:45
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 ;
}
最新文章
- 前端可视化开发-livereload
- python3练习-杨辉三角/帕斯卡三角形
- Android属性(property)机制
- 离散系统频响特性函数freqz()
- QRTZ_表注释
- ubuntu apache2 wsgi 部署django
- Mac android 开发 sdk配置和手机连接
- SCSF智能客户端学习笔记(一)
- ThreadPoolTaskExecutor异步的处理报警发送邮件短信比较耗时的东东
- WinCE5.0中文模拟器SDK(VS2005)的配置
- 利用Spring.Net技术打造可切换的分布式缓存读写类
- oracle 存储过程 动态sql语句
- 返回List的分页方法
- BHO多线程中实现右键菜单
- 关于mysql的安装
- Android Bitmap与DrawAble与byte[]与InputStream之间的转换工具类【转】
- static与final的区别
- 用Maxima画出一些有趣的图
- Armstrong公理
- qhfl-5 redis 简单操作