模拟赛 生成树

题目描述

给定 $n$ 个点，第 $i$ 个点有一个非负点权 $a_i$。 这 $n$ 个点连成了一张无向完全图，其中第 $i$ 个点和第 $j$ 个点连的边长度为 $a_i$ 按位异或 $a_j$。现在要求出这张无向完全图的最小生成树。 $1⩽n⩽200000,0⩽a_i⩽1073741823$ 时间限制2s，空间限制512MB。

题解

位运算问题常用贪心。将 $a$ 排序并分为高位为$0$和高位为$1$两类。那么整个图的最小生成树则为高位为$0$的数构成的最小生成树并上高位为$1$的最小生成树再加上再两类中个选一个数的最小边权。高位相同的答案可以递归，高位不同时将高位为$0$的数加入01字典树中，再将高位为$1$的数挨个在字典树中跑，从高位选择到低位，找出最小边权。 时间复杂度 $O(nlo{g}_2^{2}ma{x}_a)$，空间复杂度 $O(nlo{g}_{2}ma{x}_a)$。