CodeForces1285D - Dr. Evil Underscores

传送门：CodeForces - 1285D

题目描述

Today, as a friendship gift, Bakry gave Badawy n integers $a_1,a_2,…,a_n$ and challenged him to choose an integer $X$ such that the value Max{a_1⊕X,a_2⊕X,…a_n⊕X} is minimum possible

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of Max{$a_1⊕X,a_2⊕X,…a_n⊕X$}

输入描述

The first line contains integer n $(1≤n≤10^5)$.

The second line contains n integers a1,a2,…,an $(0≤a_i≤2^{30−1})$.

输出描述

Print one integer — the minimum possible value of Max{$a_1⊕X,a_2⊕X,…a_n⊕X$}

思路分析

有n个数，寻找一个$X$使得Max{$a_1⊕X,a_2⊕X,…a_n⊕X$}最小，并输出。
这道题可以通过贪心来取最小值，对于第$i$位，如果该位只有1或0，那么Ans的这一位取0，如果0和1都存在，那么这一位肯定取1。
所以我们可以建出Trie树，从树的最高位开始贪心，如果有0有1则对两个子树取Min并加上$2^i$，否则直接对子树进行操作。

样例输入

3
1 2 3

样例输出

2

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;

int dfs(vi a,int dep){
    if(a.size()==0||dep<0)
        return 0;
    vi q1,q2;
    for(auto i:a){
        if((i>>dep)&1) q1.pb(i);
        else q2.pb(i);
    }
    if(q1.size()==0) 
        return dfs(q2,dep-1);
    if(q2.size()==0)
        return dfs(q1,dep-1);
    return min(dfs(q1,dep-1),dfs(q2,dep-1))+(1<<dep);
}
 
int main() {
    IOS;
    vi a;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.pb(x);
    }
    cout<<dfs(a,30)<<endl;
 
    return 0;
}