Codeforces gym103119C 最小异或生成树

题意

传送门 Codeforces gym103119C Club Assignment

题解

将边权按照权值从小到大依次考虑，尽量使边的端点划分至不同的集合，类似于并查集处理分类问题的过程，当第一次出现无法将端点划分至不同集合时，当前边权即答案。这样处理 $O(n^2\log n)$。

将 $(u,v)$ 划分为两个集合，则连边 $(u,v)$，此时最小生成树上二分图染色得到的两个集合即是目标集合。最小异或生成树可以通过按照数位从高到低分治求解，总时间复杂度 $O(n{\log }^{2}w)$。

    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    constexpr int MAXN = 1E5 + 5, MAXLG = 30, INF = 0x3f3f3f3f;
    int T, N, W[MAXN];

    struct Trie
    {
        int rt, n, ch[MAXN * MAXLG][2], ed[MAXN * MAXLG];
        int build()
        {
            ch[n][0] = ch[n][1] = -1;
            return n++;
        }
        void init() { n = 0, rt = build(); }
        void insert(int x, int k)
        {
            int p = rt;
            for (int i = MAXLG - 1; i >= 0; --i)
            {
                int c = x >> i & 1;
                if (ch[p][c] == -1)
                    ch[p][c] = build();
                p = ch[p][c];
            }
            ed[p] = k;
        }
        int ask(int x)
        {
            int p = rt;
            for (int i = MAXLG - 1; i >= 0; --i)
            {
                int c = x >> i & 1;
                p = ch[p][c] == -1 ? ch[p][c ^ 1] : ch[p][c];
            }
            return ed[p];
        }
    } tr;
    vector<int> G[MAXN];

    void add_edge(int u, int v) { G[u].push_back(v), G[v].push_back(u); }

    void solve(int k, vector<int> &a)
    {
        if (a.size() == 0)
            return;
        if (k < 0)
        {
            for (int i = 1; i < a.size(); ++i)
                add_edge(a[0], a[i]);
            return;
        }
        vector<int> b, c;
        for (int i : a)
            if (W[i] >> k & 1)
                b.push_back(i);
            else
                c.push_back(i);
        solve(k - 1, b), solve(k - 1, c);
        if (b.size() == 0 || c.size() == 0)
            return;
        tr.init();
        for (int i : b)
            tr.insert(W[i], i);
        int u = -1, v = -1, mn = INF;
        for (int i : c)
        {
            int j = tr.ask(W[i]), t = W[i] ^ W[j];
            if (t < mn)
                mn = t, u = i, v = j;
        }
        add_edge(u, v);
    }

    int col[MAXN];

    void color(int v, int c)
    {
        col[v] = c;
        for (int u : G[v])
            if (col[u] == -1)
                color(u, c ^ 1);
    }

    void count(int c, int &res)
    {
        tr.init();
        bool fst = 0;
        for (int i = 0; i < N; ++i)
            if (col[i] == c)
            {
                if (fst)
                {
                    int j = tr.ask(W[i]);
                    res = min(res, W[i] ^ W[j]);
                }
                tr.insert(W[i], i);
                fst = 1;
            }
    }

    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin >> T;
        while (T--)
        {
            cin >> N;
            for (int i = 0; i < N; ++i)
                cin >> W[i];
            for (int i = 0; i < N; ++i)
                G[i].clear();
            vector<int> a(N);
            for (int i = 0; i < N; ++i)
                a[i] = i;
            solve(MAXLG - 1, a);
            memset(col, -1, sizeof(col));
            color(0, 0);
            int res = INF;
            count(0, res), count(1, res);
            cout << res << '\n';
            for (int i = 0; i < N; ++i)
                cout << col[i] + 1;
            cout << '\n';
        }
        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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127