HDU 5536 字典树
2024-08-30 02:38:32
题意:就是公式。
这现场赛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 ;
}
最新文章
- python基础教程-第三章-使用字符串
- Kafka深入理解-3:Kafka如何删除数据(日志)文件
- 这段时间对c#和java的感受
- sizeof和strlen()的区别
- JavaScript数字精度上代码。
- 自选项目--手机锁屏软件--NABC分析
- Android WebView常见问题的解决方案总结----例如Web page not available
- JS贪吃蛇游戏
- BOM和DOM详解
- Android程序捕获未处理异常,处理与第三方方法冲突时的异常传递
- Phoenix和SQuirrel安装详解
- typedef和define的详细区别
- centos-安装python3.6环境并配置虚拟环境
- pep 8 规范的一些记录
- 我要曝光!CDN 省钱大法!
- Microsoft Azure Tutorial: Build your first movie inventory web app with just a few lines of code
- hibernate映射(学生-科目-成绩)
- Android 开发 框架系列 Android-Universal-Image-Loader 图片加载使用demo
- 05 IO和管道
- MySQL 基础二 创建表格