CCYL Membership Activist

题解 CF510C【Fox and Names】

2021-02-25 10:11:55


没有图,就要创造图。
——鲁迅

看到这题我首先想到的算法是Floyd【我们老师当时教的是如果需要比较多个数(1000 个以下),大概率是使用 Floyd】,但是算法标签并没有Floyd(尽管如此一会你们就会发现 Floyd 真的很有用),反倒是有一个“拓扑排序”。但是无论哪种算法都需要我们先建图,这下整道题的逻辑就基本清楚了。
(秦风式战术停顿)
但事实真的如此吗?
其实字典序中有很多不容易被注意到的小细节,所以我们在开始做题之前,不妨先看看字典序的定义。其中比较方法如下(至于我为啥要写这么基础的东西,看到后面就知道了):

对于两个长度分别为 $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\}$。

由此我们就可以得到第一段代码:求字母间关系:

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. 运行拓扑排序,找到一组解
    完整代码:

    //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;
    }