T1
题面
解题
- 与字典序有关，考虑字典树。
- 考虑如何获得答案。贪心，按字典序由小到大的顺序遍历字典树，然后判断以当前节点为结尾的字符串是否为答案。
- 判断以某个节点为结尾的字符串是否为答案的方式如下图。
- 时间复杂度为 \(\mathcal O(\sum|w|)\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxw=1e6+10;
int nxt[maxw][26],cnt,sz[maxw],tot[maxw];
int n,k,rt;
char s[maxw];
void build()
{
int now=rt,len=strlen(s+1);
tot[now]++;
for(int i=1;i<=len;i++)
{
int c=s[i]-'a';
if(!nxt[now][c]) nxt[now][c]=++cnt;
tot[now=nxt[now][c]]++;
}
sz[now]++;
}
void solve()
{
scanf("%d%d",&n,&k);
rt=++cnt;
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
build();
}
int now=rt;
while(true)
{
int t=sz[now];
for(int i=0;i<26;i++)
if(tot[nxt[now][i]]) t++;
if(t>=k)
{
if(now==rt) printf("EMPTY");
printf("\n");
return;
}
for(int i=0;i<26;i++)
{
if(tot[nxt[now][i]]==0) continue;
t+=-1+tot[nxt[now][i]];
if(t>=k)
{
k-=(t-tot[nxt[now][i]]);
printf("%c",'a'+i);
now=nxt[now][i];break;
}
}
}
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
return 0;
}