acwing 143. 最大异或对
标签：范围 review size stdin div 要求 += ssi 图片
今回是Jill镇楼，
今天题目还是感觉很有意思的，我推荐大家都做，做对了就做爽了（
题干：
在给定的 NN 个整数 A1，A2……ANA1，A2……AN 中选出两个进行 xorxor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 NN。
第二行输入 NN 个整数 A1A1～ANAN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1051≤N≤105,
0≤Ai2310≤Ai
输入样例：
3
1 2 3
输出样例：
3
暴力我们就不解释了，一个个对比是O（n^2），复杂度爆了。
我们看题目要求异或值，自然会想到二进制。
假设我们有一个图，图上有所有给出数的二进制表示，
我们如何给出关于一个数的最大异或值？
我们只要找每一个对应二进制位数尽量相反（位数从高到低选取），就能保证有最大异或值。
如果我们找n个数的任意两个数最大的异或值，最坏只有O（n*32）;
自然会想到只有零一的左右儿子的二叉树，我们一建树，一看题目，空间爆了（
我们然后就会想到用字典数的建树方法来建这个只有零一的二叉树。
结果，代码如下啦：
#include
#include
#includeconst int maxn = 1e5 + 10;
int bit[33 * maxn][2], n, k, a[maxn], t[35];
inline int max(int a, int b)
{return a > b ? a : b;}
void into(int x)
{
int p = 1,pos=0,i=0,tp=x;
memset(t, 0, sizeof t);
while (x)
{
t[p] = x % 2;
x = x / 2;
++p;
}
for (i = 32; i; --i)
{
if(!bit[pos][t[i]])
bit[pos][t[i]] = ++k;
pos = bit[pos][t[i]];
}
}
int find(int x)
{
int pos = 0, maxx = 0, ans[35] = { 0 }, p = 1, v = 0;
memset(t, 0, sizeof t);
while (x)
{
t[p] = x % 2;
x = x / 2;
++p;
}
for (int i = 32; i; --i)
{
if (bit[pos][!t[i]])ans[i] = 1, v = !t[i];
else ans[i] = 0, v = t[i];
pos = bit[pos][v];
}
for (int i = 32; i; --i)
maxx += ans[i] * pow(2, i - 1);
return maxx;
}
int main()
{
int ans = 0;
freopen("C:\\Users\\Towetrlone\\Desktop\\qwq.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i i)
scanf("%d", &a[i]),into(a[i]);
for (int i = 1; i i)
ans = max(ans, find(a[i]));
printf("%d", ans);
return 0;
}
acwing 143. 最大异或对
标签：范围 review size stdin div 要求 += ssi 图片
原文地址：https://www.cnblogs.com/Inabameguru/p/14947713.html
评论