CF888G Xor-MST
2026-09-30
题解
由于要求 xor 的最小值,不妨在 0/1 Trie 上从最高位往下进行讨论。
如果当前位为 b,所有的点按照 b 可以分为 0 类和 1 类,容易发现,在这两类内部的点边权一定小于 2b,跨过两边的边权一定大于 2b。
为了求最小生成树,可以保证跨过两边的边有且仅有一条,那么要考虑怎么取到最小的边,枚举肯定是不可取的,考虑直接在字典树上按位贪心:
假设有左右儿子,我们应该尽量让最高位相同,这样能让边尽可能小,递归到两种情况取 min 即可。
至于统计答案,直接 dfs 整颗 Trie 树,若有左右儿子则加上 2b 然后求解这条边即可。
可以将原数组去重,因为相同的点连边值为 0。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
#define LOCAL
namespace IO {
#ifndef LOCAL
#define SIZE (1<<20)
char in[SIZE] , *p1=in , *p2=in , out[SIZE] , *p3=out;
#define getchar() (p1==p2 && (p2=(p1=in)+fread(in,1,SIZE,stdin)) , p1==p2 ? EOF : *p1 ++)
#define flush() (fwrite(out,1,p3-out,stdout) , p3=out)
#define putchar(c) (p3==out+SIZE && flush() , *p3 ++ = c)
class Flush{public: ~Flush(){flush();} } ___;
#endif
inline int read() {
int x = 0 , f = 1;
int c = getchar();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = (x<<3) + (x<<1) + c - '0';
c = getchar();
}
return x*f;
}
inline void write(LL x , bool f = true) {
if(x < 0) x = -x , putchar('-');
static short stk[100] , top; top = 0;
do {stk[++ top] = x%10 , x/=10; } while(x);
while(top) putchar(stk[top --] | '0');
if(f) putchar('\n');
else putchar(' ');
}
#ifndef LOCAL
#undef getchar
#undef SIZE
#undef flush
#undef putchar
#endif
} using namespace IO;
const int N = 2e5+10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct Node {
int s[2];
};
int n;
int a[N];
int tr[N*30][2] , idx;
LL ans;
void insert(int x) {
int p = 0;
for(int i = 29 ; i >= 0 ; i --) {
int u = (x>>i) & 1;
if(!tr[p][u]) tr[p][u] = ++ idx;
p = tr[p][u];
}
}
LL solve(int u , int v , int b) {
if(!u || !v) return INF;
if(b < 0) return 0;
LL res = INF;
if(tr[u][0] && tr[v][0]) res = min(res , solve(tr[u][0] , tr[v][0] , b-1));
if(tr[u][1] && tr[v][1]) res = min(res , solve(tr[u][1] , tr[v][1] , b-1));
if(res < INF) return res;
if(tr[u][0] && tr[v][1]) res = min(res , (1ll << b) + solve(tr[u][0] , tr[v][1] , b-1));
if(tr[u][1] && tr[v][0]) res = min(res , (1ll << b) + solve(tr[u][1] , tr[v][0] , b-1));
return res;
}
void dfs(int u , int b) {
if(b < 0) return;
int l = tr[u][0] , r = tr[u][1];
if(l && r) ans += (1ll << b) + solve(l , r , b-1);
if(l) dfs(l , b-1);
if(r) dfs(r , b-1);
}
int main() {
n = read();
for(int i = 1 ; i <= n ; i ++) a[i] = read();
sort(a+1 , a+n+1); n = unique(a+1 , a+n+1) - a - 1;
for(int i = 1 ; i <= n ; i ++) insert(a[i]);
ans = 0; dfs(0 , 29);
write(ans);
return 0;
}