「Bzoj 4567」「SCOI2016」背单词 (Trie 前缀关系树 + 贪心)

发表于 | 分类于 | | + s

BZOJ 4567
题意：给你$n$个字符串，不同的排列有不同的代价，代价按照如下方式计算（字符串$s$的位置为$x$）：
1.排在$s$后面的字符串有$s$的后缀，则代价为$n^2$；
2.排在$s$前面的字符串有$s$的后缀，且没有排在$s$后面的$s$的后缀，则代价为$x-y$（$y$为最后一个与$s$不相等的后缀的位置）；
3.$s$没有后缀，则代价为$x$。
求最小代价和。(吐槽一波题意)

显然第一种操作尽量少用($n^2$和$n$的增长级)，其实我们完全可以避免这种操作出现，即将他后缀权值安排在他前面。

那么我们将字符串翻转插进Trie，这样就可以维护后缀。
现在问题是Trie上有很多没有单词虚节点，不好处理，我们将其全部删掉，然后将有单词的数组成Trie 前缀关系树，那么这个树上孩子的最长前缀一定是父亲节点。

那么现在问题就是给每个点标号，然后让孩子节点减父亲节点的标号的差的总和最小。考虑将所有单词连接的虚点设为0，那么将这个虚点算作其中，然后将操作2转化到操作3。

那么我们现在可以考虑一个贪心，即从根开始DFS，每次找子树大小最小的进去然后DFS序是最优的。
具体证明比较困难，但是可以意会一下，即可以发现这样可以让后面的孩子的标号尽量小。

知识点
1、将字符串翻转插进Trie，这样就可以维护后缀。
2、将有单词的数组成Trie 前缀关系树

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 520000 + 5;

    int n, ch[MAXN][26], val[MAXN], sz;
    char s[MAXN];

    vector<int > G[MAXN];
    int sz_G, siz[MAXN], col[MAXN], idx;

    bool cmp(int x, int y) {return siz[x] < siz[y];}

    void ins(int u, int v) {G[u].push_back(v);}
    void insert() {
        int now = 0, len = strlen(s);
        for (int i = len - 1; i >= 0; --i) {
            int c = s[i] - 'a';
            if (!ch[now][c]) ch[now][c] = ++sz;
            now = ch[now][c];
            if (i == 0) val[now] = 1;
        }
    }
    void dfs_build(int u, int chain) {
        if (val[u]) ins(chain, ++sz_G), chain = sz_G;
        for (int c = 0; c < 26; ++c) {
            int v = ch[u][c];
            if (v) dfs_build(v, chain);
        }
    }
    void dfs_siz(int u, int fa) {
        siz[u] = 1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) 
                dfs_siz(v, u), siz[u] += siz[v];
        }
    }
    LL ans = 0;
    void dfs(int u, int fa) {
        col[u] = ++idx;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) {
                dfs(v, u);
                ans += col[v] - col[u];
            }
        }
    }

    void clean() {
        ms(ch, 0), ms(val, 0), sz_G = sz = 0, ms(siz, 0), ms(col, 0), idx = -1;
    }
    int solve() {

        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%s", s), insert();
        dfs_build(0, 0);
        dfs_siz(0, -1);
        for (int u = 0; u <= sz_G; ++u) sort(G[u].begin(), G[u].end(), cmp);
        dfs(0, -1);
        //for (int u = 0; u <= sz_G; ++u) for (int i = 0; i < (int)G[u].size(); ++i) printf("u=%d, v=%d\n", u, G[u][i]);

        printf("%lld\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
//
/*
3
a
ab
c
*/
------ 本文结束 ------