码创造者

这个屌丝很懒，什么也没留下！

热门标签

蓝桥杯 2024 年第十五届省赛真题 —— 最大异或结点

作者：码创造者 | 2024-07-29 08:57:37

踩

1. 最大异或结点

1. 问题描述

小蓝有一棵树,树中包含 $N$ 个结点，编号为 $0,1,2,\cdots, N - 1$ ，其中每个结点上都有一个整数 $X_{i}$ 。他可以从树中任意选择两个不直接相连的结点 $a\text{、}b$ 并获得分数 $X_{a} \oplus X_{b}$ ，其中 $\oplus$ 表示按位异或操作。

请问小蓝可以获得的最大分数是多少?

2. 输入格式

输入的第一行包含一个整数 $N$ ，表示有 $N$ 个结点。

第二行包含 $N$ 个整数 $X_{1},X_{2},\cdots ,X_{N}$ ，相邻整数之间使用一个空格分隔。

第三行包含 $N$ 个整数 $F_{1},F_{2},\cdots,F_{N}$ ，相邻整数之间使用一个空格分隔，其中第 $i$ 个整数表示 $i$ 的父结点编号， $F_{i} = - 1$ 表示结点 $i$ 没有父结点。

3. 输出格式

输出一行包含一个整数表示答案。

4. 样例输入

5. 样例输出

7
1

6. 样例说明

选择编号为 $3$ 和 $4$ 的结点， $x_{3} = 3,x_{4} = 4$ ，他们的值异或后的结果为 $\oplus 4 = 7$ 。

7. 评测用例规模与约定

对于 ${50}\%$ 的评测用例， $\leq N \leq {1000}$ ；

对于所有评测用例， $\leq N \leq 10^{5},0 \leq X_{i} \leq 2^{31} - 1, - 1 \leq F_{i} \leq N,F_{i} \neq 0$ 。

2. 解题思路

1. 解题思路

暴力做法

直接枚举所有可能选择的组合，即枚举选择的 $a$ 和 $b$ 。同时需要判断 $a$ 和 $b$ 是否为相邻节点，可以使用哈希表进行判断。对于所有可能的合法组合，计算异或值并取最大的异或值作为答案。

枚举的复杂度为 $O(n^2)$ ，判断相邻的复杂度为 $O(\log n)$ ，整体复杂度为 $O(n^2 \log n)$ ，无法通过本题。

满分做法

考虑优化。对于需要选择两个元素 $a$ 和 $b$ 的题目，常见的套路是枚举 $a$ ，并从剩余元素中选择最优元素作为 $b$ 。在本题中，当 $a$ 确定时，我们需要从剩余元素中找到最优元素 $b$ 使得 $X_a \oplus X_b$ 最大，这实际上是一个 $01$ 字典树的典型应用。如果你对 $01$ 字典树还不太熟悉，可以通过 01字典树学习。

问题在于，当我们枚举 $a$ 时，字典树中不能包含 $a$ 的相邻元素。如何去除相邻元素的干扰？

一个直观的想法是当我们枚举到 $a$ 时，先将字典树中所有 $a$ 的相邻元素删除，在进行查询后再将所有相邻元素插回字典树。

思考：这样操作的复杂度是否可行？

显然是可行的。因为本题给定的是一棵树，对于每条边而言，假设其两端的点为 $x$ 和 $y$ ，当我们枚举 $a = x$ 时， $y$ 会产生一次删除和插入；枚举到 $a = y$ 时， $x$ 会产生一次删除和插入。由于一棵树只有 $n - 1$ 条边，总共产生的删除和插入操作为 $\times (n - 1)$ 次。忽略常数，这部分复杂度视为 $O (n)$ 。

考虑到字典树每次插入、删除、查询的复杂度均为 $O(\log V)$ ，其中 $V$ 表示值域的最大值，整体复杂度为 $\log V)$ ，可以通过本题。

2. AC_Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(s) ((int)s.size())

class Node {
public:
    array<Node *, 2> children{};
    int cnt = 0;
};

class Trie {
    static const int HIGH_BIT = 31;
public:
    Node *root = new Node();

    void insert(ll val) {
        Node *cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (cur->children[bit] == nullptr) {
                cur->children[bit] = new Node();
            }
            cur = cur->children[bit];
            cur->cnt++;
        }
    }

    void remove(ll val) {
        Node *cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            cur = cur->children[(val >> i) & 1];
            cur->cnt--;
        }
    }

    int max_xor(ll val) {
        Node *cur = root;
        int ans = 0;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (cur->children[bit ^ 1] && cur->children[bit ^ 1]->cnt) {
                ans |= 1 << i;
                bit ^= 1;
            }
            cur = cur->children[bit];
        }
        return ans;
    }

    int min_xor(ll val) {
        Node *cur = root;
        int ans = 0;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (cur->children[bit] && cur->children[bit]->cnt) {
                cur = cur->children[bit];
            } else {
                ans |= 1 << i;
                cur = cur->children[bit ^ 1];
            }
        }
        return ans;
    }
};
void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    Trie tr{};
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        tr.insert(a[i]);
    }

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; ++i) {
        int f;
        cin >> f;
        if (f != -1) {
            adj[i].push_back(f);
            adj[f].push_back(i);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (auto v : adj[i]) {
            tr.remove(a[v]);
        }
        ans = max(ans, tr.max_xor(a[i]));
        for (auto v : adj[i]) {
            tr.insert(a[v]);
        }
    }

    cout << ans << '\n';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(10);

    int t = 1;
    while (t--) {
        solve();
    }

    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

Java

import java.util.*;

class Node {
    Node[] children = new Node[2];
    int cnt = 0;
}

class Trie {
    private static final int HIGH_BIT = 31;
    Node root = new Node();

    void insert(long val) {
        Node cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (int) ((val >> i) & 1);
            if (cur.children[bit] == null) {
                cur.children[bit] = new Node();
            }
            cur = cur.children[bit];
            cur.cnt++;
        }
    }

    void remove(long val) {
        Node cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            cur = cur.children[(int) ((val >> i) & 1)];
            cur.cnt--;
        }
    }

    int maxXor(long val) {
        Node cur = root;
        int ans = 0;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (int) ((val >> i) & 1);
            if (cur.children[bit ^ 1] != null && cur.children[bit ^ 1].cnt > 0) {
                ans |= 1 << i;
                bit ^= 1;
            }
            cur = cur.children[bit];
        }
        return ans;
    }

    int minXor(long val) {
        Node cur = root;
        int ans = 0;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (int) ((val >> i) & 1);
            if (cur.children[bit] != null && cur.children[bit].cnt > 0) {
                cur = cur.children[bit];
            } else {
                ans |= 1 << i;
                cur = cur.children[bit ^ 1];
            }
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] a = new int[n];
        Trie tr = new Trie();

        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
            tr.insert(a[i]);
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; ++i) {
            int f = sc.nextInt();
            if (f != -1) {
                adj.get(i).add(f);
                adj.get(f).add(i);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int v : adj.get(i)) {
                tr.remove(a[v]);
            }
            ans = Math.max(ans, tr.maxXor(a[i]));
            for (int v : adj.get(i)) {
                tr.insert(a[v]);
            }
        }

        System.out.println(ans);
    }
}

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

Python

class Node:
    def __init__(self):
        self.children = [None, None]
        self.cnt = 0

class Trie:
    HIGH_BIT = 31

    def __init__(self):
        self.root = Node()

    def insert(self, val):
        cur = self.root
        for i in range(self.HIGH_BIT, -1, -1):
            bit = (val >> i) & 1
            if cur.children[bit] is None:
                cur.children[bit] = Node()
            cur = cur.children[bit]
            cur.cnt += 1

    def remove(self, val):
        cur = self.root
        for i in range(self.HIGH_BIT, -1, -1):
            bit = (val >> i) & 1
            cur = cur.children[bit]
            cur.cnt -= 1

    def max_xor(self, val):
        cur = self.root
        ans = 0
        for i in range(self.HIGH_BIT, -1, -1):
            bit = (val >> i) & 1
            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt > 0:
                ans |= 1 << i
                bit ^= 1
            cur = cur.children[bit]
        return ans

    def min_xor(self, val):
        cur = self.root
        ans = 0
        for i in range(self.HIGH_BIT, -1, -1):
            bit = (val >> i) & 1
            if cur.children[bit] and cur.children[bit].cnt > 0:
                cur = cur.children[bit]
            else:
                ans |= 1 << i
                cur = cur.children[bit ^ 1]
        return ans

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    n = int(data[idx])
    idx += 1
    
    a = []
    tr = Trie()
    
    for i in range(n):
        a.append(int(data[idx]))
        tr.insert(a[-1])
        idx += 1
    
    adj = [[] for _ in range(n)]
    
    for i in range(n):
        f = int(data[idx])
        idx += 1
        if f != -1:
            adj[i].append(f)
            adj[f].append(i)
    
    ans = 0
    for i in range(n):
        for v in adj[i]:
            tr.remove(a[v])
        ans = max(ans, tr.max_xor(a[i]))
        for v in adj[i]:
            tr.insert(a[v])
    
    print(ans)

if __name__ == "__main__":
    solve()

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

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

蓝桥杯 2024 年第十五届省赛真题 —— 最大异或结点

目录

1. 最大异或结点

1. 问题描述

2. 输入格式

3. 输出格式

4. 样例输入

5. 样例输出

6. 样例说明

7. 评测用例规模与约定

2. 解题思路

1. 解题思路

2. AC_Code