HDU 4825 Xor Sum (模板题)【01字典树】
2024-10-15 16:41:22
<题目链接>
题目大意:
给定n个数,进行m次查找,每次查找输出n个数中与给定数异或结果最大的数。
解题分析:
01字典树模板题,01字典树在求解异或问题上十分高效。利用给定数据的二进制数进行建树,然后在查找的时候,利用贪心的策略,优先寻找与当前位数的0、1值不同的路线,从而达到异或值最大的目的。
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 1e5+;
int n,m,pos;
ll val[N*],nxt[N*][]; void init(){
pos=;
memset(nxt,,sizeof(nxt));
memset(val,,sizeof(val));
}
void Insert(ll x){ //用x的二进制建树
int now=;
for(int i=;i>=;i--){
int to=(x>>i)&; //从最高位开始建
if(!nxt[now][to])nxt[now][to]=++pos;
now=nxt[now][to];
}
val[now]=x; //标记前缀二进制串为完整的数字
}
ll query(ll x){ //寻找01Trie树上异或的最大数
int now=;
for(int i=;i>=;i--){
int to=(x>>i)&;
if(nxt[now][to^])now=nxt[now][to^]; //优先找与当前位不同的路线
else now=nxt[now][to]; //如果没有的话,只能找相同的
}
return val[now];
}
int main(){
int ncase=;
int T;scanf("%d",&T);while(T--){
init();
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
ll cur;scanf("%lld",&cur);
Insert(cur);
}
printf("Case #%d:\n",++ncase);
for(int i=;i<=m;i++){
ll cur;scanf("%lld",&cur);
printf("%lld\n",query(cur));
}
}
}
2019-03-02
最新文章
- eclipse远程调试Tomcat方法[转]
- LR手工制作webServices接口类脚本
- Apache配置代理服务器的方法(1)
- linux 安装webbench
- 通过chrome 获取网站的cookie信息
- 【.Net--资料】
- 如何在Maven官网下载到历史版本
- 开源网站管理工具—Altman
- HDFS集群balance(2)-- 架构概览
- stray &#39;/241&#39; in program 错误
- Quartz总结(三):动态修改定时器一
- 201521123016 《Java程序设计》第7周学习总结
- gcc学习(二)[第二版]
- HDU-6397(2018 Multi-University Training Contest 8) Character Encoding(生成函数+组合数学)
- 使用ajax请求后端程序时,关于目标程序路径问题
- display style edit
- 安卓TP驱动开发
- [ACM_动态规划] hdu 1176 免费馅饼 [变形数塔问题]
- Test类实验
- 使用selenium进行密码破解(绕过账号密码JS加密)
热门文章
- Confluence 6 Oracle 连接问题解决
- swift项目初始化并添加忽略文件Swift.ignore
- Java编程的分期步骤(一)
- 量化投资与Python
- SpringBoot图片上传(二)
- appium获取APP控件信息
- Android取得系统时间
- 用 DocumentFormat.OpenXml 和Microsoft.Office.Interop.Word 写入或者读取word文件
- ***在Linux环境下mysql的root密码忘记解决方法(三种)-推荐第三种
- 小改造gotty,使之适合接收经过一层加密的URL