网站开发项目设计文档,产品seo基础优化,旅游网站开发分析报告,查询网站入口G. Xor-MST
思路
异或最小生成树#xff0c;这里采用了一种分治的方法来贪心求解最值#xff1a;
首先我们对所有的点权值从小到大排个序#xff0c;从高位开始在中间找到一个这个位置上的0#xff0c;10#xff0c;10#xff0c;1分界点分成两个集合#xff0c;然后…G. Xor-MST
思路
异或最小生成树这里采用了一种分治的方法来贪心求解最值
首先我们对所有的点权值从小到大排个序从高位开始在中间找到一个这个位置上的010101分界点分成两个集合然后再通过递归的去求解两个集合。在递归的时候对两个分开的集合我们通过trietrietrie树去贪心的在两个集合连上一条边把这条边加入我们的答案。
为什么这样是对的显然我们分成两个集合我们可以抵消掉高位的一大堆一样的东西这个时候我们可以保证我们的贪心策略是正确的。
为什么我们要合并两个集合假设左边集合有nnn个点右边集合有mmm个点显然左边最多链接n−1n - 1n−1条边右边最多链接m−1m - 1m−1条边要使这nmn mnm个点形成一颗树必然我们要从左边选择一个点右边一个点链接一条边这个时候选点连边我们就可以贪心求解了。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \nusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, 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;
}// vectorpii 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;
}
