题解 CF510C【Fox and Names】
Enterpr1se
2021-02-25 10:11:55
>~~没有图，就要创造图。~~
~~——鲁迅~~
看到这题我首先想到的算法是Floyd【我们老师当时教的是如果需要比较多个数（1000 个以下），大概率是使用 Floyd】，但是算法标签并没有Floyd（尽管如此一会你们就会发现 Floyd 真的很有用），反倒是有一个“拓扑排序”。但是无论哪种算法都需要我们先建图，这下整道题的逻辑就基本清楚了。
~~（秦风式战术停顿）~~
但事实真的如此吗？
其实字典序中有很多不容易被注意到的小细节，所以我们在开始做题之前，不妨先看看[字典序的定义](https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E5%BA%8F/7786229)。其中比较方法如下（至于我为啥要写这么基础的东西，看到后面就知道了）：
>对于两个长度分别为 $n$ 和 $m$ 的字符串 $a$ 和 $b$，
>+ 首先比较 $a_1$ 和 $b_1$，若 $a_1$ 在字母表中比 $b_1$ 更靠前，则 $a$ 比 $b$ 更靠前。
>+ 若 $a_1 = b_1 $，则比较字符串 $\{a_1,a_2,a_3,...,a_n\}$ 和字符串 $\{b_1,b_2,b_3,...,b_m\}$。
>特判：
>+ 若 $a=\{b_1,b_2,b_3,...,b_n\}$，则 $a$ 比 $b$ 更靠前。
反过来，我们就可以得到通过字典序求字母表的过程：
>对于两个长度分别为 $n$ 和 $m$ 的字符串 $a$ 和 $b$，
>+ 首先比较 $a_1$ 和 $b_1$，若 $a$ 比 $b$ 更靠前，则 $a_1$ 在字母表中比 $b_1$ 更靠前。
>+ 若 $a_1 = b_1 $，则比较字符串 $\{a_1,a_2,a_3,...,a_n\}$ 和字符串 $\{b_1,b_2,b_3,...,b_m\}$。
由此我们就可以得到第一段代码：求字母间关系：
```cpp
void getrel(string a,string b){
if(!a.length() || !b.length()) return;
if(a[0]==b[0]){
if(a.length()>1 && b.length()>1) getrel(a.substr(1),b.substr(1));
return;
}
add(a[0],b[0]);
return;
}
```
接着我们再来看~~骗分助手~~ `Impossible` 的成因，无非三种：
+ Case 1：得出结论中字母 $letter_a$ 比 $letter_b$ 靠前，且 $letter_b$ 比 $letter_a$ 靠前。
+ Case 2：得出结论中 $letter_a$ 比其本身更靠前。
+ Case 3：字符串 `a.substr(0,x)` （$x<length(a)$）比字符串 `a` 更靠前。（这一点困扰了我这个蒟蒻将近半个小时）
接下来整段代码的逻辑就出来了：
1. 输入，判断是否存在 Case 3
2. 链式前向星上建图（上面已经贴了代码）
3. 将链式前向星上的图转换到一个矩阵上（方便运行 Floyd） 并统计出度（方便运行拓扑排序）
4. 通过Floyd找出所有可以推出的字母关系
5. 在矩阵中判断是否有 Case 1 和 Case 2
6. 运行拓扑排序，找到一组解
完整代码：
```cpp
//Luogu-CF510C Solution Version 题解版本
//Luogu @W53729 (Userid 363523)
//@_Qijia (Userid 363524) AK IOI!
#include<iostream>
#include<string>
#include<queue>
#define regll register long long
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
_Qijia AK IOI;//大佬保佑我AC（？
int n,last[300],rcnt,ind[300];
string name[105],ans;
bool rel[300][300];
char curr,targ;
queue<char> qu;
struct edge{
char to;
int prev;
} fig[10005];
void add(int s,int e){
++rcnt;
fig[rcnt]={e,last[s]};
last[s]=rcnt;
}
void getrel(string a,string b){
if(!a.length() || !b.length()) return;
if(a[0]==b[0]){
if(a.length()>1 && b.length()>1) getrel(a.substr(1),b.substr(1));
return;
}
add(a[0],b[0]);
return;
}
void trans(){
for(char i='a';i<='z';++i)
for(regint j=last[i];j;j=fig[j].prev){
rel[i][fig[j].to]=true;
++ind[fig[j].to];
}
return;
}
void floyd(){
for(char k='a';k<='z';++k)
for(char i='a';i<='z';++i)
for(char j='a';j<='z';++j)
if(rel[i][k] && rel[k][j]) rel[i][j]=true;
return;
}
signed main(){
ios::sync_with_stdio(false);//加速黑科技
//Step 1
cin>>n;
for(regint i=1;i<=n;++i) cin>>name[i];
for(regint i=1;i<=n-1;++i){
if(name[i].length()>name[i+1].length() && name[i+1]==name[i].substr(0,name[i+1].length())){
cout<<"Impossible";
return 0;
}
}
//Step 2
for(regint i=1;i<=n;++i)
for(regint j=i+1;j<=n;++j)
getrel(name[i],name[j]);
//Step 3
trans();
//Step 4
floyd();
//Step 5
for(char i='a';i<='z';++i)
for(char j=i+1;j<='z';++j)
if(rel[i][j] && rel[j][i]){
cout<<"Impossible";
return 0;
}
for(char i='a';i<='z';++i)
if(rel[i][i]){
cout<<"Impossible";
return 0;
}
//Step 6
for(char i='a';i<='z';++i)
if(!ind[i]) qu.push(i);
while(qu.size()){
curr=qu.front();
qu.pop();
cout<<curr;
for(regint j=last[curr];j;j=fig[j].prev){
targ=fig[j].to;
--ind[targ];
if(!ind[targ]) qu.push(targ);
}
}
return 0;
}
```