首页 > The XOR Largest Pair
开通博客写题解
头像 林思艺
发表于 2020-10-23 19:31:25
题意 你有个数，要求你选择其中的两个数使得他们的异或值最大。 分析 由于位运算都是按位进行，也就是说在二进制下的位运算每一位之间是独立的。我们还知道二进制下位数越高，对应的值也就越高。（也就是）。也就是我们就是要让两个数在二进制下从高位到低位尽可能的不同。那我们考虑建一棵字典树，对每一个数字进行一次 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 熠丶
发表于 2020-10-23 00:51:13
前言：暑假集训时学的字典树orz 太弱了www模板用的是wiki上用一个结构体封装的模板（当时就是看wiki学的字典树链接：https://oi-wiki.org/string/trie/ 做法：01字典树 思路： 一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 子希
发表于 2020-10-27 15:55:01
随便说说：第一次发现字典树还能这样用，以前都是用字典树求一些最简单的'a'-'z'前缀相同的个数,直到看见这道题。。。。才发现数据结构用好了是真的可以无敌。。。 思路：暴力枚举两个数肯定是超时，那么我们希望有这样一种操作，我们枚举每个数，枚举到当前这个数，我们希望能够在一个很快的时间里(可以是或者) 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 DeNeRATe
发表于 2020-11-01 21:45:55
分析 由于我们可以二进制按位贪心所以直接使用01Trie树即可维护每个数字的终止节点对于每个数，每次贪心往0或1走即可时间复杂度： 代码 //The XOR Largest Pair #include <algorithm> #include <iostream> #incl 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 shyyhs
发表于 2020-10-27 15:43:52
https://paste.ubuntu.com/p/qP4x7Y2nB6/ 这是代码,拿颗01字典树按位异或即可,然后尽可能取高位的1.
去ta的博客 赞 (4) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-10-23 16:06:49
The XOR Largest Pair 题目描述 给定一串长度为 序列，问序列中的两个数异或值最大是多少 分析 不难发现，要让两个数的异或值尽可能的大，就是要让两个数在二进制下 从高位到低位 尽可能的不同比如一个数是这样的 ，那么在 中与这个数异或值最大的数就是 考虑建一棵 字典树，对每一个 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Kur1su
发表于 2020-10-30 16:40:22
Description Solution 建立01Trie,对于每一个数字都从最高位开始建立字典树，并且贪心地从最高位开始在字典树上走，优先走该位不同的路线，最后取最大的答案。 Code #include <bits/stdc++.h> using namespace std; typ 展开全文
去ta的博客 赞 (4) 回复(3) 收起
头像 rk_no
发表于 2020-10-22 22:46:03
题目： 在给定的N个整数中选出两个进行运算，得到的结果最大是多少？ 做法： 经典套路，字典树处理2个数的最值。其本质是一个贪心，高位若值为必定优于低位。我们把个整数依次插入字典树，每次插入前在字典树上跑一个贪心就能得到：前个数中选某个和第个数的最大值是多少。个数跑完取，最优解肯定在其中。 代码： 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 expect2004
发表于 2020-10-27 11:23:07
Statement 在给定的 个整数 ​中选出两个进行 运算，得到的结果最大是多少？ Solution 建立 0-1 Trie。 0-1 Trie 是一类特殊的字典树，之所以特殊，在于其的字符集为 。 由于二进制中数码也只有 ，所以 0-1 Trie 上的一条路径可以看做一个数的二进制位。 考 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 LB_tq
发表于 2020-10-25 21:11:41
Solution 题目要求一对数使得异或值最大。考虑异或运算的特点：按位进行且不进位。可以想到转化为二进制数进行操作，对每一位分别处理。 把每个整数看做长度为 的 串构建字典树。最低位为字典树的叶子结点。对于数 ，在字典树中检索一次，每次都尝试沿着“与 当前位相反的字符”向下访问。若存在这样 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”