2023.01.11 补数组大小分析:
在构建 tire 树中设 son 数组大小为 [M][2],其中 M=N∗31,可是为什么是这样呢?下面以 N 为 4 来模拟一下题目,并给出解释。
设 N 为 4 即有 4 个输入如下所示:
a[0]:0000 0000 0000 0000 0000 0000 0000 000
a[1]:0100 0000 0000 0000 0000 0000 0000 000
a[2]:1000 0000 0000 0000 0000 0000 0000 000
a[3]:1100 0000 0000 0000 0000 0000 0000 000
有不少同学觉得 M 的大小应该是 N 或 31。这是远远不够的,注意看,此时输入的 N 个数都不尽相同。
观察下图的 tire 树(为了看起来容易些,将所有的树叉都花了出来,单实际上在第 k 个数输入前只有 k−1 根树叉)和 son 数组,由于存储的实际上是 idx,因此有多少个在不同位置上不同的二进制数就有多少个不同的 idx,本例比较极端,几乎用到了 4∗31=124 全部的位置,但实际上题目不会这么极端,因此设置为 N∗31 是足够的。
分析:
这里先回顾一下异或的操作。异或(Exclusive or, XOR)为当两二进制数值相同时为否,而数值不同时为真。在编程语言中,常表示为 p ^ q
。直观如下:
在本题当中可以对给出的 N 个整数进行暴力枚举同时记录两两最大的异或结果。很不幸暴力的做法会超时,下面给出暴力代码:
// 起码是 0(两个一样的数)
int res = 0
for (int i = 0; i < n; i ++) // 枚举第一个数
{
for (int j = 0; j < i; j ++) // 枚举第二个数,可以避免重复枚举
res = max(res, a[i] ^ a[j])
}
那我们要进行优化,具体为对内层循环进行优化。由于数据小于 231,因此可以将每个整数看成长度为 31 位的二进制串。那能使 a[i] 与其异或值最大的整数一定是高位至低位与a[i]有尽可能多的不同位(使异或结果可以尽可能多地获得1)。流程如下所示,假设由 a[0] 至 a[i−1] 已经构建好了trie树,且 a[i] 的二进制表示为 101110…1。在贪心准则下每次往能获得最大异或值的方向走,若其他整数不能使当前位获得最大值(假设 a[i] 当前位为0,而tire树中只有0可以走),也只能先将就一下往这里走,等下一位再追求最好的。直至走完 a[i]。
注:对于 a[i] 来讲,它面临的 trie树,是由 a[0]…a[i−1] 构建的。
以上就是利用trie树优化内层的循环的思想,并且每次 a[i] 只和 a[j] (j<i) 的数进行运算即可,这是因为 p ^ q = q ^ p
(^ 为异或运算)。
另外需要注意一个细节,对于每一个 a[i](0≤i≤N)是先进行对其进行最大异或值查询再插入进 trie树还是先插入再查询呢?这里我们采用先插入再查询的流程,因为对于第一个整数来讲,trie树为空,若此时进行异或运算可能会非法的结果;若先插入再查询,则第一个数一定是和自己做异或运算,由于异或运算的性质,可以得出结果一定为0。
别扭的位运算
由于本题都是对二进制数进行操作,因此我打算先提前把位运算说清楚,这样在看代码时会事半功倍。
左移运算(<<):在C++中,若对整数进行左移操作,如 x << 1
,即把每一位向前(左)推一位后在末尾补上0,相当于将这个数放大2倍。这是为什么呢?请看下图:
右移运算(>>):在C++中,若对整数进行左移操作,如 x >> 1
,即把每一位向后(右)推一位,并把推出去的数去掉,相当于将这个数缩小2倍。具体细节可将左移推导中的乘法转换为除法即可。同理也要搞清楚左移 k 位以及右移 k 位的含义。
有了左右移的概念之后,我们来看一下代码中经常出现的位运算操作之一:x >> k & 1
。大家都将该操作称为“看看第 k 位(k 从0开始)”。该操作为将 x 的二进制表示右移 k 位后与0000…01按位求与运算。我想与运算大家肯定明白,那为什么是看看第 k 位呢?由于二进制只有0和1,求与运算后若为0,说明第 k 位是0;若是1,说明第 k 位是1。例见下图:
代码(C++)
#include <iostream>
using namespace std;
const int N = 100010, M = 31 * N;
int a[N], son[M][2], n, idx;
void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i --)
{
// 取出 x 的第 i 位二进制数
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
int query(int x)
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i --)
{
// 从高位向低位操作
int u = x >> i & 1;
// 对于当前位的二进制数
// 尽可能往其出现过的相反的方向走,假设当前位 u = 0
// 若1的那个方向的 trie树枝干被创建则向那个方向走
// 若没有被创建,则先将就一下走0的方向
if (son[p][!u])
{
p = son[p][!u];
// 相当于 + 000..000u
res = (res << 1) + !u; // 将当前位加到左移后空出的第0位上
}
else
{
p = son[p][u];
res = (res << 1) + u;
}
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
int res = 0;
for (int i = 0; i < n; i ++)
{
// 先插入后运算是为了避免边界问题,对于第一个整数整个树为空
// 若先将自己插入进去,则与自己的异或结果始终为0
insert(a[i]);
// t 为 a[0]至a[i-1] 中与a[i]异或值最大的那个整数
// 即够成局部最大异或对
int t = query(a[i]);
// 看是否是所有整数中的最大异或对
res = max(res, a[i] ^ t);
}
cout << res;
}
我测,总算学懂了,大四老汉开始学算法,基础课都给我劝退了
大家注意楼主的query函数返回的是目前的tire树内与参数x的最大异或数,而不是异或后的结果。
如果是直接return 异或后的结果的话,要稍微改一下if else内对res的处理
if (son[p][!u]) { p = son[p][!u]; res = (res << 1) +1; } else { p = son[p][u]; res = (res << 1); }
原来son是这样的意思!!!
大佬
为什么不从低位往高位存值
大佬讲的太好了
最坏情况 1e5个不同数, 树最底层最大为1e5个, Ai<2^31共31层 开31*1e5
真的讲得清楚!我放了一个大佬帖子的链接在我的打卡里了,如果不希望我放的话QWQ麻烦大佬联系我一下,立删www谢谢了~
在构建 tire 树中设 son 数组大小为 [M(N∗31)][2]
我刚开始以为M(N*31)是这个数组的需要的常数,修改一下会不会可读性更好一些wwww感谢建议,我一开始也觉得这样写不太清楚hhh
感谢大佬