题解 CF1446C 【Xor Tree】

· · 题解

遇到这种求最小删除数的题目，都可以转化为求最大保留数。

将题目的题意转化一下，保留最多的数，令只存在一对 (i,j) 对彼此而言 a_i\oplus a_j 的值都是最小的。

自然想到 \text{trie}。把所有数插入进 \text{trie} 里，递归考虑 \text{trie} 的一棵子树 x，记令子树 x 合法的最大保留数为 f_x，子树 x 的左右儿子对应的是二进制意义下的第 k 位。

那么当子树 x 只存在左/右儿子时，f_x 的值就是左右儿子的值。否则就是左儿子的 f 值与右儿子的 f 值取 \max 再 +1。怎么理解呢？在第 k 位之前，对应位的值都相同，仅第 k 位不相同，保留左右子树中的一棵，再保留其余子树的一个节点，一定就能确保当前子树内只存在一对上述的 (i,j)。

最后答案就是 n-f_{rt}。时间复杂度为 O(n \log n)。

#include<cstdio>
int rt=1,tot=1;
int a[200005],ch[4000005][2];
inline int read() {
    register int x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline int max(const int &x,const int &y) {return x>y? x:y;}
inline void insert(int val) {                        
    int p=rt;
    for(register int i=30;i>=0;--i) {
        int cur=val>>i&1;
        if(!ch[p][cur]) ch[p][cur]=++tot;
        p=ch[p][cur];
    }
}
inline int GetMaxPoint(int p) {
    if(!ch[p][0]&&!ch[p][1]) return 1;
    if(!ch[p][0]) return GetMaxPoint(ch[p][1]);
    if(!ch[p][1]) return GetMaxPoint(ch[p][0]);
    return max(GetMaxPoint(ch[p][0]),GetMaxPoint(ch[p][1]))+1;
}
int main() {
    int n=read();
    for(register int i=1;i<=n;++i) insert(a[i]=read());
    printf("%d\n",n-GetMaxPoint(rt));
    return 0;
}