[题解][COCI2010-2011#6] ABECEDA

题目链接

题目

人们发现一份字典序未知的单词表。其中共包含 n 个单词。

虽然不知道具体的字典序,但大家已知这些单词在单词表上是按照字典序排列的。

你需要求出这份单词表所依照哪种字典序。

思路

同样是一份字典树的写法,不过对于内部处理还是比较暴力的

对于字符串根据字典序依次加入字典树的时候,如果走到了那个结点看看有多少已经存在的兄弟结点,那么这些的字母的字典序必然较小,因此我可以让字典序小的结点向字典序打的结点连一条边,

#include <bits/stdc++.h>
using namespace std;
int tot;
int trie[10005][27], r[30]; // 字典树数组,计算建图后每个字母的入读

bool e[30][30], c[30]; // e数组存图, c数组表示这个字母是否出现
void insert(string s)
{
    int len = Len(s), p = 0;
    for(int i = 0; i < len ; i ++)
    {
        c[s[i] - 'a'] = true; // 后面s[i] - 'a'这种就用idx(s[i])表示了
        for(int j = 0 ; j < 26 ; j ++) if(trie[p][j]) e[j][idx(s[i])] = true; // 看看加入这个字母前是不是有字典序更低的 
        if(!trie[p][idx(s[i])]) trie[p][idx(s[i])] = ++ tot; p = trie[p][idx(s[i])]; // 字典树模板 
    } 
} 
int32_t main() { 
    int n; cin >> n;
    for(int i = 1 ; i <= n ; i ++) { string s; cin >> s;
        insert(s);
    }
    for(int i = 0 ; i < 26 ; i ++) e[i][i] = false; // 之间删除自环的存在
    for(int i = 0 ; i < 26 ; i ++)
        for(int j = 0 ; j < 26 ; j ++)
            if(e[i][j]) r[j] ++; // 如果有字典序小的指向字典序大的边时,字典序较大的字母入度+1
    queue  q, ans; // q 用来拓扑排序, ans记录答案
    for(int i = 0 ; i < 26 ; i ++) if(c[i] && !r[i]) q.push(i); // 查看有多少个入度为零的,并且存在过的字母 int flag = 0; // flag=0 表示有唯一解 =1 表示存在多组解 =2表示无解 if(Len(q) > 1) flag = 1; //如果存在某一个时刻入度为零,那么这些字典序的排列无法确定清楚
    while(!q.empty())
    {
        int Q = q.front(); q.pop();
        ans.push(Q); // 有唯一解的情况下, q里面一定只会有一个,并且按照在q中的先后顺序是真实的字典序排列
        for(int i = 0 ; i < 26 ; i ++) { if(e[Q][i]) r[i] --; if(e[Q][i] && !r[i]) q.push(i); } if(Len(q) > 1) flag = 1; // 同上
    }
    for(int i = 0 ; i < 26 ; i ++) if(r[i]) flag = 2; // 如果最后发现还有点入度不为零,那么一定存在环
    if(flag == 0) while(!ans.empty()) {cout << char(ans.front() + 'a'); ans.pop();}
    if(flag == 1) cout << "?";
    if(flag == 2) cout << "!";
    cout << endl;
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注