题解：CF1424M Ancient Language

lgx57 · 2025-03-03 10:15:17 · 题解

一眼题。

首先把 n 页书排到一个 vector 里面。

考虑两个字符串的比较过程：

1. 逐位比较字符。如果相等，那么继续比较，否则按照字典的顺序排。
2. 如果一直比较到了其中一个字符串的结尾，那么短的字符串排在前面。

按照这样的方法，我们可以得出一些字符之间的大小关系。

考虑建图。假设字符 x 比 y 小，那么连一条 x\to y 的边。容易知道这肯定是一个 DAG。那么就可以用拓扑排序判断这个图是否为 DAG。

代码中需要注意的细节：

1. 字符串的长度也要判断。
2. 在字典中没有出现的字符不需要在结果中输出。
3. 如果最后有字典中的字符在答案中没有出现，那么也是不可能的。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define gc getchar
#define pc putchar
#define sz(v) ((int)(v.size()))
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
    int x=0,f=1;
    char ch=gc();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=gc();}
    return x*f;
}
inline void print(int x){
    if (x<0) pc('-'),x*=-1;
    if (x<10) pc(x+'0');
    else print(x/10),pc(x%10+'0');
}
const int N=1005;
vector<string> v[N];
vector<int> p[27];
int deg[N];
bool f[N];
void sol(){
    int n,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        x++;
        for (int j=1;j<=k;j++){
            string s;
            cin>>s;
            v[x].pb(s);
            for (int _=0;_<sz(s);_++) f[s[_]-'a']=1;
        }
    }
    vector<string> vv;
    for (int i=1;i<=n;i++) for (auto kk:v[i]) vv.pb(kk);
    for (int i=0;i+1<sz(vv);i++){
        string x=vv[i];
        string y=vv[i+1];
        bool ff=0;
        for (int j=0;j<min(sz(x),sz(y));j++){
            if (x[j]!=y[j]){
                p[x[j]-'a'].pb(y[j]-'a');
                deg[y[j]-'a']++;
                ff=1;
                break;
            }
        }
        if (!ff){
            if (sz(x)>sz(y)) return cout<<"IMPOSSIBLE",void();
        }
    }
    vector<int> Ans;
    queue<int> q;
    for (int i=0;i<26;i++){
        if (!f[i]) continue;
        if (!deg[i]) q.push(i);
    }
    int cnt=0;
    for (int i=0;i<26;i++) cnt+=f[i];
    while (!q.empty()){
        int u=q.front();
        q.pop();
        Ans.pb(u);
        for (int v:p[u]){
            if (!(--deg[v])) q.push(v);
        }
    }
    set<int> ss;
    for (int x:Ans){
        ss.insert(x);
    } 
    if (sz(ss)!=sz(Ans)||sz(Ans)!=cnt) return cout<<"IMPOSSIBLE",void();
    else for (int x:Ans) cout<<(char)(x+'a');
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while (t--) sol();
    return 0;
}