题解：P11226 [COTS 2019] 排名 Vezuv

· · 题解

挺好的题。

对于每一个串，我们贪心地考虑，让这个字符串中的字母字典序尽可能靠前，也就是说如果把它和其它字符串比较的话，当遇到第一个不同字母时，它这个字母的字典序应该是更靠前的。

找第一个不同字母的操作可以用 Trie 树维护，然后对每个刚刚才思路得出的字母大小关系我们可以联想到建有向边。具体的，设当前处理的字符串为 t，我们在 Trie 树上的遍历 t，对于遍历到的每一个节点如果在 Trie 上面有其它字母的分叉，那么显然需要让 t 的这个字母向其它分叉的所有字母建有向边。

建完以后无解的情况显然就是图上有环，否则按照这张图的一个拓扑序输出节点即可。

还有一种情况就是 t 是其它字符串的一个前缀，这时显然无解，特判即可。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
    return w*s;
}
const int maxn=5e6+100;
const int mod=998244353;
const int inf=1e9+7;
int n;
string s[maxn];
int tot,tr[maxn][30];
int cnt[maxn],du[90];
vector<int> G[90];
void add(string t)
{
    int now=0;
    for(int i=0;i<t.size();i++)
    {
        int ch=t[i]-'a';
        if(!tr[now][ch])tr[now][ch]=++tot;
        now=tr[now][ch];
    }
    cnt[now]++;
}
bool ask(string t)
{
    int now=0;
    for(int i=0;i<t.size();i++)
    {
        int ch=t[i]-'a';
        if(cnt[now])return 1;
        now=tr[now][ch];
    }
    return 0;
}
void work(string t)
{
    int now=0;
    for(int i=0;i<t.size();i++)
    {
        int ch=t[i]-'a';
        for(int i=0;i<26;i++)
        {
            if(i==ch||!tr[now][i])continue;
            G[ch].push_back(i);
            du[i]++;
        }
        now=tr[now][ch];
    }
}
void topsort()
{
    queue<int> q;
    vector<char> ans;
    for(int i=0;i<26;i++)if(!du[i])q.push(i);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ans.push_back(char(u+'a'));
        for(auto y : G[u])
        {
            if(--du[y]==0)
                q.push(y);
        }   
    }
    if(ans.size()==26){for(auto i : ans)cout<<i;}
    else cout<<"nemoguce";
}
void Main(int x)
{
    for(int i=0;i<26;i++)du[i]=0,G[i].clear();
    if(ask(s[x])){puts("nemoguce");return ;}
    work(s[x]);
    topsort();
    puts("");
}
signed main()
{
#ifdef Lydic
    freopen(".in","r",stdin);
    freopen(".out","w",stdout); 
//#else
//  freopen("detect.in","r",stdin);
//  freopen("detect.out","w",stdout);
#endif
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        add(s[i]);
    }
    for(int i=1;i<=n;i++)Main(i);
    return 0;
}