题解：P10283 [USACO24OPEN] Identity Theft P

Hanghang · 2024-03-25 22:55:45 · 题解

铂金组零的突破！

虽然感觉这场难度不大，但是我分数依旧难崩。

简要题意：n 个 01 串，你可以花费 1 的代价再任意一个串的末尾加上 0 或者 1，最小化代价使得任意一个串都不是另一个串的前缀。

这种 01 串最优话问题无脑建字典树，在树上分析往往可以让问题变得简单。

如何让一个串不成为其他串的前缀呢？观察到每个点最终一定会走到某个红色节点的子树上。

红色节点分成两类，一类是字典树上的叶子，另一类是一个节点如果只有一个子树，往另一个方向去的新建节点。

我们把贡献拆成两部分，第一部分是一个节点走到某个红色节点需要的代价，第二部分是红色节点内部需要处理的代价。

第一部分是好求的，答案是 dep_x-dep_p，p 是一开始的节点，x 是走到红色节点。

第二部分，设 cnt 表示有多少个节点走到了红色节点，因为需要保证一个节点不能是另一个节点的前缀，所以我们还需要在子树内加点。

大概就是需要构造 cnt 个叶子，代价为每个叶子到根的路径和。

将 val 差分一下即可得到新加一个点所需的代价。

注意到随着节点的增加，每增加一个新的点的代价单调不降，因此考虑贪心处理。

对每个红色节点开个小根堆，再记录一个 now_x 表示当前节点已经有了 x 个点。

往小根堆里面插入 dep_x+val_{now_x+1} 表示新增一个点所需的代价。(dep 那里使用了差分，在真正的值还需减去个 dep_p)。

一个点只能去子树内的红点。所以需要支持子树合并以及删除插入元素的操作。

使用 pb_ds 即可做到 O(\sum \log \sum)，常数较小。(不会 pb_ds 的右转可以看这里)

代码：

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#define heap __gnu_pbds::priority_queue

typedef long long ll;
const int N=2e6+3;
int n,tot,ans,cnt[N],now[N],dep[N],val[N],tr[N][2];
bool vis[N];
struct Nod
{
    int x,id;
    friend bool operator <(Nod a,Nod b){return a.x>b.x;}
};
heap<Nod>q[N];
void Ins()
{
    string str;cin>>str;int p=1;
    for(int i=0;i<(int)str.size();i++)
    {
        int c=str[i]-'0';
        if(!tr[p][c])tr[p][c]=++tot;
        dep[tr[p][c]]=dep[p]+1;p=tr[p][c];
    }
    cnt[p]++;
}
#define ls tr[p][0]
#define rs tr[p][1] 
void Dfs(int p)
{
    if(vis[p]){q[p].push({dep[p]+val[1],p});return;}
    if(!ls&&!rs)
    {
        for(int i=2;i<=cnt[p];i++)ans+=val[i];
        now[p]=cnt[p];q[p].push({dep[p]+val[now[p]+1],p});return;
    }
    Dfs(ls);Dfs(rs);q[p].join(q[ls]);q[p].join(q[rs]);
    while(cnt[p]--)
    {
        Nod t=q[p].top();q[p].pop();ans+=t.x-dep[p];now[t.id]++;
        q[p].push({t.x-val[now[t.id]]+val[now[t.id]+1],t.id}); 
    }
}
int main()
{
    cin>>n;tot=1;val[2]=2;
    for(int i=3;i<N;i++)val[i]=val[(i+1)/2]+1;
    for(int i=1;i<=n;i++)Ins();
    for(int p=1;p<=tot;p++)if((!ls&&rs)||(ls&&!rs))
        !ls?ls=++tot:rs=++tot,dep[tot]=dep[p]+1,vis[tot]=1;
    Dfs(1);cout<<ans;
}