Dr. Evil Underscores

Created by LXC on Sun Jul 9 14:12:21 2023

https://codeforces.com/problemset/problem/1285/D

ranting: 1900

tag: bitmasks, brute force, dfs and similar, divide and conquer, dp, greedy, strings, trees

problem

给出$a_1, a_2, \dots, a_n$共计n个数，$(0 \le a_i \le 2^{30}-1)$。

请选择一个X，使得$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$最小化。

请输出最小的$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$

solution

先看所有数的最高位，如果既有1又有0，那么答案的最高位必定是1；否则必为0。

我们将最高位按照1和0分为两组，进一步判断次高位。我们发现每个问题可以最多划分成两个子问题，子问题不重叠，可以直接递归分而治之。

每递归一层可以构造一位答案，当递归了30层后便可得到一个答案。取所有构造答案的最小值即可。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 100005
#define MOD 998244353
using namespace std;

int a[N];
int ans = (1 << 30) - 1;

void dfs(int lev, int l, int r, int num) {
    // cout << lev << ' ' << l << ' ' << r << ' ' << num << endl;
    if (lev == -1) {
        ans = min(ans, num);
        return;
    }
    if ((a[l] >> lev & 1) != (a[r] >> lev & 1)) {
        int p = l;
        while ((a[p] >> lev & 1) == (a[l] >> lev & 1))
            p++;
        dfs(lev - 1, l, p - 1, num << 1 | 1);
        dfs(lev - 1, p, r, num << 1 | 1);
    } else {
        dfs(lev - 1, l, r, num << 1);
    }
}

void sol() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    dfs(29, 0, n - 1, 0);
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}