基数树（radix tree）
目录
CSU 1323: ZZY and his little friends（异或最大值）
一，基数树（radix tree）
基数树和字典树差不多，只不过字典树的基本单位是字符，一般一个节点有大约26个或52个子节点，而基数树的基本单位是若干比特位。
思路：
无论S是结构体还是整数，都直接当做若干比特位，每x个比特位划分为一份，一共len/x份，len是S的比特数
每个节点需要2^x个指针或者整数，每一个对应x个比特位的一个取值。
整个树的深度是deep=len/x，节点总数的上限为len/x*N, N是存储目标的总数
总空间大小为len/x*N*2^x*4 字节，即4N * len * 2^x/x，所以一般取x=1或2或4
x=1或2或4，分别对应二叉树，四叉树，16叉树
应用场景： 结构体的存储和查找、求异或最大值
二，OJ实战
CSU 1216: 异或最大值
题目：
Description
给定一些数，求这些数中两个数的异或值最大的那个值
Input
多组数据。第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。
Output
任意两数最大异或值
Sample Input
3
3
7
9
Sample Output
14
代码：
-
#include<iostream>
-
#include<string.h>
-
using namespace std;
-
-
const int m = 3000000;
-
int ans[m][2], key;
-
-
int f(int x)
-
{
-
for (int i = 29, k = 0; i >= 0; i--)
-
if (ans[k][1 - (x >> i) % 2] == 0)
-
{
-
k = ans[k][(x >> i) % 2];
-
if ((x >> i) % 2)x ^= (1 << i);
-
}
-
else
-
{
-
k = ans[k][1 - (x >> i) % 2];
-
if ((x >> i) % 2 == 0)x ^= (1 << i);
-
}
-
return x;
-
}
-
-
int main()
-
{
-
int n, m, r;
-
while (scanf("%d",&n)!=EOF)
-
{
-
r = 1 << 31;
-
memset(ans[0], 0, sizeof(ans[0]));
-
key = 0;
-
for (int i = 1; i <= n; i++)
-
{
-
scanf("%d", &m);
-
if (f(m) > r)r = f(m);
-
for (int k = 29, j = 0; k >= 0; k--)
-
{
-
if (ans[j][(m >> k) % 2] == 0)
-
{
-
ans[j][(m >> k) % 2] = ++key;
-
memset(ans[key], 0, sizeof(ans[key]));
-
}
-
j = ans[j][(m >> k) % 2];
-
}
-
}
-
printf("%d\n", r);
-
}
-
return 0;
-
}
CSU 1323: ZZY and his little friends（异或最大值）
题目：
Description
zzy养了一只小怪兽和N只凹凸曼，单挑的话每只凹凸曼都不是小怪兽的对手，所以必须由两只凹凸曼合作来和小怪兽战斗。凹凸曼A和凹凸曼B合作的战斗力为他们战斗力的异或值。现在由zzy从N只凹凸曼中选出两只来和小怪兽战斗。请问zzy能否选出两只凹凸曼使他们能够战胜小怪兽(他们的战斗力比小怪兽大)。
Input
输入有多个例子，直到文件结束。 每个例子的第一行含两个数N和M，表示有N(2<=N<=100000)只凹凸曼，小怪兽的战斗力为M(0<M<=1000000000)。接着有一行N个数，每个数Ai(0<Ai<M)表示每只凹凸曼的战斗力。
Output
对于每个例子输出一行，如果能选出两只凹凸曼使他们战胜小怪兽输出"YES", 否则输出"NO"(不含引号)
Sample Input
2 5
1 1
2 6
5 2
Sample Output
NO
YES
思路：
用字典树存下所有的数，然后枚举对于每个数，利用字典树在O（1）时间内得到贪心最大值
当然，可以稍微优化一下，边建立字典树边枚举每个数
代码：
-
#include<iostream>
-
#include<string.h>
-
using namespace std;
-
-
const int m = 3000000;
-
int ans[m][2], key;
-
-
int f(int x)
-
{
-
for (int i = 29, k = 0; i >= 0; i--)
-
if (ans[k][1 - (x >> i) % 2] == 0)
-
{
-
k = ans[k][(x >> i) % 2];
-
if ((x >> i) % 2)x ^= (1 << i);
-
}
-
else
-
{
-
k = ans[k][1 - (x >> i) % 2];
-
if((x >> i) % 2==0)x ^= (1 << i);
-
}
-
return x;
-
}
-
-
int main()
-
{
-
int n, m, num;
-
while (cin>>n>>m)
-
{
-
bool flag = false;
-
memset(ans[0], 0, sizeof(ans[0]));
-
key = 0;
-
for (int i = 1; i <= n; i++)
-
{
-
cin >> num;
-
if (flag)continue;
-
if (f(num) > m)flag = true;
-
for (int k = 29, j = 0; k>=0; k--)
-
{
-
if (ans[j][(num >> k) % 2] == 0)
-
{
-
ans[j][(num >> k) % 2] = ++key;
-
memset(ans[key], 0, sizeof(ans[key]));
-
}
-
j = ans[j][(num >> k) % 2];
-
}
-
}
-
if (flag)cout << "YES\n";
-
else cout << "NO\n";
-
}
-
return 0;
-
}
力扣 421. 数组中两个数的最大异或值
题目：
给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。
找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。
你能在O(n)的时间解决这个问题吗？
示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.
思路：
字典树
代码：
-
const int m = 3000000;
-
int ans[m][2], key;
-
-
int f(int x)
-
{
-
for (int i = 30, k = 0; i >= 0; i--)
-
{
-
if (ans[k][1 - (x >> i) % 2] == 0)
-
{
-
k = ans[k][(x >> i) % 2];
-
if ((x >> i) % 2)x ^= (1 << i);
-
}
-
else
-
{
-
k = ans[k][1 - (x >> i) % 2];
-
if ((x >> i) % 2 == 0)x ^= (1 << i);
-
}
-
}
-
return x;
-
}
-
-
class Solution {
-
public:
-
int findMaximumXOR(vector<int>& nums) {
-
int n=nums.size(), m, r = INT_MIN;
-
memset(ans[0], 0, sizeof(ans[0]));
-
key = 0;
-
for (int i = 0; i < n; i++)
-
{
-
m = nums[i];
-
if (f(m) > r)r = f(m);
-
for (int k = 30, j = 0; k >= 0; k--)
-
{
-
if (ans[j][(m >> k) % 2] == 0)
-
{
-
ans[j][(m >> k) % 2] = ++key;
-
memset(ans[key], 0, sizeof(ans[key]));
-
}
-
j = ans[j][(m >> k) % 2];
-
}
-
}
-
return r;
-
}
-
};
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/115260905
- 点赞
- 收藏
- 关注作者
评论（0）