CF888G Xor-MST

题意翻译

给定一个\(n\)个节点的完全图，每个节点有个编号\(a_i\),节点\(i\)和节点\(j\)之间边的权值为\(a_i\ xor\ a_j\),求该图的最小生成树的权值和。

说明

\(1\le n \le 200000,0\le a_i< 2^{30}\)

有一种B开头的MST算法

大致流程是这样的

当前每个集合伸出去一条最短的边，然后把联通块缩成一个新的集合，因为每次缩集合个数减半，所以复杂度对。

事实上基本不会让我们真去写它，有时候需要用这种方法或者思想处理处MST。

比如这个题就可以这么做，每次合并实际上对trie树做启发式合并，然后在里面查一下最小值。

然后有一种神奇的思路，这里sto attack巨佬

发现每次合并的集合都是最高位的1不同的两个集合进行合并，于是可以从上往下做，从最高位把集合分开，然后查询两个集合的最小连边。

如果我们把所有元素按从小到大排序加入trie，那么一个集合内的元素就在一个连续的区间里啦

这样我们就可以非常方便的直接遍历一遍字典树统计出答案了

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

using std::min;

using std::max;

const int N=2e5+10;

const int inf=0x3f3f3f3f;

#define ls ch[now][0]

#define rs ch[now][1]

int L[N*40],R[N*40],ch[N*40][2],tot;

int n,a[N],root;

void Insert(int &now,int x,int dep)

{

    if(!now) now=++tot;

    L[now]=min(L[now],x),R[now]=max(R[now],x);

    if(dep<0) return;

    int bit=a[x]>>dep&1;

    Insert(ch[now][bit],x,dep-1);

}

int query(int now,int val,int dep)

{

    if(dep<0) return 0;

    int bit=val>>dep&1;

    if(ch[now][bit]) return query(ch[now][bit],val,dep-1);

    else return query(ch[now][bit^1],val,dep-1)+(1<<dep);

}

ll dfs(int now,int dep)

{

    if(dep<0) return 0;

    if(R[ls]&&R[rs])

    {

        int mi=inf;

        for(int i=L[ls];i<=R[ls];i++) mi=min(mi,query(rs,a[i],dep-1));

        return dfs(ls,dep-1)+dfs(rs,dep-1)+mi+(1<<dep);

    }

    if(R[ls]) return dfs(ls,dep-1);

    if(R[rs]) return dfs(rs,dep-1);

    return 0;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",a+i);

    std::sort(a+1,a+1+n);

    memset(L,0x3f,sizeof(L));

    for(int i=1;i<=n;i++) Insert(root,i,30);

    printf("%lld\n",dfs(root,30));

    return 0;

}

2019.1.4

巴特西

CF888G Xor-MST 解题报告

CF888G Xor-MST

题意翻译

说明

最新文章

热门文章