TYB电竞队选名字，第一次模拟赛，字典树最长公共前缀

2019-04-13 16:45发布

站内文章 / 模拟电子
11753 0 1133
正文      题目描述：身为电竞队队长的TYB今天要召开电竞队会议啦！由于TYB觉得再电竞队里面，叫原名不太合适，应当取一些电竞队专属名字。比如说，clearlove，PDD，狗贼叔叔，UZi，faker之类的。TYB经过冥思苦想，想到了n个十分酷炫的名字。电竞队也有恰好n个人。所以人和新的专属名字是一一对应的。现在要把这些专属名字分配给每一个同学，每一个同学分配到一个专属名字，每一个专属名字必须分配给某个同学。。大家都知道，两个名字如果比较像，就会方便记忆。现在定义专属名字和真名之间的相似度是他们之间的最长公共前缀。现在要求分配专属名字，使得匹配的相似度总和最大。

       相信大家都学过字典树，我们直接每次把一个字符串丢进字典树里面，把每个字符串的末尾标记一下(c[0][x]++   ||   c[1][x]++)，再把原名和专属名字区分开(1/0)，我们记录一下当前的深度，然后用min(c[0][当前点]，c[1][当前点])*dep(深度)累加答案，我们要的就是让深度越大越好，所以我们在回溯的时候做这个操作即可。如果多出来的怎么办，，比如说，名字有ababb,ababb , 专属名字有ababb,abacc.这时候，在ababb这个位置c[0][ababb]=2,c[1][ababb]=1。多出来的就是剩下的ababb。我们把他往它往上传递，就是将c[0][abab]++;发现这时还是不行，在往上传递.c[0][aba]++;另一边的c[1][abacc]=1也是多余的，传递上来，c[1][abac]++;c[1][aba]++;   这时候又可以加一便，答案就是1*5+1*3=5+3=8;代码<要背板子>#include #include #include #include using namespace std; int n; int son[800010][30]; int c[2][800010]; int tot; int t=0; int ans=0; char s[800010]; struct Tire{ void Clear(){tot=1;memset(son[1],0,sizeof(son[1]));memset(c,0,sizeof(c));} void Insert(char *s,int x){ int n=strlen(s); int u=1; for(int i=0;i int temp=s[i]-'a'; if(son[u][temp]==0){ son[u][temp]=++tot; memset(son[tot],0,sizeof(son[tot])); } u=son[u][temp]; } c[x][u]++; } }xx; void Find(int x,int fa,int dep){ for(int i=0;i<26;i++) if(son[x][i]!=0) Find(son[x][i],x,dep+1); ans+=min(c[0][x],c[1][x])*dep; if(c[0][x]>c[1][x])  c[0][fa]+=c[0][x]-c[1][x]; else if(c[1][x]>c[0][x]) c[1][fa]+=c[1][x]-c[0][x]; c[0][x]=c[1][x]=0; } int main(){ scanf("%d",&t); while(t--){  scanf("%d",&n); xx.Clear();   ans=0; for(int i=1;i<=n;i++){ scanf("%s",s); xx.Insert(s,0); } for(int i=1;i<=n;i++){ scanf("%s",s); xx.Insert(s,1); } Find(1,0,0); printf("%d ",ans); } }

热门文章