Dr. Evil Underscores

​​D - Dr. Evil Underscores​​

參考：​​Codeforces Round #613 (Div. 2) Editorial​​

其實比賽的時候就已經想到了基本上一樣的解法，可是最後還是沒有寫出來...

具體思路就是分治，在二進制中，如果\(a_1{\sim}a_n\)，在該位上既有1又有0，說明這一位上的數是躲不掉的，那麼這一位上肯定是1，是以在傳回的數裡加一個​

​1<<i​

​​，而對于後面的數則取最小值即可​

​min(dfs(i-1, v0), dfs(i-1, v1))+(1 << i)​

​

要注意的一點：i 要一直算到​

​i<0​

​​才結束，因為當​

​i==0​

​是運算的是最後一位的值。

代碼：

// Created by CAD on 2020/1/10.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll a[maxn];

int dfs(int i,vector<int> &v)
{
    vector<int> v0,v1;
    if(i<0)    return 0;
    for(auto &j:v)
    {
        if((j>>i)&1) v1.push_back(j);
        else v0.push_back(j);
    }
    if(v0.size()==0) return dfs(i-1, v1);
    if(v1.size()==0) return dfs(i-1, v0);
    return min(dfs(i-1, v0), dfs(i-1, v1))+(1 << i);
}
vector<int> v;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //    FOPEN;
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i],v.push_back(a[i]);
    cout << dfs(30, v) << endl;
    return 0;
}