文章目录
题目思路代码思考
题目
给你
n
n
n 个点，每个点点权为
a
i
a_i
ai，定义连接两点花费为
a
i
a_i
ai^
a
j
a_j
aj 求最小生成树？
1
≤
n
≤
2
⋅
1
0
5
1\le n \le 2\cdot10^5
1≤n≤2⋅105
思路
首先我们来看看这个算法： Boruvka算法 然后如果对于这道题我们用这个算法的话我们会发现，对于一个数的最高位是
0
0
0，它一定会优先和最高位是
0
0
0 的连边再和最高位是
1
1
1 的连边，我们就不难和
01
T
i
r
e
01Tire
01Tire 联系起来
我们首先研究如果将数按照最高位01划分为两个集合
S
1
,
S
2
S_1,S_2
S1,S2 对于某个合并过程而言，我们一定是先
S
1
，
S
2
S1，S2
S1，S2 点集内分别连接完成后再考虑
S
1
，
S
2
S1，S2
S1，S2 点集合并，其实用
K
r
u
s
k
a
l
Kruskal
Kruskal 算法也可以证明，优先选择较小边权进行合并 为了方便实现，我们可以将所有数
s
o
r
t
sort
sort 后，一个点就能对应一段区间数
L
u
,
R
u
L_u,R_u
Lu,Ru 的从根到
u
u
u 之间的边的那几位都相等 合并是将
S
1
S1
S1 内的数一个一个到
S
2
S2
S2 的
01
T
i
r
e
01Tire
01Tire 内查询最小异或和（尽量走相同的）即可
代码
#include<set>
#include<map>
#include<cmath>
#include<deque>
#include<stack>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std
;
int read(){
int f
=1,x
=0;char c
=getchar();
while(c
<'0'||'9'<c
){if(c
=='-')f
=-1;c
=getchar();}
while('0'<=c
&&c
<='9') x
=(x
<<3)+(x
<<1)+(c
^48),c
=getchar();
return f
*x
;
}
#define MAXN 200000
#define INF 0x3f3f3f3f
const int bit
=30;
int a
[MAXN
+5];
int n
,ch
[bit
*MAXN
][2],L
[bit
*MAXN
+5],R
[bit
*MAXN
+5],Root
,ncnt
;
void Insert(int val
,int pos
){
int u
=Root
;
for(int i
=bit
;~i
;i
--){
int j
=((val
>>i
)&1);
if(!ch
[u
][j
]) ch
[u
][j
]=++ncnt
,L
[ncnt
]=pos
,R
[ncnt
]=pos
;
L
[u
]=min(L
[u
],pos
),R
[u
]=max(R
[u
],pos
);
u
=ch
[u
][j
];
}
return ;
}
LL
Query(int u
,int nbit
,int val
){
LL ret
=0;
for(int i
=nbit
;~i
;i
--){
int j
=((val
>>i
)&1);
if(ch
[u
][j
]) u
=ch
[u
][j
];
else ret
|=(1<<i
),u
=ch
[u
][j
^1];
}
return ret
;
}
LL
DFS(int u
,int nbit
){
LL ret
=0;
if(!nbit
)
return (a
[L
[u
]]^a
[R
[u
]]);
if(ch
[u
][0]) ret
+=DFS(ch
[u
][0],nbit
-1);
if(ch
[u
][1]) ret
+=DFS(ch
[u
][1],nbit
-1);
if(ch
[u
][0]&&ch
[u
][1]){
LL con
=INF
;
for(int i
=L
[ch
[u
][0]];i
<=R
[ch
[u
][0]];i
++)
con
=min(con
,Query(ch
[u
][1],nbit
-1,a
[i
]));
ret
+=con
+(1<<nbit
);
}
return ret
;
}
int main(){
n
=read();
for(int i
=1;i
<=n
;i
++)
a
[i
]=read();
sort(a
+1,a
+n
+1);
L
[Root
]=1,R
[Root
]=n
;
for(int i
=1;i
<=n
;i
++)
Insert(a
[i
],i
);
printf("%lld\n",DFS(Root
,bit
));
return 0;
}
思考
3个月前才做过就不会了…要多总结
