「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 的个数计算。为了支持这个总和计算，预处理排序数组每一位的前缀计数。

实现上，Trie 节点只维护子树元素个数 pass 和子树区间的左端点 left，区间长度就是 pass，右端点由 left + pass 得到。这样“取一整支”就变成“对一段排序下标求和”，可以用位前缀计数一次算完；具体推导见下面的「关键函数」小节。

代码

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
148
149
150
151
152
153
154
155
156
157
158/**
 * 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-27 14:09
 */
// main.cpp：P17416 正解。
//
// 思路：把 a 从小到大排序，枚举“子序列里的最大值” a[i]，
//       其余 k-1 个数只能从它前面（a[0..i-1]）里选。
//       固定最大值 m = a[i] 后，要让 sum(value xor m) 最大，
//       就是要求前面这些数里「前 k-1 大的 (value xor m) 之和」。
//
// 结构：01 Trie（按二进制位建的 Trie），可以理解成把字典树模板
//       从「26 个小写字母」换成「0/1 两个二进制位」：
//       - ch[26]  -> ch[2]，每个节点只有 0/1 两个儿子；
//       - pass    不变，表示「落在这个节点子树里的已插入元素个数」。
//
//       每个节点还记录它管的排序区间。由于我们按 rank 递增插入，
//       一个节点子树里的元素在排序数组里一定是连续的一段：
//       - left 是这段区间的左端点，建节点时就能确定；
//       - 区间长度恰好是 pass（子树里已插入的元素个数），
//         所以右端点 right = left + pass 直接算出来，不用另存。
//
// 查询：从高位往低位贪心。当前位希望异或出来是 1，所以优先走与 m
//       当前位相反的分支；这一支不够取就整支拿走，再从另一支补。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;   // n 的上界
const int MAX_BIT = 30;    // a_i <= 1e9 < 2^30，二进制第 0..30 位
const int DIGIT = 2;       // 01 Trie：每个节点只有 0 和 1 两个分支

int n, k;
int a[MAXN];               // 排序后的输入序列

// bit_one[b][i] = 排序后前 i 个数（a[0..i-1]）里，二进制第 b 位为 1 的个数。
// 有了它，就能 O(1) 算出一段连续下标区间中第 b 位为 1 的元素个数。
int bit_one[MAX_BIT + 1][MAXN];

// 01 Trie 的节点
struct Node {
    int ch[DIGIT] = {0, 0}; // ch[c] 是第 c 位上的子节点编号，0 表示没有这个分支
    int pass = 0;           // 落在这个节点子树里的已插入元素个数
    int left = 0;           // 这个节点子树对应区间的左端点，即记成 [left, left + pass)
};

// 01 Trie：插入元素，以及查询前若干大的异或和
struct Trie {
    vector<Node> tree; // tree[0] 是根节点，节点编号 0 也表示空分支

    Trie() { tree.push_back(Node()); }

    // 新建一个节点，left 是它对应区间的左端点（第一次走到这个前缀时的 rank）
    int new_node(int left) {
        tree.push_back(Node());
        tree.back().left = left;
        return (int)tree.size() - 1;
    }

    // 插入一个数 value，它是排序数组里第 rank 个（从 0 开始）。
    // 只需要维护 pass：区间长度会跟着一起长，right 不用单独记。
    void insert(int value, int rank) {
        int u = 0; // 从根出发
        tree[u].pass++;
        for (int bit = MAX_BIT; bit >= 0; bit--) {
            int c = (value >> bit) & 1; // 取出当前这一位
            if (tree[u].ch[c] == 0) {   // 没有这个分支就先建一个
                tree[u].ch[c] = new_node(rank);
            }
            u = tree[u].ch[c];
            tree[u].pass++;
        }
    }

    // 求节点 u 的子树里，所有已插入元素与 x 异或之后的和。
    // highest_bit：这个子树里的元素与 x 异或后，不为 0 的最高位。
    long long xor_sum(int u, int x, int highest_bit) {
        int l = tree[u].left;         // 子树区间左端点
        int total = tree[u].pass;     // 子树元素个数，也是区间长度
        int r = l + total;            // 区间右端点，区间是 [l, r)

        long long result = 0;
        for (int bit = 0; bit <= highest_bit; bit++) {
            int ones = bit_one[bit][r] - bit_one[bit][l];
            // x 这一位是 0：异或结果里这一位的 1，来自原本这一位是 1 的数；
            // x 这一位是 1：则来自原本这一位是 0 的数。
            int xor_ones = ((x >> bit) & 1) ? total - ones : ones;
            result += (long long)xor_ones * (1LL << bit);
        }
        return result;
    }

    // 在当前 Trie（只装了排序前缀里的元素）里，
    // 求最大的 need 个 (value xor x) 的和。
    // 调用前保证 need <= 节点 u 子树里的元素个数。
    long long top_k_xor_sum(int u, int bit, int x, int need) {
        if (need <= 0 || bit < 0) {
            return 0;
        }

        int x_bit = (x >> bit) & 1;
        int prefer = x_bit ^ 1; // 这一位异或结果为 1 的分支，优先走
        int other = x_bit;
        int p = tree[u].ch[prefer];
        int prefer_count = (p == 0) ? 0 : tree[p].pass;

        if (prefer_count >= need) {
            // 优先分支里就够 need 个，这一位全都能拿到 1
            return (long long)need * (1LL << bit)
                + top_k_xor_sum(p, bit - 1, x, need);
        }

        // 优先分支不够：整支取走，再去另一分支补剩下的
        long long result = 0;
        if (prefer_count > 0) {
            result += xor_sum(p, x, bit);
        }
        int q = tree[u].ch[other]; // 因为 need <= pass，这里 q 一定不为 0
        return result + top_k_xor_sum(q, bit - 1, x, need - prefer_count);
    }
};

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

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n); // 排序后，子序列元素就是连续的一段前缀里挑

    // 预处理每一位的前缀 1 的个数
    for (int bit = 0; bit <= MAX_BIT; bit++) {
        for (int i = 0; i < n; i++) {
            bit_one[bit][i + 1] = bit_one[bit][i] + ((a[i] >> bit) & 1);
        }
    }

    Trie trie;
    trie.tree.reserve((long long)n * (MAX_BIT + 1) + 5);

    long long answer = 0;
    for (int i = 0; i < n; i++) {
        // 用 a[i] 当最大值，其余 k-1 个数从 a[0..i-1] 里取
        if (i >= k - 1) {
            long long now = trie.top_k_xor_sum(0, MAX_BIT, a[i], k - 1);
            answer = max(answer, now);
        }
        // 查询完再插入 a[i]，保证自己不会选到自己
        trie.insert(a[i], i);
    }

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

关键函数：整棵子树的异或和

正解里最不容易一眼看懂的，是“整支取走”时用来求和的 xor_sum。它要在 O(31) 的时间内算出

\sum_{v \in \text{subtree}(u)} (v \oplus x)

而不是去遍历子树里的每个数。下面分四步拆开。

第一步：按二进制位拆开。 设 $\text{bit}_b(y)$ 表示 $y$ 的第 $b$ 位，则

\sum_v (v \oplus x) = \sum_b 2^b \cdot \#\{\, v : \text{bit}_b(v) \oplus \text{bit}_b(x) = 1 \,\}

也就是说：每一位单独统计“异或后这一位是 1”的元素个数，再乘 $2^b$ 累加。

第二步：这一位为 1 的个数怎么数。 记子树里共有 total 个数，其中第 b 位原本是 1 的有 ones 个。异或的规则是“不同才为 1”，所以：

`x` 的第 `b` 位	异或后第 `b` 位为 1 的是	个数
`0`	原本为 `1` 的数	`ones`
`1`	原本为 `0` 的数	`total - ones`

第三步：ones 和 total 用排序区间的下标算。 一个 Trie 节点代表一个二进制前缀，而同一个前缀的所有数，在按大小排序后的数组里必然是一段连续的下标。注意这个“连续区间”是排序数组上的下标区间，不是树的 dfs 序——代码从头到尾没有遍历过 Trie，靠的只是这条链：

前缀相同 → 数值落在某个区间里 → 排序后下标连续。

节点记录的区间是左闭右开的 [left, right)：left 在建节点时就确定了（第一次走到这个前缀时的下标），而区间长度恰好等于子树里的元素个数 pass。所以代码只存 left 和 pass，右端点用 right = left + pass 算出来，不需要单独维护：

cpp

1
2
3
4
5
6int l = tree[u].left;                                  // 子树区间左端点
int total = tree[u].pass;                              // 子树元素个数，也是区间长度
int r = l + total;                                     // 右端点：left + pass
int ones = bit_one[bit][r] - bit_one[bit][l];          // 第 bit 位为 1 的个数
int xor_ones = ((x >> bit) & 1) ? total - ones : ones; // 异或后这一位为 1 的个数
result += (long long)xor_ones * (1LL << bit);          // 这一位的贡献

下面这张图用一个 3 位数的例子说明 [left, right) 到底指什么：

图中排序数组是 4,5,6,7，每个 Trie 节点都标出自己管的下标区间：叶子只管一格，prefix 10 管 a[0..1] 即 [0, 2)，prefix 11 管 a[2..3] 即 [2, 4)。left 是这段的第一个下标，right 是最后一个下标加一，所以写成左闭右开。

total 一眼看出是 4；bit_one[1] 在右端点 4 处为 2、左端点 0 处为 0，所以第 1 位为 1 的有 ones = 2 个。

第四步：为什么只算到 highest_bit 就够了。 容易误以为要算全部 31 位。回想调用时机：只有在“整支取走优先分支”时才调用它；而查询向下走时，只有优先分支不够才会进入另一分支，也就是只在 $v$ 这一位与 $x$ 相同时继续往下。于是路径上 highest_bit 以上的每一位，子树里的 $v$ 都和 $x$ 相同，异或结果恒为 0，不必统计。传入的 highest_bit = bit 正好把范围收在 0..bit。

完整走一个例子。 取上面的子树 [4,5,6,7] 和 x = 2，其中 left = 0、right = 4、total = 4，而 $x = 010_2$ 。

`bit`	原本该位为 1 的 `ones`	`x` 该位	异或后为 1 的 `xor_ones`	贡献
2	4	0	4	4 × 4 = 16
1	2	1	2	2 × 2 = 4
0	2	0	2	2 × 1 = 2

合计 16 + 4 + 2 = 22。手工验算 $4 \oplus 2 = 6$ 、 $5 \oplus 2 = 7$ 、 $6 \oplus 2 = 4$ 、 $7 \oplus 2 = 5$ ，加起来同样是 22。

区间必须只包含已插入的元素

xor_sum 把 [left, right) 当作“子树里现有的数”，因此主循环必须先查询、后 insert 当前元素，否则区间会混进还没激活的数。

复杂度

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 的高位优先顺序正好等价于比较异或值的大小。