题目概述

CF1446C

解题报告

画下Trie树，不难发现如果一个节点 $0$ 子树中只有一个元素，$1$ 子树中只有一个元素，那么这两个元素就会形成重边。由于题目要求形成一棵树，因此重边必须有且只有一个。

那么，如果一个节点 $0$ 子树中有 $\ge 2$ 个元素，并且 $1$ 子树中有 $\ge 2$ 个元素，显然是违法的，因为该节点子树中一定存在至少两个重边。因此，每个节点要么 $0$ 子树为空或 $1$ 子树为空，要么 $0$ 子树只有一个元素或 $1$ 子树只有一个元素，这样才合法。

考虑DP，定义 $f_i$ 表示 $i$ 子树最多能保留多少元素，那么：

• $0$ 子树为空：$f_i=f_{son_{i,1}}$
• $1$ 子树为空：$f_i=f_{son_{i,0}}$
• $0$ 子树 $1$ 子树不为空：$f_i=\max\{f_{son_{i,0}},f_{son_{i,1}}\}+1$（另一边可以保留一个）

最后答案为 $n-f_{root}$ 。

不过，实现的时候可以不用建Trie，只要将元素从小到大排序，然后按位递归就行了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200000;

int n,a[maxn+5];

int Solve(int L,int R,int k){
    if (!k){
        int mid;for (mid=L;mid<=R && !(a[mid]>>k&1);mid++);mid--;
        if (mid<L || mid+1>R) return 1;return 2;
    }
    int mid;for (mid=L;mid<=R && !(a[mid]>>k&1);mid++);mid--;
    if (mid<L || mid+1>R) return Solve(L,R,k-1);
    return max(Solve(L,mid,k-1),Solve(mid+1,R,k-1))+1;
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);printf("%d\n",n-Solve(1,n,30));return 0;
}