【题解 && Trie树 && 字符串】 C - New but Nostalgic Problem

发布时间:2024年01月19日

题目描述:

在这里插入图片描述


分析:

题目中涉及到了若干字符串的公共前缀,显然可以用trie树去完成
建立trie树的同时,我们为了做题方便,用以下两个数组去记录一下trie树的信息:
t o t i tot_i toti?表示以i为根的子树中有几个字符串, n u m i num_i numi?表示以i结尾的字符串有几个

建立完trie树之后,就开始了解决问题的过程

题目中要我们找所有公共前缀的最小值
所以我们只需要从小到大枚举公共前缀,看当前公共前缀能否由k个字符串组合得到即可。

我们一层一层从小到大枚举。
假设当前公共前缀已经枚举到了 a b c abc abc
那么接下来就有两种情况:
第一种情况就是答案就是abc
第二种情况是答案是abc*

什么情况下,答案是abc呢?
首先,答案已经确定了至少有abc,也就是说目前挑选出的几个字符串中都是以abc打头的,可能就是abc,也可能是abc[a-z]
答案的第一部分贡献就是abc的个数 c n t 1 cnt1 cnt1
第二部分贡献就是abc[a-z]的个数 c n t 2 cnt2 cnt2
但是我们需要注意:这些abc[a-z]我们可以全部取吗?
显然是不行的,对于每一种情况,我们至多取一个字符串
不然,答案就会出现变化。
比如,我们取了两个abca,那么答案显然就变成了abca
所以,在答案不改变的情况下,我们对于每种情况至多只能取出一个字符串

当cnt1+cnt2>=k时,说明我们能找出至少k个字符串,使得他们的前缀是abc,这个时候答案确定。

但是当 c n t 1 + c n t 2 < k cnt1+cnt2<k cnt1+cnt2<k时,说明答案应该是abc*,我们要继续往后面找
这个时候就没有上述的限制了(每种只能取一个),我们每种可以取若干个,同理,我们也是从小到大枚举,找到合适的那个字符(第一个字符串的和>=k的地方),而后按照上述的方式检验是否可行即可


Code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int ch[N][26];
int num[N],tot[N];
int n,k;
int cnt = 0;

void Add(string s){
	int now = 1; tot[now]++;
	for (int i = 0; i < s.size(); i++){
		int x = s[i]-'a';
		if (ch[now][x] == 0){
			ch[now][x] = ++cnt;
			memset(ch[cnt],0,sizeof ch[cnt]);
		}
		now = ch[now][x]; tot[now]++;
	}
	num[now]++;
}

void Work(){
	scanf("%d %d",&n,&k);
	cnt = 1;
	memset(ch[1],0,sizeof ch[1]);
	tot[1] = 0 , num[1] = 0;
	for (int i = 1; i <= n; i++){
		string s; cin>>s;
		Add(s);
	}
	int now = 1;
	while (1){
		int nowt = num[now];
		for (int i = 0; i < 26; i++)
		  if (tot[ch[now][i]]) nowt++;
		if (nowt >= k){
			if (now == 1) {cout<<"EMPTY";}
			for (int i = 1; i <= cnt; i++) tot[i] = 0,num[i] = 0;
			cout<<endl; return;
		}
		for (int i = 0; i < 26; i++){
			if (tot[ch[now][i]] == 0) continue;
			nowt = nowt+tot[ch[now][i]]-1;
			if (nowt >= k){
				k = k-(nowt-tot[ch[now][i]]);
				cout<<(char)(97+i);
				now = ch[now][i];
				break;
			}
		}
	}
	return;
}

int main(){
	int t;
	scanf("%d",&t);
	while (t--) Work();
	return 0;
}
文章来源:https://blog.csdn.net/huang_ke_hai/article/details/135701033
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。