题解：P9694 [GDCPC 2023] New but Nostalgic Problem
my_dream666
·
·
题解
前言
题目传送门。
做此题时被题意搞得晕头转向，毫无思路，故作此题解。
题意说明
给定 n 个字符串 s_1,s_2\dots s_n，从中选取 k 个， 令 \operatorname{lcp}(s_i,s_j) 为 s_i,s_j 的最长公共前缀。
在一次选取的 k 个字符串中，又定义 V 为所选的字符串集合，则有字符串 S 为：
S=\max_{i\in V,j\in V,i\neq j}\operatorname{lcp}(s_i,s_j)
最后要将 $S$ 的字典序最小化。
:::info[字典序]
将两个字符串从头开始比较，如果有一个字符串小，那么这个字符串字典序就小，如果相等，那么就比较下一位。
如果比较到某一位超出了其中一个字符串的长度，那么那个短的字符串的字典序小（即空的字典序小）。
:::
## 做法
题目就是要我们求最大值的最小值。
这题方法比较巧妙，~~套路地~~将题目转化成判定性问题。
从头开始枚举每一位字符是什么。
假设枚举到了第 $i$ 位，在这一位中需要选出 $x$ 个字符串，我们的操作步骤是这样的：
- $\texttt{a}\dots\texttt{z}$ 遍历一遍，如果有字符串包含，那么 $x$ 就减 $1$，到最后如果 $x\leq0$，就 `return`，这位的答案为空。
因为我们可以在 $\texttt{a}\dots\texttt{z}$ 有字符串的每个选一个，在这一位他们的公共前缀为空，因为空的字典序最小，那么答案就到此为止了，否则进行下一步操作。
- $\texttt{a}\dots\texttt{z}$ 遍历一遍，如果有 $y(y\neq 0)$ 个字符串包含，在原来的基础上 $x$ 减去 $y-1$（因为先前减去了一个 $1$），如果此时 $x\leq 0$，就将 $x$ 加上 $y$，记录这一位的字符，枚举下一位。
因为例如我们枚举到了 $\texttt{e}$，那么 $\texttt{a}\dots\texttt{d}$ 肯定都全部选，所以减去，然后到了 $\texttt{e}$ 就够了，所以这意味这一位答案为 $\texttt{e}$。
接下来就要看下一位在 $\texttt{e}$ 的基础上怎么选了，而且在 $\texttt{e}$ 的基础上要选的数量就是原来的 $x$ 减去 $\texttt{a}\dots\texttt{d}$ 全选的，再减去 $\texttt{f}\dots\texttt{z}$ 有的话选一个的（第一步）。所以要加上 $y$。（实际写代码的时候可以简化一些，例如先判断，就可以少一些加减）
还有一个小细节，引用上面的例子，如果有字符串就是在第 $i$ 位，以 $\texttt{e}$ 结尾，那么它肯定要选，但是在下一位我们没有考虑也没有办法考虑它的贡献，所以我们在 $\texttt{e}$ 的时候就要减去它，因为必选它肯定是优的。
最后就做完了。
:::info[code]
```c
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e6+10;
const int S=26;
int trie[N][S],word[N],last[N],idx,len;
char s[N];
vector <char> ans;
void read()
{
return ;
}
template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
read(args...);
}
void read_char()
{
len=0;
char ch=getchar();
while(ch<'a'||ch>'z') ch=getchar();
while(ch>='a'&&ch<='z')
{
s[++len]=ch;
ch=getchar();
}
}
void insert()
{
int p=0;
for(int i=1;i<=len;i++)
{
if(!trie[p][s[i]-'a']) trie[p][s[i]-'a']=++idx;
p=trie[p][s[i]-'a'];
word[p]++;
}
last[p]++;
}
void cal(int x)
{
int p=0,sum=0;
for(int i=1;;i++)
{
for(int j=0;j<S;j++) //第一步
if(word[trie[p][j]]) sum++;
if(sum>=x) return ;
x-=sum;
for(int j=0;j<S;j++) //第二步
{
if(word[trie[p][j]]-1>=x)
{
ans.push_back('a'+j);
p=trie[p][j];
sum=0;
x++; //计算下一位要选的数量
x-=last[p]; //计算以它结尾的字符串的贡献
break;
}
else if(word[trie[p][j]]>1) x-=word[trie[p][j]]-1; //不要忘了这一步
}
}
}
void solve()
{
ans.clear();
for(int i=0;i<=idx;i++)
{
word[i]=last[i]=0;
for(int j=0;j<S;j++) trie[i][j]=0;
}
idx=0;
int n,m;
read(n,m);
for(int i=1;i<=n;i++)
{
read_char();
insert();
}
cal(m);
if(!ans.empty())
{
for(int i=0;i<ans.size();i++) putchar(ans[i]);
putchar('\n');
}
else puts("EMPTY");
}
int main()
{
int t;
read(t);
while(t)
{
solve();
t--;
}
return 0;
}
```
:::
## 后记
此题的方法还是比较巧妙，想到字典树是自然的，但是枚举答案转化成判定性问题还是有一定思维。