给定n个非负整数A[1], A[2], ……, A[n]。 对于每对(i, j)满足1 <= i < j <= n,得到一个新的数A[i] xor A[j],这样共有n*(n-1)/2个新的数。求这些数(不包含A[i])中前k小的数。 注:xor对应于pascal中的“xor”,C++中的“^”。
【bzoj3689】【异或之】【trie树+堆】
发布日期:2021-11-16 15:38:38
浏览次数:7
分类:技术文章
本文共 1362 字,大约阅读时间需要 4 分钟。
Description
Input
第一行2个正整数 n,k,如题所述。 以下n行,每行一个非负整数表示A[i]。
Output
共一行k个数,表示前k小的数。
Sample Input
4 5
1
1
3
4
1
1
3
4
Sample Output
0 2 2 5 5
HINT
【样例解释】 1 xor 1 = 0 (A[1] xor A[2]) 1 xor 3 = 2 (A[1] xor A[3]) 1 xor 4 = 5 (A[1] xor A[4]) 1 xor 3 = 2 (A[2] xor A[3]) 1 xor 4 = 5 (A[2] xor A[4]) 3 xor 4 = 7 (A[3] xor A[4]) 前5小的数:0 2 2 5 5 【数据范围】 对于100%的数据,2 <= n <= 100000; 1 <= k <= min{250000, n*(n-1)/2}; 0 <= A[i] < 2^31
题解:对所有的数建立trie树.
每个节点多记一个size,表明这个点下面有多少单词.这样就可以查第k小的异或值了。
首先把每个数的第二小的异或之压进堆中。因为第一小一定是和它自己。
由于一个异或值会被两个数各记录一遍,
所以我们取k*2次堆顶,只在奇数次取堆顶的时候输出答案。
假设取出了一个数的第k小异或值,那就把它的第k+1小异或值入堆即可。
代码:
#include#include #include #include #define N 100010 using namespace std;int n,a[N],k,mx;struct use{ int k,v,a;};bool operator<(use x,use y){return x.v>y.v;}priority_queue
转载地址:https://blog.csdn.net/sunshinezff/article/details/51056494 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月13日 20时22分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
当集合a为空集时a的取值范围_1.1.2 集合间的基本关系
2019-04-21
vue 可合并表格组件_Vue实战046:详解Mixins混入使用和注意事项
2019-04-21
python包怎么做双重差分did分析_多变量相关性分析(一个因变量与多个自变量)
2019-04-21
fi sap 凭证冲销 稅_SAP中的成本要素
2019-04-21
mysql幻读是什么意思_MySQL中的幻读,你真的理解吗?
2019-04-21
易语言执行mysql命令_易语言通过“打开”命令操作数据库
2019-04-21
mysql slave 1062_mysql主从同步slave错误1062
2019-04-21
2008日志清理 server sql_SQL Server 2008 清除日志
2019-04-21
mac mysql root 权限_Mac平台重新设置MySQL的root密码
2019-04-21
mysql新增一列_MySQL-ProxySQL中间件
2019-04-21
mysql 30入门_30分钟带你快速入门MySQL教程
2019-04-21
mysql 翻页 存储过程_MySQl通用翻页(存储过程)
2019-04-21
mysql多字段存储过程_mysql 的存储过程_多字段
2019-04-21
python怎么创建字符串列表_如何在python列表中为每个字符串创建子列表?
2019-04-21