HDU 5536 Chip Factory Trie
2024-08-26 18:54:01
题意:
给出\(n(3 \leq n \leq 1000)\)个数字,求\(max(s_i+s_j) \bigoplus s_k\),而且\(i,j,k\)互不相等。
分析:
把每个数字看成一个\(01\)字符串插入倒Trie树中去,枚举\(i\)和\(j\),然后把\(s_i\)和\(s_j\)从Trie树中删去。
然后在Trie树中贪心找到能与\(s_i+s_j\)异或得到的最大值。
具体匹配的过程中是这样的,首先看树中最高位能否异或得到\(1\)。
能的话就往能的那个方向走,否则往另外一个方向走。
另外删除操作是这样实现的,我们每个节点记录一个\(val\)值。
插入时对所有经过节点的\(val\)值加\(1\),删除就将对应节点的\(val\)值减\(1\)。
在树上匹配的时候就只走那些\(val\)值为正的节点。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 10;
const int maxnode = 100000 + 10;
int n;
int s[maxn];
int sz;
int ch[maxnode][2];
int val[maxnode];
void init() {
sz = 1;
memset(ch[0], 0, sizeof(ch[0]));
}
//d=1表示插入,d=-1表示删除
void update(int v, int d) {
int u = 0;
for(int i = 30; i >= 0; i--) {
int c = (v >> i) & 1;
if(!ch[u][c]) {
memset(ch[sz], 0, sizeof(ch[sz]));
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
val[u] += d;
}
}
int match(int v) {
int ans = 0, u = 0;
for(int i = 30; i >= 0; i--) {
int c = (v >> i) & 1;
if(ch[u][c^1] && val[ch[u][c^1]]) {
ans |= (1 << i);
u = ch[u][c^1];
}
else u = ch[u][c];
}
return ans;
}
int main()
{
int T; scanf("%d", &T);
while(T--) {
init();
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", s + i);
update(s[i], 1);
}
int ans = (s[1] + s[2]) ^ s[3];
for(int i = 1; i < n; i++) {
update(s[i], -1);
for(int j = i + 1; j <= n; j++) {
update(s[j], -1);
int t = match(s[i] + s[j]);
ans = max(ans, t);
update(s[j], 1);
}
update(s[i], 1);
}
printf("%d\n", ans);
}
return 0;
}
最新文章
- Android开发之画图的实现
- 延迟加载外部js文件,延迟加载图片(jquery.lazyload.js和echo,js)
- win10环境下使用苹果虚拟机不要开多线程应用下载文件
- 是时候学习Android分屏开发了
- js的面向对象的程序设计之理解继承
- tomcat 6 不支持jsf2.2,仅支持jsf2.0及以下版本
- C#设置程序自启动
- js MD5加密后的字符串
- Ubuntu如何备份和恢复系统 - 落花往事的日志 - 网易博客
- eclipse中集成svn maven开发手册---导入项目
- 在Visual Studio中入门F#
- js正则表达式中test,exec,match方法的区别说明
- AES加密然后ajax传输数据
- Chemical table CFR500 div2D(并查集)
- PHP连接MySQL查询中文时显示Notice: Trying to get property of non-object
- HDU2665 求区间第K大 主席树
- topcoder srm 440 div1
- 利用nginx搭建RTMP视频点播、直播、HLS服务器(转)
- SharePoint 2016 站点注册工作流服务报错
- 从ext4将mysql数据目录移动至lustre出现(InnoDB: Unable to lock ./ibdata1, error: 38.)
热门文章
- 重写FileUpload控件让它可以显示上传后的文件名
- JSON(未完待续,等讲到对象时再加)
- guacamole 0.9.13安装与配置
- Mac下安装ElasticSearch及其插件
- LaTeX小技巧——File ended while scanning use of \@writefile错误的
- Ubuntu批量修改权限
- Hadoop 2.7.0模拟分布式实验环境搭建[亲测]
- Netweaver和SAP云平台的quota管理
- [论文理解]SSD:Single Shot MultiBox Detector
- Python-OpenCV中图像合并显示