Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF888G Xor-MST

Posted on

Trie+生成树。

Solution

感觉挺妙的。

首先我们考虑怎样合并最小，可以发现，当我们将这些节点建成$Trie$树时，最优的方案一定是每次合并$Trie$树的两个子树最优，为什么呢，画张图之后就可以发现只有$n- 1$个节点有两个儿子，而对于每一个叶子节点，想要合并到联通块之中的话最优一定是在两两的$lca$处合并，所以我们对于每一个存在两个儿子的$Trie$树，从它的两个子树中分别找一个节点，使他们的异或和最小（启发式即可），依次合并即可。

一个卡常小技巧：将节点排序之后插入$Trie$树，这样$Trie$树中节点编号更加连续，常数更小。

Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); }
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
inline void out(T res)
{
    if(res < 0) putchar('-'), res = -res;
    if(res > 10) out(res / 10);
    putchar(res % 10 + '0'); 
}
template <class T>
inline void write(T res)
{
    out(res), putchar('\n');
}
const int N = 2e5 + 5;
const LL Inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
int ch[N * 31][2], tot = 1, l[N * 31], r[N * 31];
inline void insert(int x, int id)
{
    int root = 1;
    l[1] = 1, r[1] = n;
    for(int i = 30, op;i >= 0;i --)
    {
        op = (x >> i) & 1;
        if(ch[root][op]) root = ch[root][op];
        else ch[root][op] = ++ tot, root = tot;
        if(!l[root]) l[root] = id;
        r[root] = id;
    }
}
LL query(int x, int k, int depth)
{
    if(depth < 0) return 0;
    int op = (k >> depth) & 1;
    if(ch[x][op]) return query(ch[x][op], k, depth - 1);
    return query(ch[x][op ^ 1], k, depth - 1) + (1 << depth);
}
LL dfs(int x, int depth)
{
    if(depth < 0) return 0;
    if(ch[x][0] && ch[x][1])
    {
        LL ans = Inf;
        if(r[ch[x][0]] - l[ch[x][0]] <= r[ch[x][1]] - l[ch[x][1]])
        {
            for(int i = l[ch[x][0]];i <= r[ch[x][0]];i ++)
                ans = min(ans, query(ch[x][1], a[i], depth - 1) + (1 << depth));
        }
        else {
            for(int i = l[ch[x][1]];i <= r[ch[x][1]];i ++)
                ans = min(ans, query(ch[x][0], a[i], depth - 1) + (1 << depth));
        }
        return dfs(ch[x][0], depth - 1) + dfs(ch[x][1], depth - 1) + ans;
    }
    if(ch[x][0]) return dfs(ch[x][0], depth - 1);
    if(ch[x][1]) return dfs(ch[x][1], depth - 1);
    return 0;
}
int main()
{
    read(n);
    for(int i = 1;i <= n;i ++) read(a[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1;i <= n;i ++) insert(a[i], i);
    write(dfs(1, 30));
    return 0;
}