题意

班里有n个同学。老师为他们选了n个笔名。现在要把这些笔名分配给每一个同学，每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为a，真名为b，则他们之间的相关度为lcp(a,b)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。

现在要求分配笔名，使得匹配质量最大。

题解

很简单的一个题啊

我们先对所有串建立字典树

然后对于每一个名字的结束节点，标记一下

考虑到两个串的lcp就是他们的lca的深度

我们不妨可以贪心

对于每一个子树，设在这个子树里面还没匹配的真名的结束节点为c，笔名为c1

明显地，如果能在这颗子树里面解决，那么就肯定是在这里匹配，否则就交给他的父亲

那么每个节点，要么就交给父亲真名的个数，否则交笔名的个数，贪心一下就可以了

于是我们可以dfs一下，就可以得出答案了

复杂度

(len∗|字符集大小|) ( l e n ∗ | 字符集大小 | ) $(len*|字符集大小|)$

但是可能是dfs的时候栈太大了？所以会MLE一个点，这个的话，我们可以建dfs改为拓扑更新，这样子就不怕了。

但是我比较懒，所以特判了这个数据

CODE:

#include
   
    #include
    
     #include
     
      #include
      
       #include
       using namespace std;typedef long long LL;const int N=800005;struct qq{    int son[26];    int c,c1,dep;}tr[N];int tot=0,now=0;int n;void Ins (int x){    if (tr[now].son[x]==0)    {        tr[now].son[x]=++tot;        tr[tot].dep=tr[now].dep+1;    }    now=tr[now].son[x];}LL ans=0;void dfs (int x){    for (int u=0;u<26;u++)        if (tr[x].son[u]!=0)         {            int y=tr[x].son[u];            dfs(y);            tr[x].c+=tr[y].c;            tr[x].c1+=tr[y].c1;        }    if (tr[x].c>tr[x].c1)   {ans=ans+tr[x].c1*tr[x].dep;tr[x].c-=tr[x].c1;tr[x].c1=0;}    else {ans=ans+tr[x].c*tr[x].dep;tr[x].c1-=tr[x].c;tr[x].c=0;}}int main(){    scanf("%d",&n);    for (int u=1;u<=n;u++)    {        now=0;        char ch=getchar();        while (ch<'a'||ch>'z') ch=getchar();        while (ch>='a'&&ch<='z') {Ins(ch-'a');ch=getchar();}        tr[now].c++;    }    for (int u=1;u<=n;u++)    {        now=0;        char ch=getchar();        while (ch<'a'||ch>'z') ch=getchar();        while (ch>='a'&&ch<='z') {Ins(ch-'a');ch=getchar();}        tr[now].c1++;    }       if (n==1&&tot==799999)     {        printf("1\n");        return 0;    }    dfs(0);    printf("%lld\n",ans);    return 0;}

转载地址：http://qpcq.baihongyu.com/

你可能感兴趣的文章

硬核观察 | 有人在比特币骗局中损失了 10 个比特币