题意:给你一个数组长度为n的a数组,要求a数组的值为非负整数,再给你一个k,a的值全小于2的k次方,找到一个小于a的k次方的值x,再从a中找到两个值,让他们 (ai⊕x)&(aj⊕x)最小
结论:n个数的最小异或对的答案就是排序后最小的相邻异或和
思路:(ai⊕x)&(aj⊕x)的最高位为1,可以把它先转换成二进制
例如:
0010 2
0100 4
0100 4
0100 4
0101 5
0110 6
1001 9
1010 10
1110 14
我们知道异或是相同为0,不同为1,与是有0为0,所以我们要先让(ai⊕x)和(aj⊕x)位数尽可能为1,而(ai⊕aj)为1的位数我们是没有办法改变的,(ai⊕aj)为1则(ai⊕x)&(aj⊕x)为0,所以我们要找最小的异或对,这个时候就用到上面的结论了,然后找到异或对后就是构造x,x就是i,j的同一位数全为0则x这一位为1,否则为0
点击查看代码
const int N = 1e6 + 10;
int n,m,k;
struct now{
int u;
int v;
}a[N];
bool cmp(now ll,now rr)
{
if(ll.u == rr.u)
return ll.v < rr.v;
return ll.u < rr.u;
}
void solve()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
{
cin >> a[i].u;
a[i].v = i;
}
sort(a+1,a+n+1,cmp);
int l = 0,r = 0,num = 1e18;
for(int i = 2;i <= n;i ++)//找最小异或对
{
int w = a[i].u ^ a[i-1].u;
if(w < num)
{
num = w;
l = i-1;
r = i;
}
}
int cnt = 1,ans = 0;
for(int i = 0;i < m;i ++)//二进制枚举位数,比对该位是否为相同为0
{
cnt = 1 << i;
int xx = a[l].u&cnt;
int yy = a[r].u&cnt;
if(xx==0&&yy==0)
{
ans += cnt;
}
}
cout << a[l].v << ' ' << a[r].v << ' ' << ans << '\n';
}