当前位置: 首页 > >

CSU 1216 异或最大值(01Trie)

发布时间:

字典树,碰到了一个同类型但比这个难点的题,不会做,先找个简单的来练练,铺垫下。01Trie就是每层只有0和1的字典树。把一个数字的二进制看成字符串,从高位到低位放进字典树。
http://blog.csdn.net/fuyukai/article/details/50366133
这里讲的很详细。


??-2017.11.06??????
突然想到,这题代码是错误的,数据水,还是过了,query那里写错了,正确代码见:http://blog.csdn.net/gyhguoge01234/article/details/78357625
虽然不是一个题了,但大致一样


#include
#include

const int MAXN = 1e5+10;

template
T max(const T a, const T b)
{
if(a > b) return a;
return b;
}

struct Trie
{
int next[MAXN*31][2];
int root,sz;

void init()
{
memset(next,-1,sizeof(next));
sz = 0;
root = 0;
}

void insert(int x)
{
int now = root;
for(int i = 31; i >= 0; --i)
{
int t = (x>>i)&1;
if(next[now][t] == -1)
next[now][t] = ++sz;
now = next[now][t];
}
}

int query(int x)
{
int ret = 0,t;
int now = root;
for(int i = 31; i >= 0; --i)
{
t = (x>>i)&1;
if(next[now][!t] != -1)
t = !t;
ret |= t< now = next[now][t];
}
return ret;
}
};

Trie t;

int main()
{
int n,res,num;
while(scanf("%d",&n) != EOF)
{
t.init();
res = -1;
for(int i = 0; i < n; ++i)
{
scanf("%d",&num);
t.insert(num);
res = max(res,num^t.query(num));
}
printf("%d
",res);
}
return 0;
}



友情链接: