CF1285D 【Dr. Evil Underscores】题解

非常容易就能想到 01trie 的做法，首先建立一颗字符集只有 $0$ 和 $1$ 的 trie，然后把所有的数按位拆开插入进去。考虑树形 dp，记 $f_i$ 为树上节点 $i$ 子树上的最小异或值最大的数。

记两个儿子节点的编号分别为 $x$，$y$，当前位位权为 $w$，那么转移方程就是：

$$f_i=\begin{cases}
1 &i \text{ 无子结点}\\
f_x &i \text{ 只有 } 0 \text{ 节点}\\
f_y &i \text{ 只有 } 1 \text{ 节点}\\
\min\{f_x+f_y\}+w &i \text{ 两节点均有}
\end{cases}
$$

代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
constexpr long long N=1e6,M=30;
ull n,m,k,son[8*N+5][2],
w[N+5],ans=0,dp[N+5],cnt=1;
void ins(ull v)
{
    ull tmp=1;
    for(long long i=M;i>=0;i--)
    {
        ull to=!!(v&(1ull<<i));//!!强转为bool
        if(!son[tmp][to])
        {
            son[tmp][to]=++cnt;
        }
        tmp=son[tmp][to];
    }
}
void dfs(ull rt,ull dep=1)
{
    ull x=(!!son[rt][1])+2*(!!son[rt][0]),y=1ull<<(M-dep+1);
    // cout<<bitset<2>(x)<<endl;
    if(!x) 
    {
        dp[rt]=0;
        return;
    }
    else dp[rt]=INT_MAX+1e5;
    if(x==3)
    {
        dfs(son[rt][1],dep+1);dfs(son[rt][0],dep+1);
        dp[rt]=min(dp[son[rt][0]]+y,dp[son[rt][1]]+y);
    }
    else if(x==2) dfs(son[rt][0],dep+1),dp[rt]=dp[son[rt][0]];
    else if(x==1) dfs(son[rt][1],dep+1),dp[rt]=dp[son[rt][1]];
    return ;
}
int main()
{
    // freopen("asdfjaisd.in","r",stdin);
    // freopen("asdfjaisd.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        ins(w[i]);
    }
    dfs(1);
    cout<<dp[1];
    return 0;
}
```

记得空间开大一点

正在渲染内容...

CF1285D 【Dr. Evil Underscores】 题解

CF1285D 【Dr. Evil Underscores】题解