【CF888G】Xor-MST（最小生成樹(shù)，Trie樹(shù)）

題面

CF
洛谷

題解

利用\(Kruskal\)或者\(Prim\)算法都很不好計(jì)算。
然而我們還有一個(gè)叫啥來(lái)著?\(B\)啥啥的算法，就叫\(B\)算法吧。
思想是對(duì)于每個(gè)點(diǎn)找到一條最小邊，并且將這條邊連上，不難證明每次至少連上了\(n/2\)個(gè)點(diǎn)。
再將這些聯(lián)通塊看做一個(gè)點(diǎn)繼續(xù)重復(fù)這個(gè)過(guò)程，時(shí)間復(fù)雜度是\(log\)級(jí)別的。

我們從高位往低位看，如果我們按照\(01\)分類，根據(jù)上述的過(guò)程，不難得到，如果\(01\)兩個(gè)集合都存在的話，它們之間一定會(huì)連上一條邊，并且\(01\)分類后的兩個(gè)集合一定在內(nèi)部形成聯(lián)通塊，這就很好辦了，直接分治遞歸處理，每次拿\(Trie\)算一下\(01\)分類后兩個(gè)集合之間邊的最小值然后給連上就好。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define ll long long #define MAX 200200 #define pb push_back inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,a[MAX],tot; struct Node{int ch[2];}t[MAX<<5]; void insert(int &x,int w,int p) {if(!x)x=++tot,t[x].ch[0]=t[x].ch[1]=0;if(p==-1)return;insert(t[x].ch[(w>>p)&1],w,p-1); } int Query(int x,int w,int p) {if(p==-1)return 0;int c=(w>>p)&1;if(t[x].ch[c])return Query(t[x].ch[c],w,p-1);else return Query(t[x].ch[c^1],w,p-1)^(1<<p); } ll Solve(vector<int> v,int p) {if(!v.size()||p==-1)return 0;vector<int> d[2];int ret=0,rt;for(int i:v)d[(i>>p)&1].pb(i);if(d[0].size()&&d[1].size()){ret=1<<(p+1);rt=tot=0;for(int i:d[0])insert(rt,i,30);for(int i:d[1])ret=min(ret,Query(rt,i,30));}return ret+Solve(d[0],p-1)+Solve(d[1],p-1); } int main() {n=read();vector<int> a;for(int i=1;i<=n;++i)a.pb(read());printf("%I64d\n",Solve(a,30));return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cjyyb/p/9479584.html

總結(jié)

以上是生活随笔為你收集整理的【CF888G】Xor-MST（最小生成树，Trie树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。