「IXOI R3」我才不玩原神呢

形式化题目

给定序列 $a$ ，从中选择恰好 $k$ 个元素。设所选元素最大值为 $m$ ，最大化 $\sum(a_i\mathbin{\mathrm{xor}}m)$ 。

暴力解法

思路

递归枚举所有长度为 $k$ 的下标组合。生成完整组合后求出最大值 $m$ ，再计算 $\sum(a_i\mathbin{\mathrm{xor}}m)$ 并更新答案。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 19:06
 * update_at: 2026-09-06 19:22
 */
// brute.cpp：小数据暴力解，枚举长度为 k 的选择序列，用来辅助对拍。
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[20];
int chosen[20];
long long answer = 0;

void dfs(int pos, int count) {
    if (count == k) {
        int maximum = 0;
        for (int i = 0; i < k; i++) {
            maximum = max(maximum, chosen[i]);
        }
        long long value = 0;
        for (int i = 0; i < k; i++) {
            value += (chosen[i] ^ maximum);
        }
        answer = max(answer, value);
        return;
    }
    if (n - pos < k - count) {
        return;
    }
    for (int i = pos; i < n; i++) {
        chosen[count] = a[i];
        dfs(i + 1, count + 1);
    }
}

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

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dfs(0, 0);
    cout << answer << '\n';
    return 0;
}

复杂度与瓶颈

共有 $\binom{n}{k}$ 个组合，每个组合需要 $O(k)$ 时间计算权值，总复杂度为 $O\!\left(k\binom{n}{k}\right)$ ，只能用于 $n \leqslant 20$ 的子任务。瓶颈是同时枚举最大值和其余元素。

正解

关键观察

先固定所选序列中的最大值 $m$ 。因为 $m\mathbin{\mathrm{xor}}m=0$ ，其余 $k-1$ 个元素应该从所有不大于 $m$ 的元素中选出，使 $a_i\mathbin{\mathrm{xor}}m$ 的和最大。

思路

将所有 a_i 排序。依次把当前元素 a_i 作为“最后一个最大值”考虑，Trie 中只放它之前的元素：这样既允许更小的值，也允许同值的更早出现，但不会重复使用当前这个元素。

固定 m 后，比较两个候选异或值时，最高不同位决定大小。因此在二进制 Trie 的每一层，优先走与 m 当前位相反的分支：这一分支的异或当前位为 1，其中的所有值都比另一分支更优。

如果优先分支的元素数不超过还需要的数量，就整支取走；整支的异或和用每一位的 1 的个数计算。为了支持这个总和计算，预处理排序数组每一位的前缀计数。

代码

cpp

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 19:06
 * update_at: 2026-09-06 19:22
 */
#include <bits/stdc++.h>
using namespace std;
const int MAX_BIT = 30;

struct TrieNode {
    int child[2];
    int left_rank;
    int right_rank;
    int count;
};

int n, k;
vector<int> value_list;
vector<TrieNode> trie;
vector<vector<int> > prefix_one;

int new_node() {
    TrieNode node;
    node.child[0] = node.child[1] = 0;
    node.left_rank = n;
    node.right_rank = 0;
    node.count = 0;
    trie.push_back(node);
    return (int)trie.size() - 1;
}

// 建立完整的值域 Trie，同时记录每个节点对应的排序下标区间。
void build_structure(int value, int rank) {
    int p = 1;
    trie[p].left_rank = min(trie[p].left_rank, rank);
    trie[p].right_rank = max(trie[p].right_rank, rank + 1);
    for (int bit = MAX_BIT; bit >= 0; bit--) {
        int direction = (value >> bit) & 1;
        if (trie[p].child[direction] == 0) {
            trie[p].child[direction] = new_node();
        }
        p = trie[p].child[direction];
        trie[p].left_rank = min(trie[p].left_rank, rank);
        trie[p].right_rank = max(trie[p].right_rank, rank + 1);
    }
}

// 激活排序下标为 rank 的数。当前时刻激活的元素总是一个前缀。
void activate(int value) {
    int p = 1;
    trie[p].count++;
    for (int bit = MAX_BIT; bit >= 0; bit--) {
        int direction = (value >> bit) & 1;
        p = trie[p].child[direction];
        trie[p].count++;
    }
}

// 计算一个 Trie 节点中当前已激活元素的 xor 总和。
long long sum_xor(int node, int x, int activated_prefix, int highest_bit) {
    int left = trie[node].left_rank;
    int right = min(trie[node].right_rank, activated_prefix);
    if (left >= right) {
        return 0;
    }

    long long result = 0;
    for (int bit = 0; bit <= highest_bit; bit++) {
        int ones = prefix_one[bit][right] - prefix_one[bit][left];
        int total = right - left;
        int xor_ones = ((x >> bit) & 1) ? total - ones : ones;
        result += (long long)xor_ones * (1LL << bit);
    }
    return result;
}

// 查询当前集合中最大的 need 个 (value xor x) 之和。
long long query_top_sum(int node, int bit, int x, int need, int activated_prefix) {
    if (need == 0 || bit < 0) {
        return 0;
    }

    int x_bit = (x >> bit) & 1;
    int preferred = x_bit ^ 1; // 这一支在当前位产生 1，更优先。
    int other = x_bit;
    int preferred_node = trie[node].child[preferred];
    int preferred_count = preferred_node == 0 ? 0 : trie[preferred_node].count;

    if (preferred_count >= need) {
        return (long long)need * (1LL << bit)
            + query_top_sum(preferred_node, bit - 1, x, need,
                            activated_prefix);
    }

    long long result = 0;
    if (preferred_count > 0) {
        result += sum_xor(preferred_node, x, activated_prefix, bit);
    }
    int other_node = trie[node].child[other];
    result += query_top_sum(other_node, bit - 1, x, need - preferred_count,
                            activated_prefix);
    return result;
}

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

    cin >> n >> k;
    value_list.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> value_list[i];
    }
    sort(value_list.begin(), value_list.end());

    prefix_one.assign(MAX_BIT + 1, vector<int>(n + 1, 0));
    for (int bit = 0; bit <= MAX_BIT; bit++) {
        for (int i = 0; i < n; i++) {
            prefix_one[bit][i + 1] = prefix_one[bit][i]
                + ((value_list[i] >> bit) & 1);
        }
    }

    trie.reserve(n * (MAX_BIT + 1) + 5);
    trie.push_back(TrieNode());
    new_node(); // 根节点编号固定为 1。
    for (int i = 0; i < n; i++) {
        build_structure(value_list[i], i);
    }

    long long answer = 0;
    for (int i = 0; i < n; i++) {
        // 把当前值作为被选子序列中的最后一个最大值，
        // 其余 k-1 个元素只能来自排序前缀。
        if (i >= k - 1) {
            long long candidate = query_top_sum(1, MAX_BIT, value_list[i],
                                                k - 1, i);
            answer = max(answer, candidate);
        }
        activate(value_list[i]);
    }

    cout << answer << '\n';
    return 0;
}

复杂度

Trie 高度为 31。每次查询至多访问 31 层，并在至多 31 个整支上计算 31 位的异或和，时间复杂度为 O(n·31^2)，可视为 O(n log^2 A)。预处理和 Trie 空间复杂度为 O(n log A)。

总结

“最大值”是这题的切入口：固定它以后，目标就变成静态集合中的前 k-1 大异或值之和。排序保证最大值约束，Trie 保证异或值按二进制高位贪心选取。

图示解析

这张图串起本题从最大值枚举到异或求和的主线：

text

1
2
3
4
5
6排序后的序列
`- 枚举最后一个最大值 m
   `- 查询前缀中的 k-1 个元素
      |- 异或当前位为 1：优先进入
      `- 不足时补另一分支
         `- 累加前 k-1 大异或值

排序前缀保证候选值不超过当前最大值，且当前元素尚未被激活。Trie 的高位优先顺序正好等价于比较异或值的大小。