HDU 4825 Xor Sum(字典树)
2024-09-03 20:30:59
嗯...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4825
这道题更明确的说是一道01字典树,如果ch[u][id^1]有值,那么就向下继续查找/建树,如果没有则向别的方向建树,类似一个贪心的思想。
每次记录一下每个节点的编号及所代表的值。
AC代码:
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; int ch[][];
int cnt;
int val[]; inline void build(long long x){
int u = ;
for(int i = ; i >= ; i--){
int id = (x >> i) & ;
if(ch[u][id] == ) ch[u][id] = ++cnt;
u = ch[u][id];
}
val[u] = x;
} inline long long query(long long x){
int u = ;
for(int i = ; i >= ; i--){
int id = (x >> i) & ;
if(ch[u][id^]) u = ch[u][id^];
else u = ch[u][id];
}
return val[u];
} int main(){
int t;
scanf("%d", &t);
for(int i = ; i <= t; i++){
memset(ch, , sizeof(ch));
cnt = ;
memset(val, , sizeof(val));
int n, m;
scanf("%d%d", &n, &m);
for(int j = ; j <= n; j++){
long long x;
scanf("%lld", &x);
build(x);
}
printf("Case #%d:\n", i);
for(int k = ; k <= m; k++){
long long x;
scanf("%lld", &x);
printf("%lld\n", query(x));
}
}
return ;
}
AC代码
最新文章
- apache的AB测试
- .NET中Redis安装部署及使用方法简介附->;开源Redis操作辅助类
- Quartz.NET开源作业调度框架系列(五):AdoJobStore保存job到数据库
- git命令拾遗
- 细化如何安装LNMP + Zabbix 监控安装文档以及故障排除
- php随笔杂记(一)
- CLR探索应用程序域世界(上):Windbg SOS剖析揭示域世界
- android学习日记21--消息提示之Toast和Notification
- 使用pypi镜像源加速第三方库在线安装
- 【转】c++重载、覆盖、隐藏——理不清的区别
- Toast——提醒方式
- DVWA笔记之二:Command Injection
- ubuntu16.04 配置opensips服务器并编译pjsip测试
- 最简单的基于FFMPEG的图像编码器(YUV编码为JPEG)
- HBase 运维分析
- jmeter压测数据库,抓包工具,python基础
- 浅谈Python装饰器
- Vue.js——快速入门
- You Don&#39;t Know JS: Scope &; Closures (第4章: Hoisting)
- HDU - 1174:爆头 (三维平面点到射线的距离)