HDU 4825 Xor Sum【01字典树/贪心】(两数最大/最小异或和)
发布日期:2021-07-01 02:50:45
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年05月07日 11时52分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
node.js AES/ECB/PKCS5Padding 与其他语言的加密解密通用
2019-05-02
node.js 实现一个简单的登录拦截器
2019-05-02
c++抽象类、纯虚函数以及巧用纯虚析构函数实现接口类【转】
2019-05-02
WebRTC学习记录(1):采集microphone到文件原理实践&讲解【转】
2019-05-02
Caffe 安装错误记录及解决办法【转】
2019-05-02
Android用类继承Application的全局变量使用注意
2019-05-02
qml之TextField使用笔记
2019-05-02
排序算法之冒泡排序
2019-05-02
排序算法之选择排序
2019-05-02
排序算法之希尔排序
2019-05-02
pyqt5之拖拽
2019-05-02
pyqt5之俄罗斯方块
2019-05-02
算法排序之归并排序
2019-05-02
算法排序之快速排序
2019-05-02
算法排序之堆排序
2019-05-02
算法排序之计数排序
2019-05-02
算法排序之桶排序
2019-05-02
C++ Template初识函数模板(2.1节,2.2节)
2019-05-02
C++ Template函数模板参数(2.3节)
2019-05-02
C++ Template重载函数模板(2.4节)
2019-05-02