BZOJ 3689 异或之

发布于 2017-06-28  179 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3689

题意:求 n 个数两两异或得到的数中最小的 k 个


为了做 3261 发现需要先会做 3689... 会做 3689 首先需要会做一个经典的问题:

求 n 个数两两异或得到的数中最小的那个

朴素的暴力是\(O(n^2)\) 的,我们考虑异或的性质来简化一些情况。显然按位贪心是最优的,选定一个数后,选择的另一个数能消掉原数的位越高越优。

那么用一棵 trie 树来维护整个数列即可。

现在考虑这个问题:求最小的 k 个,首先考虑转化问题:求确定一个数后第 k 小异或值,我们可以在建立 trie 树时记录一下每个节点的\(size\), 依旧贪心查询,如果较优的方向不足 k 个,则选择另一侧即可。

那么动态维护整个数列的 k 小也是容易的了,首先将每个数的最小值推进堆,每次取出某个数的第 k 小后推入 k+1 即可,有一些小细节:

原题意显然数对正反是一样的,那么每个答案会重复统计两次,只输出奇数次即可。

查询的朴素写法需要从 2 开始,因为最小的异或值是异或自身

 


一个非常弱的准退役OIER