CF1446C Xor Tree

作者: MayFlyyh 分类: Trie 发布时间: 2020-11-18 16:59 ė 6 没有评论

CF1446C Xor Tree

对于每个点i,找到j≠ia_j xor a_i最小,连边(i,j)

如果连边之后形成一棵树,那么称{a_i}为合法的。

给出{a_i},求至少删掉多少个点才合法。

n≤2∗10^5

a_i互不相同

考虑到序列中 n 个点产生的 n 条边,必然有重合的两条边(异或值最小的点对产生的两条边),故一个序列不可能连接成一个简单环(最多有 n-1 条边),那么就考虑怎么删除最少的点能够把连通块合并。

考虑将每个数字插入 01Trie

显然,每个点会和一个和最近的一个点连边(因为每个点深度一样,在 01Trie 上,最近的点一定是和这个点异或值最小的点)

Trie 上,找一点 X 与某点 Y ,使它们的 BIT 位拥有最长公共前缀,那么 X 即为 Y 距离最近的点

因为它们的 BIT 位拥有最长公共前缀,所以在所有的点中 X ,与 Y 的异或值最小。

那么如果某个节点的两个儿子的大小都大于 2,就说明两个儿子的内部各自形成了连通块

那么必须把一个子树的点删成仅剩1个节点,才能与另一个儿子合并成一个连通块。

直接在最小的子树保留一个点,其他的都删了就好,直接一遍dfs

#include<bits/stdc++.h>
const int N = 1e7+10;
int trie[N][2],rt=1,cnt=1;
int end[N],size[N];
int a[N],n;
int b[40],ans;
void insert(){
    int nw=rt;
    for(int i=1;i<=31;++i){
        if(!trie[nw][b[i]])
            trie[nw][b[i]]=++cnt;
        nw=trie[nw][b[i]];
    }
    end[nw]++;
}
void dfs(int x){
    size[x]=end[x];
    if(end[x]) return ;
    for(int i=0;i<=1;++i){
        if(trie[x][i])
            dfs(trie[x][i]);
        size[x]+=size[trie[x][i]];
    }
    //printf("%d %d\n",x,size[x]);
    if(size[trie[x][0]]>=2&&size[trie[x][1]]>=2){
        ans+=std::min(size[trie[x][0]]-1,size[trie[x][1]]-1);
        size[x]=std::max(size[trie[x][0]],size[trie[x][1]])+1;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        for(int j=1;j<=31;++j){
            b[31-j+1]=a[i]&1;
            a[i]>>=1;
        }
        insert();
    }
    dfs(rt);
    printf("%d",ans);
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/697

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部