DDOSvoid's Blog

The 2020 ICPC Asia Macau Regional Contest C Club Assignment

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

题目描述

https://codeforces.com/gym/103119/problem/C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在要将每个数划分到两个集合，一个几何的权值为集合内的所有数，两两之间的异或和的最小值，现在要求一种分法，使得两个点集的权值的最小值最大

$n\le 10^5$

Solution

首先考虑一个比较套路的做法，根据 Luogu P1525 [NOIP2010 提高组] 关押罪犯(最小生成树)，容易得到我们只需要求一个最小生成树，然后用 $01Trie$ 求一个最小值即可，求异或最小生成树是一个经典的做法，时间复杂度 $O(n\log^2 n)$

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
#include <iostream>
#include <vector>
#define maxn 100010
#define INF (1 << 30)
using namespace std;

const int N = 30;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct Trie {
    int v, ch[2]; 
} T[maxn * 30]; int rt, top;
void init_Trie() {
    for (int i = 1; i <= top; ++i) lc = rc = T[i].v = 0; 
    rt = top = 1; 
}

void ins(int &i, int k, int o, int v) {
    if (!i) i = ++top; 
    if (o == -1) return T[i].v = v, void(); 
    ins(T[i].ch[k >> o & 1], k, o - 1, v);
}

int query(int i, int k, int o) {
    if (o == -1) return T[i].v; int d = k >> o & 1;
    if (T[i].ch[d]) return query(T[i].ch[d], k, o - 1);
    else return query(T[i].ch[d ^ 1], k, o - 1); 
}

int n, w[maxn];
struct node {
    int v, id;
} a[maxn], t1[maxn], t2[maxn];

vector<int> G[maxn];
void solve(int l, int r, int o) {
    if (o == -1) {
        for (int i = l + 1; i <= r; ++i) {
            G[a[l].id].push_back(a[i].id);
            G[a[i].id].push_back(a[l].id); 
        }
        return ;
    }
    int c1 = 0, c2 = 0, m = l + r >> 1, v = INF, x, y; 
    for (int i = l; i <= r; ++i)
        if (a[i].v >> o & 1) t1[++c1] = a[i];
        else t2[++c2] = a[i];
    init_Trie();
    if (!c1 || !c2) return solve(l, r, o - 1), void();
    for (int i = 1; i <= c1; ++i) ins(rt, t1[i].v, N, t1[i].id);
    for (int i = 1; i <= c2; ++i) {
        int t = query(rt, t2[i].v, N); 
        if ((t2[i].v ^ w[t]) < v) x = t2[i].id, y = t, v = t2[i].v ^ w[t];
    } G[x].push_back(y); G[y].push_back(x); 
    for (int i = 1; i <= c1; ++i) a[l + i - 1] = t1[i];
    for (int i = 1; i <= c2; ++i) a[l + c1 + i - 1] = t2[i];
    solve(l, l + c1 - 1, o - 1); solve(l + c1, r, o - 1); 
}

int dep[maxn];
void dfs(int u, int fa) {
    for (auto v : G[u])
        if (v != fa) dep[v] = dep[u] + 1, dfs(v, u); 
}

void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i) G[i].clear(); 
    for (int i = 1; i <= n; ++i) cin >> w[i], a[i] = { w[i], i };
    solve(1, n, N); dep[1] = 1; dfs(1, 0); int ans = INF;

    init_Trie(); 
    for (int i = 1; i <= n; ++i) {
        if (dep[i] % 2 == 0) continue;
        if (top > 1) ans = min(ans, w[i] ^ w[query(rt, w[i], N)]);
        ins(rt, w[i], N, i);
    }

    init_Trie();
    for (int i = 1; i <= n; ++i) {
        if (dep[i] & 1) continue; 
        if (top > 1) ans = min(ans, w[i] ^ w[query(rt, w[i], N)]);
        ins(rt, w[i], N, i); 
    }

    cout << ans << "\n";
    for (int i = 1; i <= n; ++i) cout << (dep[i] % 2 == 0 ? 1 : 2); cout << "\n";
}

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

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

现在我们仿照求异或最小生成树的做法，按位分治

我们考虑现在在考虑第 $k$ 位，令第 $k$ 位为 $1$ 的个数为 $a$，第 $k$ 位为 $0$ 的个数为 $b$

注意到如果 $a$ 和 $b$ 都小于等于 $2$，那么我们可以通过分组来避免最小值小于 $2^k$

否则，最小值一定不含第 $k$ 位，且一定由左边和右边组成，所以可以直接递归

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

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
#include <iostream>
#define maxn 100010
#define INF (1 << 30)
using namespace std;

int n, m;

struct node {
    int v, id;
} a[maxn], t1[maxn], t2[maxn];

const int N = 30;
int ans[maxn];
int solve(int l, int r, int o) {
    if (o == -1) {
        for (int i = l; i <= r; ++i) ans[a[i].id] = 1;
        return 0;
    } int c1 = 0, c2 = 0;
    for (int i = l; i <= r; ++i)
        if (a[i].v >> o & 1) t1[++c1] = a[i];
        else t2[++c2] = a[i];
    if (r - l + 1 <= 2) {
        ans[a[l].id] = 1;
        if (r > l) ans[a[r].id] = 2;
        return INF;
    }
    if (!c1 || !c2) return solve(l, r, o - 1);
    if (c1 <= 2 && c2 <= 2) {
        int v = INF, x, y, res = INF;
        for (int i = 1; i <= c1; ++i)
            for (int j = 1; j <= c2; ++j)
                if ((t1[i].v ^ t2[j].v) < v) x = i, y = j, v = (t1[i].v ^ t2[j].v);
        ans[t1[x].id] = 1; ans[t2[y].id] = 2;
        if (c1 > 1) ans[t1[2 - x + 1].id] = 2, res = min(res, t1[2 - x + 1].v ^ t2[y].v);
        if (c2 > 1) ans[t2[2 - y + 1].id] = 1, res = min(res, t2[2 - y + 1].v ^ t1[x].v); 
        return res;
    }
    for (int i = 1; i <= c1; ++i) a[l + i - 1] = t1[i];
    for (int i = 1; i <= c2; ++i) a[l + c1 + i - 1] = t2[i];
    return min(solve(l, l + c1 - 1, o - 1), solve(l + c1, r, o - 1)); 
}

void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].v, a[i].id = i;
    cout << solve(1, n, N) << "\n";
    for (int i = 1; i <= n; ++i) cout << ans[i]; cout << "\n";
}

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

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