9.9未完成

usaco24openP1. Identity Theft

题意：

给一些 01 串，现在你每一次操作都可以往其中一个 01 串的摸末尾添加一个数字。问至少需要多少次操作才可以让任意一个串都不是其他串的前缀。

题解:

我们先建一颗 trie 出来，发现我们对一些现在不满足要求的串操作，可以选择把这个串 \(S\) 添加成两种可能。

• 在子树中选择一个度数为 \(1\) 的点，把串 \(S\) 添加到这个点的空的儿子上，代价为 \(dep\) 差值 \(+1\)。而且此时同时创造了一个叶子。
• 在子树中选择一个满足要求的串 \(X\)，然后把这个串和 \(S\) 分别挂到原来 \(X\) 叶子上的两个空儿子上代价为 \(dep\) 差值 \(+2\)。而且此时同时创造了两个叶子。

显然我们贪心的选择所有代价中最小的。用堆来维护代价。合并的时候启发式合并即可。\(\Theta(\sum|s_i|\log N)\).

code:

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef pair<int,int> Pair;
const int Maxn=1e6;
int n,ans,tot,t[Maxn+5][2],cnt[Maxn+5],dep[Maxn+5];
priority_queue<Pair,vector<Pair>,greater<Pair>> q[Maxn+5];
inline void Insert(){string s;cin>>s;int p=0;for(auto i:s){if(!t[p][i-'0']) t[p][i-'0']=++tot,dep[tot]=dep[p]+1;p=t[p][i-'0'];} cnt[p]++;
}
inline void dfs(int x){int a=t[x][0],b=t[x][1];if(a) dfs(a); if(b) dfs(b);if(!a && !b) q[x].emplace(dep[x]+2,1),cnt[x]--;else if(!a || !b) swap(q[x],q[a+b]),q[x].emplace(dep[x]+1,2);else{if(q[a].size()<q[b].size()) swap(a,b);swap(q[x],q[a]); while(!q[b].empty())q[x].push(q[b].top()),q[b].pop();}while(cnt[x]--){auto [k,id]=q[x].top(); q[x].pop(),ans+=(k-dep[x]);if(id==1) q[x].emplace(k+1,1),q[x].emplace(k+1,1);else q[x].emplace(k+2,1);}
}int main(){cin>>n; For(i,1,n) Insert();dfs(0); cout<<ans<<endl;return 0;
}