Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 2] M. Ancient Language

题意

给定一个共有\(n\)页的字典，每一页有\(k\)个单词

已知这本字典使用的古老语言的字母是英文字母的子集，不一定\(26\)个英文字母都被使用到

问你是否存在一种字典序满足这本字典内单词原来的排列顺序

存在的话只需要输出任意一种即可，不存在输出IMPOSSIBLE

限制

\(1\le n,k\le 1000\)

\(0\le p_i\lt 1000\)

思路

将给定的所有单词按照题意进行排序，页码小的放前，页码相同的按照输入顺序排序

然后考虑所有的相邻单词，这里以\(i,j\)来描述（\(j=i+1\)）

如果\(i,j\)两个单词相同，不考虑

如果\(i,j\)两个单词不同，且\(i\)是\(j\)的前缀，不考虑

如果\(i,j\)两个单词不同，且\(j\)是\(i\)的前缀，明显这样不可能有满足的字典序，输出IMPOSSIBLE

如果\(i,j\)两个单词不同，且不满足上述两种条件，则只看出现不同字母时下标最小的那个位置\(k\)

令\(a\)表示第\(i\)个单词下标为\(k\)的字母，令\(b\)表示第\(j\)个单词下标为\(k\)的字母

可以发现，\(a\)的字典序应该是小于\(b\)的，所以将\(26\)个英文字母看作点，将\(a\rightarrow b\)连边，同时标记\(b\)的入度\(+1\)

明显的，只有当最后产生的图是一个DAG时才存在一个解，所以我们每次找入度为\(0\)的点加入答案中即可，直接拓扑排序搜索即可

程序

(826ms/2000ms)

// StelaYuri
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define pb push_back
#define eb emplace_back
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const double angcst=PI/180.0;
const ll mod=998244353;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

struct node
{
    string s;
    int i,j; //页码、位置
    bool operator < (const node& a) const
    {
        if(i^a.i)
            return i<a.i;
        return j<a.j;
    }
}str[1000050];

int ind[30]; //入度
bool to[30][30]; //连边
bool vis[30]; //是否出现过该字母

void solve()
{
    int n,k;
    cin>>n>>k;
    
    int tot=0;
    rep(i,1,n)
    {
        int id;
        cin>>id;
        rep(j,1,k)
        {
            ++tot;
            cin>>str[tot].s;
            for(char c:str[tot].s)
                vis[c-'a']=true;
            str[tot].i=id;
            str[tot].j=j;
        }
    }
    
    sort(str+1,str+1+tot);
    
    repp(i,1,tot)
    {
        int len=min(str[i].s.size(),str[i+1].s.size());
        bool flag=false;
        repp(j,0,len)
        {
            if(str[i].s[j]!=str[i+1].s[j])
            {
                int a=str[i].s[j]-'a';
                int b=str[i+1].s[j]-'a';
                if(!to[a][b])
                    ind[b]++;
                to[a][b]=true; //a->b连边
                flag=true;
                break;
            }
        }
        if(!flag)
        {
            if(str[i].s.size()>str[i+1].s.size()) //如果i+1是i的前缀，显然不存在解
            {
                cout<<"IMPOSSIBLE\n";
                return;
            }
        }
    }
    
    int siz=0;
    repp(i,0,26)
        siz+=(vis[i]?1:0);
    
    queue<int> q;
    vector<int> ans;
    repp(i,0,26)
        if(vis[i]&&ind[i]==0) //挑选入度为0的点
            q.push(i);
    
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        ans.pb(cur);
        repp(it,0,26)
        {
            if(to[cur][it])
            {
                ind[it]--;
                if(ind[it]==0)
                    q.push(it);
            }
        }
    }
    
    if(ans.size()!=siz)
    {
        cout<<"IMPOSSIBLE\n";
        return;
    }
    
    for(int it:ans)
        cout<<char(it+'a');
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}