Almost

题解 #

我们从最高位开始因为最高位对数的影响最大。我们需要把所有数分成两组，一组是当前位为 1 的数，另一组是当前位为 0 的数。如果其中一组是空的那么我们总是可以使这一位变成 0 然后到下一位。否则这一位总会有 1，那么我们就需要对那两组解决同样的问题来知道这位是填 1 还是 0，这很明显是个递归。设那两组的答案分别是 $ans_1$ 和 $ans_0$ ，当前在第 $i$ 位，那么答案就是 $2^i+\min(ans_1,ans_0)$ 。

Code #

#include <bits/stdc++.h>
 
using namespace std;
vector<int> a;
int dfs(vector<int> v,int idx){
    if(v.empty()) return 0;
    if(idx==-1) return 0;
    vector<int> a,b;
    for(auto it:v){
        if(it&(1<<idx)) a.pb(it);
        else b.pb(it);
    }
    if(a.empty()) return dfs(b,idx-1);
    if(b.empty()) return dfs(a,idx-1);
    return min(dfs(a,idx-1),dfs(b,idx-1))+(1<<idx);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
    cin>>n;
    a.resize(n);
    for(int& it:a) cin>>it;
    cout<<dfs(a,30);
    return 0;
}

Codeforces 1285D - Dr. Evil Underscores 题解

题解 #

Code #