Codeforces 241B: Friends
1. 题目大意
给出\(n\)个非负整数\(a_i\)，两两配成无序对，每对\((a_i, a_j)\)的好看度为\( a_i \oplus a_j \)。请选出\(m\)对使得好看度之和最大。
其中\(\oplus\)表示异或。
2. 数据范围
\( 1 \le n \le 5 \cdot 10^4 \)
\( 0 \le m \le \frac { n \cdot (n - 1) } 2 \)
\( 0 \le a_i \le 10^9 \)
3. 题解
记\( w =max\{ log_2 a_i \} \)。
将算法分为两部分：
1. 求出最大的\(l\)使得满足\(a_i \oplus a_j \ge l\)的数对的个数不小于\(m\)；
2. 对这些数对的好看度求和。
对于第一步，我们可以将所有\(a_i\)插入Trie，在Trie上走一走，每次从高到低贪心考虑每一位，检查一下这一位置为1后满足条件的个数是否超过\(m\)。这样我们就可以在\( O(nw) \)的时间复杂度内求出\(l\)及好看度大于\(l\)的对数\(c\)。
对于第二步，我们可以把每个\(a_i\)放在Trie上跑，就可以把原问题分解成Trie上若干棵子树中所有数与\(a_i\)异或之和。如果记录子树内每一位为1的个数，那么空间复杂度是\(O(nw^2)\)的。考虑到每棵子树在dfs序中是一个区间，我们就可以做个前缀和，然后用对应区间相减即可。这样我们就得到了好看度大于\(l\)的数对的好看度之和\(s\)。
最终答案即为\(s + l \cdot (m - c)\)。
4. 时间复杂度
时间复杂度：\( O( nw^2 ) \)
空间复杂度：\( O( nw ) \)
5. 代码
代码在这里。
我的实现中空间复杂度是\(O(nw^2)\)的。
