傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個長度為$n$序列$a$，每兩個點之間的邊權為$a_i\oplus a_j$，問你最小生成樹的權值是多少。

$n\le 2e5,a_i<2^{30}$

思路：

看到最小生成樹，我們可以想到克魯斯卡爾算法，但是完全圖顯然不能直接做，但是異或的話顯然我們需要放到$tire$樹上來跑的。

這里先介紹一種基于$tire$樹分治的算法。

根據克魯斯卡爾的思想，我們需要找當前邊權最小的點來合并，顯然就是兩個點的$lca$中深度最深的位置，但是這個比較難搞啊，既然我們都放在$tire$樹上了，為什么不利用一下$tire$樹的性質呢？

根據$tire$樹我們可知，每個點最多有兩個兒子，并且可以拆位來看貢獻！

所以我們遍歷$tire$樹，找每個可能為$lca$的點，找一個最小的邊，加上當前位的貢獻即可。

一個小技巧，我們可以將$a$排序后依次插入，那么$tire$每個點的區間都是連續的。

復雜度$O(nlo{g}^{2}n)$

在考慮利用$Boruvka$算法來解決。

我們需要使用$Boruvka$算法來快速找出對于每個連通塊，與他連邊最小的聯通塊是哪個，讓后不斷折半，最多進行$logn$次。

考慮對每一個點$a_i$建一顆字典樹，讓后對全局建一顆字典樹，比如要查與$i$這個連通塊異或值最小的聯通塊，我們可以利用全局的$tir{e}_{all}$減去當前的$tir{e}_i$，這樣就得到了其他連通塊的$tire$，在上面貪心的找即可，合并的時候啟發式合并即可。

不知道為何$a$排序就過了，不排序過不了。

復雜度$O(nlo{g}^{2}n?\alpha )$

// Problem: G. Xor-MST // Contest: Codeforces - Educational Codeforces Round 32 // URL: https://codeforces.com/contest/888/problem/G // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=200010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; LL a[N]; int tr[N*32][2],idx; int l[N*32],r[N*32];void insert(int x,int id) {int p=0;for(int i=30;i>=0;i--) {int u=x>>i&1;if(!tr[p][u]) tr[p][u]=++idx;if(!l[p]) l[p]=id; r[p]=id;p=tr[p][u];}if(!l[p]) l[p]=id; r[p]=id; }LL query(int x,int p,int dep) {if(dep==-1) return 0;int u=x>>dep&1;if(tr[p][u]) return query(x,tr[p][u],dep-1);else return query(x,tr[p][!u],dep-1)+(1<<dep); }LL dfs(int p,int dep) {if(dep==-1) return 0;if(tr[p][0]&&tr[p][1]) {LL ans=1e12;for(int i=l[tr[p][0]];i<=r[tr[p][0]];i++) {ans=min(ans,query(a[i],tr[p][1],dep-1));}return dfs(tr[p][0],dep-1)+dfs(tr[p][1],dep-1)+ans+(1<<dep);} else if(tr[p][1]) {return dfs(tr[p][1],dep-1);} else if(tr[p][0]) {return dfs(tr[p][0],dep-1);}return 0; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);for(int i=1;i<=n;i++) insert(a[i],i);printf("%lld\n",dfs(0,30));return 0; } /**/ // Problem: G. Xor-MST // Contest: Codeforces - Educational Codeforces Round 32 // URL: https://codeforces.com/contest/888/problem/G // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<LL,LL> PII;const int N=300010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; LL a[N]; int tr[N*50][2],root[N],idx,cnt[N*50],ed[N*50]; int p[N],se[N],id[N]; LL d[N];int find(int x) {return x==p[x]? x:p[x]=find(p[x]); }void dfs(int p,int q) {cnt[p]+=cnt[q];ed[p]=ed[q];for(int i=0;i<2;i++) {if(tr[q][i]) {if(!tr[p][i]) {tr[p][i]=tr[q][i];} else dfs(tr[p][i],tr[q][i]);}} }void merge(int a,int b) {int pa=find(a),pb=find(b);if(pa==pb) return;if(se[pa]<se[pb]) dfs(root[pb],root[pa]),p[pa]=pb,se[pb]+=se[pa];else dfs(root[pa],root[pb]),p[pb]=pa,se[pa]+=se[pb]; }void insert(int p,int x,int id) {ed[p]=id;for(int i=30;i>=0;i--) {int u=x>>i&1;if(!tr[p][u]) tr[p][u]=++idx;assert(idx<N*50);p=tr[p][u]; cnt[p]++;ed[p]=id;} }PII query(int x,int p) {int pp=root[0];LL ans=0;for(int i=30;i>=0;i--) {int u=x>>i&1;if(tr[pp][u]&&cnt[tr[pp][u]]-cnt[tr[p][u]]>0) p=tr[p][u],pp=tr[pp][u];else p=tr[p][!u],pp=tr[pp][!u],ans+=1<<i;}return {ed[pp],ans}; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);random_shuffle(a+1,a+1+n);root[0]=++idx;for(int i=1;i<=n;i++) {root[i]=++idx; p[i]=i; se[i]=1;assert(idx<N*50);insert(root[i],a[i],i); insert(root[0],a[i],i);}// merge(3,2); merge(1,3);// PII now=query(a[3],root[find(3)]);// cout<<now.X<<' '<<now.Y<<endl;// return 0;LL ans=0;int all=0;while(1) {for(int i=1;i<=n;i++) d[i]=(1ll<<31)-1;int cur=0;for(int i=1;i<=n;i++) {PII now=query(a[i],root[find(i)]);int x=find(i),y=find(now.X);if(x==y) continue;if(d[x]>now.Y) d[x]=now.Y,id[x]=now.X;if(d[y]>now.Y) d[y]=now.Y,id[y]=x;}for(int i=1;i<=n;i++) if(d[i]!=(1ll<<31)-1&&find(i)!=find(id[i])) {merge(i,id[i]); ans+=d[i];cur++;}if(!cur) break;}cout<<ans<<endl;return 0; } /**/

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 32 G. Xor-MST 01tire + 分治 + Boruvka的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。