codeforces 1851F

题目链接

题目大意：给你一个长度为n的数组a, 和一个整数k(2<=n<=2e5, k<=30, a[i]<=pow(2,k))。
任选一个x，求(a[i] ^ x) & (a[j] ^ x) 的最大值(1<=i,j<=n, i!=j, x<=pow(2,k))。

由于中间有个&，所以我们要求两个数最高位尽量相等，所以a[i]和a[j]的最高位也要尽量相等，
然后可以通过x的构造最大值，可以想到我们肯定想让结果的最高位为1，
那么x与另外两个数的高位就要不同，但是可以想到当a[i]和a[j]某一位不同时，x这位的取值就不重要了。
要求a[i]和a[j]尽量相等的结果，可以转化为求最小异或和问题。
最小异或和只需要排个序即可。 

void solve() {int n, k;cin >> n >> k;vector<int> a(n), p(n);for (int i = 0; i < n; i++) {cin >> a[i];p[i] = i;}sort(p.begin(), p.end(), [&](int i, int j) {return a[i] < a[j];});int i = -1, j = -1, x = -1;int ans = 1 << k;for (int t = 1; t < n; t++) {if(ans > (a[p[t]] ^ a[p[t - 1]])) {ans = a[p[t]] ^ a[p[t - 1]];i = p[t] + 1;j = p[t - 1] + 1;x = ((1 << k) - 1) ^ (a[p[t]] | a[p[t - 1]]);}}cout << i << ' ' << j << ' ' << x << "\n";
}