题解
1.对于任意 \(a_i\) 和 \(a_j\) ,最大异或和是唯一的
2.对于 \(a_i\) 来说,要想异或和最大,则 \(a_j\) 要尽量满足每一位上的数相同,比如都是0,或者都是1,所以最优配对的 \(a_j\) 一定是大小最接近 \(a_i\) 的 \(a_j\) ,因为这样第一个不同的位最小
code
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,id;
}a[200005];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i].x;
a[i].id=i;
}
sort(a+1,a+1+n,[&](const node &b,const node &c){return b.x<c.x;});
int maxs=(1<<k)-1;
int mn=maxs;
for(int i=1;i<n;i++) mn=min(mn,(a[i].x^a[i+1].x));
for(int i=1;i<n;i++)
{
if(mn==(a[i].x^a[i+1].x))
{
cout<<a[i].id<<" "<<a[i+1].id<<" "<<maxs-(a[i].x&a[i+1].x)<<"\n";
break;
}
}
}
return 0;
}
标签:node,Martians,int,cin,异或,Lisa,id
From: https://www.cnblogs.com/pure4knowledge/p/18253424