最小异或生成树
一、前置知识：
1.Trie树：
高效的存储和查找字符串集合的数据结构
int son[maxn][26],cnt[maxn],idx;
void add(char *str){///将新的字符串插入到字典树里
int p=0,len=strlen(str);
for(int i=0;i<len;i++){
///遍历字符串的每一个字母
int tmp=str[i]-'a';
if(!son[p][tmp]) son[p][tmp]=++idx;///没有节点的时候就创建节点
p=son[p][tmp];///往下走
}
cnt[p]++;///表示该地方有一个字符串
}
int qask(char *str){///查询某个字符串是否在字典树里出现过
int p=0,len=strlen(str);
for(int i=0;i<len;i++){
///逐位查找
int tmp=str[i]-'a';
if(!son[p][tmp]) return 0;///该节点不存在
p=son[p][tmp];///继续往下走
}
return cnt[p];///返回答案
} 2.最大异或对
题意：
在给定的n个整数里选出两个数进行异或运算，得到的结果最大是多少？
思路：
最基础的是要知道异或运算的含义，异或运算是一种位运算，简称“不进位加法”，在二进制下中逐位比较，若两位相同则为0，不同则为1。
思路一（暴力解法）：
int maxx=0;
for(int i=1;i<=n;i++)///枚举第一个数
for(int j=1;j<i;j++)///枚举第二个数 寻找和a[i]异或值最大的数
maxx=max(maxx,a[i]^a[j]); 思路二（用Trie优化第二层循环）：
首先要明确的一个问题就是在思路一中两层循环的作用，第一层循环是枚举第一个数x，第二层循环是寻找和第一个数异或值最大的数，然后再与最终结果取max。那么在这个过程中，我们可以利用贪心的思想，来将第二层循环省去。问题就转化成了如何找到和x异或值最大的数。
根据异或常见的思路，我们按位考虑，从最高位依次考虑，每次都优先考虑和x的当前位不同的数，这样肯定会比和x的当前位相同的数优，这样依次递推下去。
综上，我们可以构建01字典树，for循环枚举第一个数，再贪心求出第二个数，最后对答案取max即可。
int a[maxn],son[maxm][2],idx;
void add(int x){
///将数插入01字典树
int p=0;
for(int i=30;i>=0;i--){
///二进制拆分
int tmp=son[p][x>>i&1];
if(!tmp) tmp=++idx;///不存在就插入
p=s;///继续往下走
}
}
int Find(int x){///查找跟x异或值最大的数
int p=0,res=0;
for(int i=30;i>=0;i--){
int tmp=x>>i&1;
if(son[p][!tmp]){
res+=1<<i;
p=son[p][!tmp];
}
else p=son[p][tmp];
}
return res;
}
3.Borůvka算法
前言：
学完后才看到这个算法的，个人感觉先理解这个算法的思想会更容易点。
Borůvka算法用于求最小生成树，时间复杂度nlogn，可以将其看成多源的prim算法。
基本思路：
一开始的时候每个点都自成一个联通块，每次给所有联通块都找一条边权最小的边，其中一端在联通块内而另一段不在，加入这些边并合并联通块，重复直到没有联通块可合并。
证明和图示过程可以参考博客。
二、【Codeforces 888G】Xor-MST （最小异或生成树）
原题链接
题意：
给2e5个点，每个点都有点权，两个点如果连边，该边权就是两个点权的异或值，求所有点组成的最小生成树。
思路：
可以借鉴Borůvka算法的思路，初始的时候，把每个点都看做是一个联通块，这样我们进行Borůvka算法的过程，对于联通块每次都找一条边权最小的边，加入这些边合并联通块，重复直到没有联通块可合并。
本题跟普通的最小生成树就是边权的设置，对于上方的黑体字过程，首先想到的肯定就是暴力枚举的思路，但显然复杂度不够优秀。简化一下问题就是最小异或对，借鉴最大异或对（前置知识2）的思路，将点权都插入Trie树，这样从根节点rt到叶子节点的一条路径就表示一个点权。
根据贪心的思想，对于一个节点来说，如果左右子树都存在，就必须找到一条边要连接左右子树，那么这条边一定会有W=1<<pos（pos为该节点所在层数）的贡献。
一个节点的最小异或生成树就是左子树的最小异或生成树+右子树的最小异或生成树+左右子树合并时的最小代价。对于前两个贡献可以递归进行计算，对于第三个贡献，就是两个子树的最小异或对+W。我们可以枚举任意一棵子树，借助Trie求异或另一颗子树的值，最后取min即可。
那么如何确定该子树里有哪些值呢？暴力dfs显然不可取，我们可以在插入前就排序，记录每个节点的左右区间，枚举的时候直接枚举区间里的数即可。
另外，借鉴并查集按秩合并的思想，可以在在合并子树时加一个小优化，每次都将小的子树合并到大的子树上，即启发式合并，可以优化几十秒吧。
最后要注意数组开大一点！
代码：
#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
///#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
#define I_int ll
#define modl 19260817*19890604-19491001
#define x first
#define y second
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char F[200];
inline void out(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
//cout<<" ";
}
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int inf=0x3f3f3f3f,mod=1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn=1e7+7,maxm=3e6+7;
ll n,a[maxn];
struct Xortrie{
int node;///节点编号
int son[maxn][2];///01字典树
int L[maxn],R[maxn];///该节点控制的左区间和右区间
void Xortrie_init(){
node=0;///初始化
}
///插入这个数 需要控制左右区间
void add(ll x,int id){
int rt=0;
for(int i=32;i>=0;i--){
///逐位分离
int tmp=(x>>i&1ll)?1:0;///判断当前位
int &tt=son[rt][tmp];///当前节点是否存在
if(!tt) tt=++node;///如果被卡内存，可以改用动态开点
rt=tt;
///如何记录一个节点控制的左右区间
if(!L[rt]) L[rt]=id;///最早的是左端点
R[rt]=id;///一直往右拓展
}
}
///询问rt从pos位开始和x异或得到的min
ll qaskpos(int rt,int pos,ll x){
ll res=0;
for(int i=pos;i>=0;i--){
int tmp=(x>>i&1ll)?1:0;///判断当前位
if(son[rt][tmp]) rt=son[rt][tmp];
else{
res+=(1ll<<i);
rt=son[rt][!tmp];
}
}
return res;
}
///分治操作 查询某子树
ll Divide(int rt,int pos){
if(son[rt][0]&&son[rt][1]){
///左右子树均存在
int x=son[rt][0],y=son[rt][1];
ll minn=INF;
///启发式合并:根据子树大小合并，小优化
if(R[x]-L[x]+1<=R[y]-L[y]+1){///如果左子树小
for(int k=L[x];k<=R[x];k++)///枚举左子树
minn=min(minn,qaskpos(y,pos-1,a[k])+(1ll<<pos));
}
else{
for(int k=L[y];k<=R[y];k++)///枚举右子树
minn=min(minn,qaskpos(x,pos-1,a[k])+(1ll<<pos));
}
return minn+Divide(x,pos-1)+Divide(y,pos-1);///左右子树合并的最小异或值+左子树的最小异或值+右子树的最小异或值
}
else if(son[rt][0]){
///只有左子树 递归
return Divide(son[rt][0],pos-1);
}
else if(son[rt][1]){
///只有右子树 递归
return Divide(son[rt][1],pos-1);
}
///叶子节点
return 0ll;
}
void debug(int rt){
printf("%d %d\n",L[rt],R[rt]);
if(son[rt][0]) debug(son[rt][0]);
if(son[rt][1]) debug(son[rt][1]);
}
}az;
int main(){
az.Xortrie_init();
n=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) az.add(a[i],i);
//// az.debug(0);
ll q=az.Divide(0,32);
out(q);
return 0;
}
三、【牛客】2020牛客暑期多校训练营（第五场）B-graph （最小异或生成树）
原题链接
题意：
给一棵树，每条边都有边权，可以任意加边和删边，但要保证图联通并且任何一个环的边权异或和为0.求最小权值和。
思路：
首先要明确的一点就是无论添加的先后顺序如何，添加两点的边大小一定是固定的。因为要保证任何一个环的边权异或和为0；我们假设a[i]为根节点rt到i节点的所有边的异或和，所以如果节点x和节点y之间连边，该边的权值是a[x]^a[y]。
所以可以把确定的和不变的边权转化为各点点权，这样问题就转化成了求最小异或生成树。
对于黑字部分可以dfs求解即可。
void dfs(int u,int fa,ll w){
a[u]=w;
for(int i=h[u];~i;i=e[i].ne){
int j=e[i].e;
if(j==fa) continue;
dfs(j,u,w^e[i].w);
}
} 具体证明 (证明超级详细的博客)
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44469783
四、杂七杂八
51Nod的相似题
学长博客 （永远滴神）
其他参考博客都在对应位置。
京公网安备 11010502036488号