Codeforces 1447E. Xor Tree（字典树/贪心）_codefores e. xor tree

Codeforces Round #683 (Div. 2, by Meet IT) 全文见：https://blog.csdn.net/qq_43461168/article/details/113175011

E. Xor Tree

题意：

一个数组。每个元素会和与自己异或值最小的数连一条无向边。想要最终形成的图是一颗树。 至少要删掉几个元素。

思路：

首先肯定不会形成环。

为什么呢。因为一个值，只会和一个异或起来最小的值相连。要形成环。就说明至少要有一个元素。同时连向两个元素。这显然不符合条件。环中边的数量等于点的数量。但是题目的条件中。必然至少存在一对。两两异或互为最小的。也就减少了一条边。所以不可能形成环。

既然不会形成环，还有一种不是树的情况。就是形成了森林。或者说多个连通块。比如数组中 a-b 异或起来互为最小。 c-d异或起来互为最小。这时候就必须要删点了。

具体怎么删。考虑贪心。

建一颗01字典树。那么和自己异或以来最小的数。一定是同一颗子树上的，公共前缀越长越好啊，这样高位都是0。低位才会出现1。

然后就会发现，如果，一个点的左右两颗子树。都存在超过两个叶节点。那么完了。左子树的点互相连接形成连通块。右子树的点互相连接形成连通块。而左右子树 不会连边，也就是不连通。那就不可能形成树了。

所以这时候必须抉择。其中一颗子树。最多只能有一个叶子节点。其他的得删掉，那因为要贪心的考虑。肯定是选择，叶子数量大的那一颗留下来。小的那一颗删到剩下一个点就行了。

递归处理整颗树。就完成了。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 5e6+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N],c[N];
int tot=0;
int tree[N][2];
int sz[N];

void insert(int x){
    int pos = 0;
    for(int i = 30 ; i >= 0; i --){
        int now = (x>>i)&1;
        if(!tree[pos][now]) tree[pos][now] = ++tot;
        pos = tree[pos][now];
        sz[pos] ++;
    }
}

int dfs(int pos,int dep){
    if(!tree[pos][0] && !tree[pos][1]){
        return 1;
    }
    int l = 0 ,r = 0;
    if(tree[pos][0]) l = dfs(tree[pos][0],dep+1);
    if(tree[pos][1]) r = dfs(tree[pos][1],dep+1);
    if(l&&r) return max(l,r)+1;
    else return l+r;
}


signed main(){
    //cin>>t;
    while(t--){
        cin>>n;
        for(int i = 0 ; i < n ; i ++){
            cin>>a[i];
            insert(a[i]);
        }
        cout<<n-dfs(1,0)<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50