DDOSvoid's Blog

The 14th Chinese Northeast Collegiate Programming Contest A Micro Structure Thread

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/gym/102801/problem/A

简要题意：给定一个长度为 $n$ 的序列 $a_i$，$a_i$ 互不相同，定义两个点 $(x,y)$ 的距离为 $popcount(a_x,a_y)$，求最小生成树

$n\le 2\times 10^5,a_i< 2^{18}$

Solution

我们考虑建一张有 $2^{18},[0,2^{18}-1]$ 个点的图，点 $u$ 的出边为 $u\oplus 2^{i},i\in[0,17]$，我们令 $a_i$ 为关键点，然后进行多源点 $bfs$，对于每个点 $u$，我们记录离它最近的关键点 $id_u$，然后对于每个与它相连的点 $v$，我们记录一条连接 $(id_u,id_v)$ 的边，然后拿这些边跑 $kruskal$ 即可，注意到这样一定是正确的，因为如果有若干个关键在某个非关键点进行合并的话，离这个非关键点最近的那个点一定会参与合并，所以我们只记录它就行了

时间复杂度 $O(18n\log (18n))$

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define maxn 200010
#define ll long long
using namespace std;

int n, a[maxn];

struct Edge {
    int fr, to, w;

    friend bool operator < (const Edge &u, const Edge &v) { return u.w < v.w; } 
}; vector<Edge> E;

int id[1 << 18];
void bfs() {
    queue<int> Q; fill(id, id + (1 << 18), 0); 
    for (int i = 1; i <= n; ++i) id[a[i]] = i, Q.push(a[i]);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int o = 0; o < 18; ++o) {
            int v = u ^ 1 << o;
            if (!id[v]) id[v] = id[u], Q.push(v);
            else if (id[u] != id[v]) E.push_back({ id[u], id[v], __builtin_popcount(a[id[u]] ^ a[id[v]]) });
        }
    }
}

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return 0;
    fa[fx] = fy; return 1; 
}

vector<int> G[maxn];
vector<pair<int, int>> ans;
void dfs(int u, int fa) {
    ans.emplace_back(u, fa ? fa : n);
    for (auto v : G[u]) { 
        if (v == fa) continue;
        dfs(v, u);
    }
}

void work() { 
    cin >> n; E.clear(); ans.clear();
    for (int i = 1; i <= n; ++i) G[i].clear();
    for (int i = 1; i <= n; ++i) cin >> a[i];
    bfs(); sort(E.begin(), E.end()); init_fa(n); int mst = 0; 
    for (auto [u, v, w] : E) 
        if (merge(u, v)) {
            mst += w;
            G[u].push_back(v); G[v].push_back(u);
        }
    dfs(1, 0); cout << mst << "\n";
    for (auto [fi, se] : ans) cout << fi << " "; cout << "\n";
    for (auto [fi, se] : ans) cout << se << " "; cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}