cf888G. Xor-MST(Boruvka最小生成树 Trie树)
程序员文章站
2022-09-03 15:18:50
题意 "题目链接" 给出$n$点,每个点有一个点权$a[i]$,相邻两点之间的边权为$a[i] \oplus a[j]$,求最小生成树的值 Sol 非常interesting的一道题,我做过两种这类题目, "一种是直接打表找规律" ,另一种就像这种用Boruvka算法加一些骚操作来搞。 首先,把所有 ......
题意
给出\(n\)点,每个点有一个点权\(a[i]\),相邻两点之间的边权为\(a[i] \oplus a[j]\),求最小生成树的值
sol
非常interesting的一道题,我做过两种这类题目,一种是直接打表找规律,另一种就像这种用boruvka算法加一些骚操作来搞。
首先,把所有元素扔到trie树里面,这样对于trie树上的每一层(对应元素中的每一位)共有两种情况:
全为0或全为1
一部分为0另一部分为1
对于第一种情况,我们无需考虑,因为任意点相邻产生的贡献都是0,对于第二种情况,需要找到一条最小的边来连接链各个集合,这可以在trie树上贪心实现
另外还有一个小trick,我们把元素从小到大排序,这样trie树上每个节点对应的区间就都是连续的
实现的时候可以从底往上update,也可以从上往下dfs
时间复杂度:\(o(nlognlog_{max(a_i)})\)
本来以为这题要写一年,结果写+调只用了1h不到?
#include<bits/stdc++.h> #define pair pair<int, int> #define fi first #define se second #define mp(x, y) make_pair(x, y) #define ll long long using namespace std; const int maxn = 2e5 + 10, b = 31, inf = 1e9 + 7; inline ll read() { char c = getchar(); ll x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[maxn], l[maxn * 30], r[maxn * 30], ch[maxn * 30][2], tot = 0; void insert(int val, int pos) { int now = 0; for(int i = b; ~i; i--) { int x = val >> i & 1; if(!ch[now][x]) ch[now][x] = ++tot, l[tot] = pos, r[tot] = pos;//???ʵ???֮?????λ l[now] = min(l[now], pos); r[now] = max(r[now], pos); now = ch[now][x]; } } int query(int val, int now, int nowbit) { ll ans = 1 << (nowbit + 1); for(int i = nowbit; ~i; i--) { int x = val >> i & 1; if(ch[now][x]) now = ch[now][x]; else ans |= 1 << i, now = ch[now][x ^ 1]; } return ans; } ll dfs(int x, int nowbit) { ll res = 0; if(nowbit == 0) return (ch[x][0] && ch[x][1]) ? (a[l[ch[x][0]]] ^ a[r[ch[x][1]]]) : 0; //if(nowbit == 0) return ; if(ch[x][0] && ch[x][1]) { int tmp = inf; for(int i = l[ch[x][0]]; i <= r[ch[x][0]]; i++) tmp = min(tmp, query(a[i], ch[x][1], nowbit - 1)); res += tmp; } if(ch[x][0]) res += dfs(ch[x][0], nowbit - 1); if(ch[x][1]) res += dfs(ch[x][1], nowbit - 1); return res; } int main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(); sort(a + 1, a + n + 1); l[0] = inf; r[0] = 0; for(int i = 1; i <= n; i++) insert(a[i], i); cout << dfs(0, b); return 0; }
上一篇: 欢乐新春,宝宝不能做的7件事
下一篇: 怎样控制好孩子吃饭量?