<题目链接>

题目大意:

给定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

最新文章

  1. eclipse远程调试Tomcat方法[转]
  2. LR手工制作webServices接口类脚本
  3. Apache配置代理服务器的方法(1)
  4. linux 安装webbench
  5. 通过chrome 获取网站的cookie信息
  6. 【.Net--资料】
  7. 如何在Maven官网下载到历史版本
  8. 开源网站管理工具—Altman
  9. HDFS集群balance(2)-- 架构概览
  10. stray &#39;/241&#39; in program 错误
  11. Quartz总结(三):动态修改定时器一
  12. 201521123016 《Java程序设计》第7周学习总结
  13. gcc学习(二)[第二版]
  14. HDU-6397(2018 Multi-University Training Contest 8) Character Encoding(生成函数+组合数学)
  15. 使用ajax请求后端程序时,关于目标程序路径问题
  16. display style edit
  17. 安卓TP驱动开发
  18. [ACM_动态规划] hdu 1176 免费馅饼 [变形数塔问题]
  19. Test类实验
  20. 使用selenium进行密码破解(绕过账号密码JS加密)

热门文章

  1. Confluence 6 Oracle 连接问题解决
  2. swift项目初始化并添加忽略文件Swift.ignore
  3. Java编程的分期步骤(一)
  4. 量化投资与Python
  5. SpringBoot图片上传(二)
  6. appium获取APP控件信息
  7. Android取得系统时间
  8. 用 DocumentFormat.OpenXml 和Microsoft.Office.Interop.Word 写入或者读取word文件
  9. ***在Linux环境下mysql的root密码忘记解决方法(三种)-推荐第三种
  10. 小改造gotty,使之适合接收经过一层加密的URL