G. Xor-MST

思路

異或最小生成樹，這里采用了一種分治的方法來貪心求解最值：

• 首先我們對所有的點權值從小到大排個序，從高位開始在中間找到一個這個位置上的$0，1$分界點分成兩個集合，然后再通過遞歸的去求解兩個集合。
• 在遞歸的時候，對兩個分開的集合，我們通過$trie$樹去貪心的在兩個集合連上一條邊，把這條邊加入我們的答案。

為什么這樣是對的：顯然我們分成兩個集合我們可以抵消掉高位的一大堆一樣的東西，這個時候，我們可以保證我們的貪心策略是正確的。

為什么我們要合并兩個集合：假設左邊集合有$n$個點，右邊集合有$m$個點，顯然左邊最多鏈接$n?1$條邊，右邊最多鏈接$m?1$條邊，要使這$n+m$個點形成一顆樹，必然我們要從左邊選擇一個點，右邊一個點鏈接一條邊，這個時候選點連邊我們就可以貪心求解了。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 2e5 + 10;int trie[N * 31][2], tot; int a[N], n;void insert(int x) {int rt = 0;for(int i = 30; i >= 0; i--) {int now = (x >> i) & 1;if(!trie[rt][now]) {trie[rt][now] = ++tot;rt = trie[rt][now];trie[rt][0] = trie[rt][1] = 0;}else {rt = trie[rt][now];}} }int find(int x) {int ans = 0, rt = 0;for(int i = 30; i >= 0; i--) {int now = (x >> i) & 1;if(trie[rt][now]) {rt = trie[rt][now];}else {rt = trie[rt][now ^ 1];ans |= 1 << i;}}return ans; }ll ans = 0;void dfs1(int l, int r, int dep) {if(dep < 0 || l >= r) return ;int mid = l - 1;while(mid < r && ((a[mid + 1] >> dep) & 1) == 0) mid++;dfs1(l, mid, dep - 1);dfs1(mid + 1, r, dep - 1);if(mid == l - 1 || mid == r) return ;tot = 0;trie[tot][0] = trie[tot][1] = 0;for(int i = l; i <= mid; i++) {insert(a[i]);}int temp = INT_MAX;for(int i = mid + 1; i <= r; i++) {temp = min(temp, find(a[i]));}ans += temp; }// vector<pii> G[N];// void dfs2(int rt, int fa, int w) { // a[rt] = w; // for(auto i : G[rt]) { // if(i.first == fa) continue; // dfs2(i.first, rt, w ^ i.second); // } // }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();for(int i = 1; i <= n; i++) a[i] = read();// for(int i = 1; i < n; i++) {// int x = read() + 1, y = read() + 1, w = read();// G[x].pb(mp(y, w));// G[y].pb(mp(x, w));// }// dfs2(1, 0, 0);sort(a + 1, a + 1 + n);dfs1(1, n, 29);printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的G. Xor-MST（异或最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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