HDU 5536 字典树

HDU 5536  字典树

题意:就是公式。

这现场赛O(n^3)能过,觉得太没天理了。

做法:字典树,枚举两个数,然后在字典树上贪心的跑。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = ;

struct Trie {
int ch[],size;
}T[MAXN]; int root = ,tot = ; void Insert(int x) {
int o = root;
T[o].size++; for(int k = ; k >=; k--) {
int c;
if(x&(<<k)) c = ;
else c = ;
if(!T[o].ch[c]) T[o].ch[c] = ++tot;
o = T[o].ch[c];
T[o].size++;
}
} void Delete(int x) {
int o = root;
T[o].size--; for(int k = ; k >=; k--) {
int c;
if(x&(<<k)) c = ;
else c = ;
o = T[o].ch[c];
T[o].size--;
}
} int Query(int x) {
int o = root;
for(int k = ; k >=; k--) {
int c;
if(x&(<<k)) c = ;
else c = ;
if(c==) {
if(T[o].ch[]&&T[T[o].ch[]].size) o = T[o].ch[];
else o = T[o].ch[],x^=(<<k);
}
else {
if(T[o].ch[]&&T[T[o].ch[]].size) o = T[o].ch[],x^=(<<k);
else o = T[o].ch[];
}
}
return x;
} int a[MAXN]; int main()
{
//freopen("in.txt","r",stdin);
int T_T,n;
scanf("%d",&T_T);
while(T_T--) {
scanf("%d",&n);
int ans = ;
for(int i = ; i <= n; i++) scanf("%d",&a[i]);
for(int i = ; i <= n; i++)
Insert(a[i]); for(int i = ; i <= n; i++) {
Delete(a[i]);
for(int j = i+; j <= n; j++) {
Delete(a[j]);
ans = max(ans,Query(a[i]+a[j]));
Insert(a[j]);
}
Insert(a[i]);
}
printf("%d\n",ans);
for(int i = ; i<=tot; i++) T[i].ch[] = T[i].ch[] = T[i].size = ;
tot = ;
}
return ;
}
上一篇:ios开发之数据存储


下一篇:C#学习笔记(24)——C#将PPT批量转为JPG(最简单的方法)