题解 P6286 [COCI2016-2017#1] Cezar

· · 题解

首先我们达成共识，这道题我们可以把所给的字符串按照它要求的顺序排好，我们记这个叫 str。

这题的题意很明确，我们大概一看我们发现这道题很容易从这个顺序中确定这些字母的先后关系。举一个例子

abc
abd
ade
efg

（再次提醒：这是要求的顺序，不是输入的顺序哦）

那么我们很容易得到（下面记 A<B 代表字母 A 字典序在 B 之前）

  1. c < d
  2. b < d
  3. a < e

我们再来仔细思考一下这个的过程。首先只给第一个字符串我们什么也干不了，给了第二个呢？在第三位不同，第一个是 c，第二个是 d，所以我们就能得到 c < d。

我们再将这个东西一般化：对于字符串 str_i 与 str_j(i < j)，下面我们记 str_{a, b} 代表 str_a 的第 b 个字符。我们找到它们两个的最长公共前缀长度 k。那么应该有 str_{i, k + 1}\not= str_{j, k + 1}，因为 i 排在前面，所以就应该有 str_{i, k + 1} < str_{j, k + 1}。

得到了次序关系，我们很容易想到把它连边（对于 A<B，连一条 A 到 B 的有向边），然后跑一遍拓扑排序，这样就得到所有字符的大小关系了！

其实这里找前缀的地方我们可以优化，因为如果每个都找一遍前缀的话，对于一个 j 光是枚举 i 就得花费 O(n^2) 的时间，还不算上枚举公共前缀的时间。

所以我们就可以建立一棵 trie 树，按照排好后的顺序依次插入 str_1\sim str_n。对于 str_i，我们只需要在 trie 上找找找，找到第一个没有儿子 str_{i, k} 的节点（也就是说找到了 str_i 与前面一个字符串的最长公共前缀长度），那么我们就可以遍历这个节点的其它儿子，它们在 str_i 前面插入，所以这些儿子必然比 str_{i, k} 小。连边即可。

时间复杂度每次都要插入一个字符串，插入 n 次，所以是 O(n|str|) 的，考虑到一共就 26 个字母也就是说只有 26 个点，所以我们可以忽略掉拓扑排序的时间（）

请特别注意一点！

我们上面的考虑，似乎还没有考虑到当 str_i 就是 str_j 的情况。这种情况看样子就得不到任何有效信息了，也就是说我们的答案就可以是 abcdefghijklmnopqrstuvwxyz 了。

但是真的是这样吗？这里我们起码可以得到 str_i < str_j，但是给定的顺序不一定满足这点。所以我们需要在结束所有过程以后特判。我们也不需要把所有满足 str_i 为 str_j 的前缀且 i < j 的数对 (i, j) 找出来，事实上我们完全可以在求出答案后再检验一遍，生成加密后。如果加密后的满足要求，那么就行，否则就是无解（输出 NE。）

相信很多人都因此 80pts，hack 数据

input:
5
d
dd
ddd
dddd
ddddd
1 2 3 5 4

output:NE

代码

//SIXIANG
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAXN 100000
#define QWQ cout << "QWQ" << endl;
using namespace std;
string str[MAXN + 10], tmp[MAXN + 10];
vector <int> gra[MAXN + 10];
int n, a[MAXN + 10], deg[MAXN + 10];
void link(int x, int y) {//如果 x 在 y 之前，则 x 到 y 连边 
    gra[x].push_back(y);
}
bool vis[27][27];

struct node {
    int ch[26];
    int isend;  
} T[MAXN + 10];
int root = 1, tot = 1;
void insert(string str) {
    int now = root;
    bool qwq = 0;
    for(int p = 0; p < str.size(); p++) {
        for(int i = 0; i < 26; i++) {
            if(T[now].ch[i] && i != (str[p] - 'a') && !vis[i][str[p] - 'a']) {
                gra[i].push_back(str[p] - 'a');
                vis[i][str[p] - 'a'] = 1;//vis 是用来判重边的
                deg[str[p] - 'a']++;
            }
        }
        if(T[now].ch[str[p] - 'a'])
            now = T[now].ch[str[p] - 'a'];
        else {
            T[now].ch[str[p] - 'a'] = ++tot;
            now = tot;
        }
    }
}

vector <int> output;
char ans[27];
void topo() {//拓扑排序，很容易理解
    queue <int> que;
    int cnt = 0;
    for(int p = 0; p < 26; p++)
        if(!deg[p]) que.push(p);
    while(!que.empty()) {
        int fr = que.front(); que.pop();
        cnt++;
        output.push_back(fr);
        for(int p = 0; p < gra[fr].size(); p++) {
            int v = gra[fr][p];
            deg[v]--;
            if(!deg[v]) que.push(v);
        }
    }
    if(cnt != 26) cout << "NE" << endl;
    else {
        int o = 0;
        for(int p = 0; p < output.size(); p++)
            ans[output[p]] = o++;
        for(int p = 1; p <= n; p++) {
            for(int i = 0; i < str[p].size(); i++)
                str[p][i] = char(ans[str[p][i] - 'a'] + 'a');
            tmp[p] = str[p];
        }

        sort(str + 1, str + n + 1);
        for(int p = 1; p <= n; p++)//最后检查一遍
            if(str[p] != tmp[p]) {
                cout << "NE" << endl;
                return ;
            }
        cout << "DA" << endl;
        for(int p = 0; p < 26; p++)
            cout << char(ans[p] + 'a'); 
    }
}
void init() {
    cin >> n;
    for(int p = 1; p <= n; p++)
        cin >> tmp[p];
    for(int p = 1; p <= n; p++)
        cin >> a[p], str[p] = tmp[a[p]];//str 就是希望的次序
    for(int p = 1; p <= n; p++)
        insert(str[p]);
    topo();
} 
int main() {
//  freopen("read.txt", "r", stdin);
//  freopen("write.txt", "w", stdout);
    init();
}