HDU 4825 Xor Sum (模板题)【01字典树】

<题目链接>

题目大意:

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

上一篇:macOS通过ssh使用PEM登录


下一篇:C# 函数式编程:LINQ