背单词

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2567 字
逆序 Trie 建后缀森林，子树升序定序
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1477
// 题意：n 个互不相同的单词排成 1..n 的填表顺序，每个单词必须排在其所有后缀单词之后，代价为「自己的位置 - 最后一个后缀的位置」（无后缀时代价为位置本身），求最小总代价。
// 思路：单词逆序建 Trie，每个单词结点挂到「最近的单词结尾祖先」下形成一棵森林（该祖先即最长真后缀）。总代价 = 所有位置之和 - 各点父结点位置之和，用 DFS 给每棵子树分配连续区间，并把兄弟按子树大小升序排列即可最小化。
// 复杂度：O(总字符数 + n log n) 时间 / O(总字符数) 空间
// 易错点：后缀父子关系必须在全部单词插完后统一由 Trie 父亲推出，插入时顺手记录会因后面的短单词还没进树而挂错父亲。
// 易错点：森林里只放「单词结尾结点」，中间结点不能参与排位；兄弟要按子树大小升序排且 DFS 区间必须连续。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[26];
    bool ed;
    Node(){
        memset(ch, 0, sizeof(ch));
        ed = false;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<Node> tr;
    tr.reserve(510000 + 5);
    tr.push_back(Node());
    vector<int> tpar(1, 0);
    vector<int> par(1, 0);
    vector<char> isEnd(1, 0);
    vector<int> wordNode(n, 0);
    for(int i = 0; i < n; i++){
        string w;
        cin >> w;
        reverse(w.begin(), w.end());
        int u = 0;
        for(int j = 0; j < (int)w.size(); j++){
            int c = w[j] - 'a';
            int v = tr[u].ch[c];
            if(!v){
                v = (int)tr.size();
                tr[u].ch[c] = v;
                tr.push_back(Node());
                tpar.push_back(u);
                par.push_back(0);
                isEnd.push_back(0);
            }
            u = v;
        }
        isEnd[u] = 1;
        wordNode[i] = u;
    }
    int sz = (int)tr.size();
    for(int u = 1; u < sz; u++){
        par[u] = isEnd[tpar[u]] ? tpar[u] : par[tpar[u]];
    }
    vector<vector<int>> kids(sz);
    vector<int> sub(sz, 0);
    for(int u = 1; u < sz; u++){
        if(!isEnd[u]) continue;
        kids[par[u]].push_back(u);
        sub[u] = 1;
    }
    for(int u = sz - 1; u >= 1; u--){
        if(!isEnd[u]) continue;
        sub[par[u]] += sub[u];
    }
    for(int u = 0; u < sz; u++){
        sort(kids[u].begin(), kids[u].end(), [&](int a, int b){
            return sub[a] < sub[b];
        });
    }
    vector<int> pos(sz, 0);
    vector<int> idx(sz, 0);
    vector<int> st;
    st.push_back(0);
    int timer = 0;
    while(!st.empty()){
        int u = st.back();
        if(idx[u] == 0 && u != 0) pos[u] = ++timer;
        if(idx[u] < (int)kids[u].size()){
            st.push_back(kids[u][idx[u]++]);
        }else{
            st.pop_back();
        }
    }
    long long ans = 0;
    for(int i = 0; i < n; i++){
        int u = wordNode[i];
        ans += (long long)pos[u] - (par[u] ? pos[par[u]] : 0);
    }
    cout << ans << "\n";
    return 0;
}
背单词

正文

一本通·提高篇的其它内容
