你说得对，但是为什么不直接排序呢？
NATO
·
2024-03-26 16:47:52
·
题解
还以为自己铂金组的号被 ban 到铜组了捏。
思路浅析：
考虑建 trie。在建树的过程中去操作。
考虑什么情况是合法的。
首先我们知道，任意从根到叶子的路径都代表一个串。其次，如果一个串 S_a 是另一个串 S_b 的前缀，必有 S_a 的终止节点是 S_b 的终止节点的祖先（包括 S_b 的终止节点本身）。
那么容易想到，所有字符串的终止节点都是叶子节点时，操作是合法的。
那么可以想到，当出现冲突的时候我们就是要继续往下走（往这个字符串后面加字符，每走一层就是插入一个字符），将一个儿子不满的节点加上一个儿子，或者是将某个叶子节点置上两个儿子（代表之前在这个叶子节点结束的字符串末尾加一个字符，当前的字符串走到这里时加另一个字符），即可。
每一次我们都可以取局部最优，但我们怎么确保全局最优？简单来说，我们插入的时候可能出现这样的问题：
已经插入 00，01，1。
现在我们再插入一个 0，那么由于存在两种最优决策（给 00 或 01 建两个儿子）它就有可能任选一种决策。而如果我们的决策是给 00 建两个儿子，那么我们如果还需要插入一个 00，我们会发现之前我们做出的决策就让当前决策变劣。我们并不知道我们当前的决策是否会影响后面的决策，就会错误决策。
因为插入字符串的顺序不影响答案，我们考虑将字符串按长度从大到小排序后插入，也可以理解成按原串建树后自底向上的递归去做，此时不会出现后效性。就用递归这个等价做法分析一下正确性：
令 f_u 为使 u 子树合法的最小操作数。考虑一个节点 u。
如果节点 u 为叶子或空节点，f_u=0。
如果节点 u 不是任意一个字符串的终止节点，那么显然不操作（也无法操作）最优：f_u=f_{lson}+f_{rson}。
如果节点 u 是某一个字符串的终止节点（暂时不考虑多个相同的串，虽然是一样的），按前面的思路，我们先将左右子树分别操作到所用操作数最小的合法状态，然后再走到深度最小的空位。如果存在更优的方案，那么就必然是这一步存在着可以走到深度严格不大于当前方案的某个位置的方案。然而深度小的部分都必然是满二叉树，否则我们当前就会到深度小的部分去。如果通过反悔之前的操作让开位置，让开的那个字符串仍然要走下去，不会更优。令 cost_u 为走到深度最小的空位的代价，则 f_u=f_{lson}+f_{rson}+cost_u。
分析一下复杂度：
只有当插入字符串结尾子树内的某一层满了的时候，我们的最优决策才需要走到下一层，否则显然在该层结束是严格不劣于在下面的某一层结束的，要卡满层数显然是让 trie 变成满二叉树，而这样显然是 \log n 层的（一个叶子节点对应一个字符串嘛），所以最坏情况下只会往下走 \log n 层，故时间复杂度是 O(n\log n+\sum\limits_{i=1}^n |s_i|) 的，空间复杂度同时间复杂度。
参考代码：
#include
#define ll long long
using namespace std;
ll n;
string s[100005];
ll res;
int cnt,tr[10000005][2],mad[10000005];
bool cmp(string a,string b)
{
return a.size()>b.size();
}
void add_more(ll now)
{
++res;
if(!tr[now][0]&&!tr[now][1])
{
res+=2;tr[now][0]=++cnt;mad[cnt]=2;tr[now][1]=++cnt;mad[cnt]=2;
mad[now]=3;
return;
}
else if(!tr[now][0])
{
++res;tr[now][0]=++cnt;mad[cnt]=2;
mad[now]=min((tr[now][0]?mad[tr[now][0]]:0),(tr[now][1]?mad[tr[now][1]]:0))+1;
return;
}
else if(!tr[now][1])
{
++res;tr[now][1]=++cnt;mad[cnt]=2;
mad[now]=min((tr[now][0]?mad[tr[now][0]]:0),(tr[now][1]?mad[tr[now][1]]:0))+1;
return;
}
else
{
if(mad[tr[now][0]]<=mad[tr[now][1]])add_more(tr[now][0]);
else add_more(tr[now][1]);
mad[now]=min((tr[now][0]?mad[tr[now][0]]:0),(tr[now][1]?mad[tr[now][1]]:0))+1;
}
}
void insert(ll now,ll sid,ll nv,bool use)
{
if(s[sid].size()==nv)
{
if(!use)
add_more(now),--res;
else mad[now]=2;
return;
}
if(!tr[now][s[sid][nv]-'0'])tr[now][s[sid][nv]-'0']=++cnt,use=1;
insert(tr[now][s[sid][nv]-'0'],sid,nv+1,use);
mad[now]=min((tr[now][0]?mad[tr[now][0]]:0),(tr[now][1]?mad[tr[now][1]]:0))+1;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(ll i=1;i<=n;++i)cin>>s[i];
sort(s+1,s+1+n,cmp);
for(ll i=1;i<=n;++i)
insert(0,i,0,0);
cout< }