【bzoj3689】【异或之】【trie树+堆】
发布日期:2021-11-16 15:38:38 浏览次数:7 分类:技术文章

本文共 1362 字,大约阅读时间需要 4 分钟。

Description

给定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++中的“^”。

Input

第一行2个正整数 n,k,如题所述。

以下n行,每行一个非负整数表示A[i]。

Output

 共一行k个数,表示前k小的数。

Sample Input

4 5
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
q;struct abc{ int cnt,ch[N*30][3],size[N*30]; void insert(int x){ int now(0); for (int i=30;i>=0;i--){ int t=x&(1<
>=i; if (!ch[now][t]) ch[now][t]=++cnt; now=ch[now][t];size[now]++; } } int query(int x,int k){ int now(0),temp(0); for (int i=30;i>=0;i--){ int t=x&(1<
>=i; if (size[ch[now][t]]>=k) now=ch[now][t]; else k-=size[ch[now][t]],now=ch[now][t^1],temp+=(1<

转载地址:https://blog.csdn.net/sunshinezff/article/details/51056494 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj2754】【scoi2012】【喵星球上的点名】【AC自动机+map】
下一篇:【bzoj1954】【The xor-longest Path】【trie树】

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.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执行计划中性能最差的是_MySQL性能优化(七):MySQL执行计划,真的很重要,来一起学习吧... 2019-04-21
易语言执行mysql命令_易语言通过“打开”命令操作数据库 2019-04-21
mysql slave 1062_mysql主从同步slave错误1062 2019-04-21
mysql构造器_MySQL行构造器表达式优化(Row Constructor Expression) 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
kangle主机怎么配置MySQL_kangle web服务+easypanel主机控制面板快速搭建网站和数据库以及管理空间详细教程... 2019-04-21
mysql 翻页 存储过程_MySQl通用翻页(存储过程) 2019-04-21
2020word替换所有文本_Excel字符函数(5):REPLACE、SUBSTITUTE查找替换函数之区别... 2019-04-21
win10安装ipython_win10环境 ipython app.py 8080 这里为什么是ipython 这步无法启动 2019-04-21
假定在MYSQL_假定在名称为教学库的数据库中包含有学生、课程和选课三个表,它们的定义如下 - 问答库... 2019-04-21
mysql多字段存储过程_mysql 的存储过程_多字段 2019-04-21
python怎么创建字符串列表_如何在python列表中为每个字符串创建子列表? 2019-04-21