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

正文

      题目描述：身为电竞队队长的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\n",ans);
	}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！