HDU 4825 Xor Sum【01字典树/贪心】(两数最大/最小异或和)
发布日期:2021-07-01 02:50:45
浏览次数:4
分类:技术文章
本文共 2221 字,大约阅读时间需要 7 分钟。
Problem Description
Zeus
和 Prometheus
做了一个游戏,Prometheus
给 Zeus
一个集合,集合中包含了 N
个正整数,随后 Prometheus
将向 Zeus
发起M
次询问,每次询问中包含一个正整数 S
,之后 Zeus
需要在集合当中找出一个正整数 K
,使得 K
与 S
的异或结果最大。Prometheus
为了让 Zeus
看到人类的伟大,随即同意 Zeus
可以向人类求助。你能证明人类的智慧么? Input
输入包含若干组测试数据,每组测试数据包含若干行。 输入的第一行是一个整数T
(T < 10
),表示共有 T
组数据。 每组数据的第一行输入两个正整数 N, M
(1<=N,M<=100000
),接下来一行,包含 N
个正整数,代表 Zeus
的获得的集合,之后 M
行,每行一个正整数 S
,代表 Prometheus
询问的正整数。所有正整数均不超过 2^32
。 Output
对于每组数据,首先需要输出单独一行Case #?:
,其中问号处应填入当前的数据组数,组数从 1
开始计算。对于每个询问,输出一个正整数 K
,使得 K
与 S
异或值最大。 Sample Input
23 23 4 5154 14 6 5 63
Sample Output
Case #1:43Case #2:4
题意:有最多 9
组数据,每组数据包含最多 100000
个正整数,以及最多 100000
个询问。对于每个询问 S
,在集合当中找出一个正整数 K
,使得 K
与 S
的异或结果最大。
思路:暴力算法毫无希望。本题最优的解法是使用01字典树。做法是:将数字转换为二进制01串,补成一样的长度,然后从高位到低位像普通字典树一样存储。之后,就可以贪心地解决这个问题——要找与给定的数 S
异或最大的数 K
,就应该从高位到低位、尽可能走与数 S
当前位不同的路径。反之则尽可能走与当前位相同的路径。
如果从低位到高位存储数字,然后从低位到高位走与 S
当前位不同的路径,不能得到最大的异或值,(⊙o⊙)…比如:
# / \ 0 1 \ \ 1 1 \ / \ 1 0 1 (4) (3) (5)S: 5(寻找和5异或值最大的数字)从低位到高位走不同的路径, 最终得到的是4, 而不是正解35 ^ 4 = 15 ^ 3 = 4
知道了原理后,就可以很容易地解决这道题目了。代码如下:
#includeusing namespace std;typedef long long ll;const int MAXNODE = 3300010, MAXBITS = 32; //每个数都补成33位 int trie[MAXNODE][2], pos;ll num[MAXNODE]; //记录每个插入字典树的数 void init() { memset(trie, 0, sizeof(trie)); pos = 1; }void insert(ll a) { //正整数<=2^32 int cur = 0; for (int i = MAXBITS; i >= 0; --i) { int bit = (a >> i) & 1; //求出当前位并插入 if (trie[cur][bit] == 0) trie[cur][bit] = pos++; cur = trie[cur][bit]; } num[cur] = a;}ll findXorMax(ll a) { //找到与a异或最大的那个数 int cur = 0; for (int i = MAXBITS; i >= 0; --i) { int bit = (a >> i) & 1; if (trie[cur][bit ^ 1] != 0) //优先走与当前位不同的路径 cur = trie[cur][bit ^ 1]; else cur = trie[cur][bit]; } return num[cur];}int main() { int t, n, m; ll a; scanf("%d", &t); for (int cases = 1; cases <= t; ++cases) { init(); scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%lld", &a); insert(a); } printf("Case #%d:\n", cases); for (int i = 1; i <= m; ++i) { scanf("%lld", &a); printf("%lld\n", findXorMax(a)); } } return 0;}
虽然说起来简单,但是这道题我还是提交了好几次的。一是数据范围 <= 2^32
,会爆 int
;二是要补成 33
位的二进制数;三是有多组测试用例,要记得每次重新初始化字典树。提交后AC:
转载地址:https://memcpy0.blog.csdn.net/article/details/108318897 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月13日 22时31分06秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
SpringApplication执行流程
2019-05-01
自定义Starter
2019-05-01
分布式事务原理探究(一)
2019-05-01
spring cloud consul 应用的多实例名的解决
2019-05-01
人工智能为什么这么火?看看安防江湖30年血战就知道了
2019-05-01
“前端智能为安防产生新的数据价值”
2019-05-01
(8)CMake入门笔记--CMake语法
2019-05-01
头文件中 #ifndef---#define---#endif的作用
2019-05-01
Ant内置任务之whichresource
2019-05-01
Ant内置任务之symlink
2019-05-01
jface databinding:部分实现POJO对象的监测
2019-05-01
深入理解python--线程、进程与协程(1)
2019-05-01
Java--流重点总结初稿
2019-05-01
Html2Servlet--Html代码转换为Servlet小程序
2019-05-01
ImageView scaleType
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
ffmpeg & mplayer & vlc 手册
2019-05-01
Go语言并发组件
2019-05-01