CF1446C 题解

题目传送门

题意简述

给定你一个序列 a（序列为互不相同的正整数），对于每个 i，它会向序列中的满足 a_i⊕a_j 最小的 j 连双向边，并且如果 j 也向 i 连了边，只算一条边。现在要让你删去序列中的一些数，使得最后形成的图是一颗树，输出最少需要删除几个数。

前置芝士

• 简单 dp 能力。

\texttt{SOLUTION}

求最小删除数十分困难，不如转过来求最大保留。

先将每个数字插入 \texttt{Trie} 树中。

因为异或值最小的两个数才会连边。

所以没删除前一定是 \texttt{Trie} 树中如下图所示的点所表示的数会连边，不难发现他们是不连通的。

要让他们变为一棵树，就就必须删除一些点。

记以 u 为根的子树中的数字连完边后为一棵树的最大保留数为 dp_u（有点拗口qwq）。

其实按上图中连边，我们已经求出了：dp_4=dp_5=dp_6=dp_7=2。

然后我们继续递归处理。

开始处理 dp_2 想要让以 4 为根的子树中的数与以 5 为根的子树连边。就必须要让两棵子树的其中一棵只保留一个数字。

为什么呢？因为 \text{Trie} 树中一个子树内任意两个数的异或值一定比一个子树内的数与一个子树外的数异或值小。

所以为了让这棵子树内的树与另一棵子树上的树连边，只能令这棵子树只留下它一个数。

于是 dp 转移出来了。

记 u 的两个儿子为 v_1,v_2。

dp_u=\left\{ \begin{aligned} 1(u\ \text{不存在儿子，即}u\text{为叶子}) \\ dp_{v_1}\ (u\text{不存在}v_2\text{儿子})\\ dp_{v_2}\ (u\text{不存在}v_1\text{儿子})\\ \max\{dp_{v_2},dp_{v_1}\}+1\ (u\text{存在两个儿子})\\ \end{aligned} \right.

列完转移发现甚至不需要记录 dp 数组。一遍递归即可解决。

\texttt{AC CODE}

#include<bits/stdc++.h>
#define IN inline

const int N=3000010;

IN int read()
{
    int x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int idx;
struct Trie_Tree{int son[2];}tr[N];
inline void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int tmp=(x>>i)&1;
        if(!tr[p].son[tmp]) tr[p].son[tmp]=++idx;
        p=tr[p].son[tmp];
    }
}
long long dp(int p)
{
    if(!tr[p].son[0]&&!tr[p].son[1]) return 1;
    if(!tr[p].son[0]&&tr[p].son[1]) return dp(tr[p].son[1]);
    if(tr[p].son[0]&&!tr[p].son[1]) return dp(tr[p].son[0]);
    return std::max(dp(tr[p].son[0]),dp(tr[p].son[1]))+1;
}
int main()
{
    int n=read();
    for(int i=1;i<=n;i++) insert(read());
    return !printf("%lld",n-dp(0));
}

欢迎提问or提出我的问题，会改的。