CodeForces 965E Short Code 【Trie】【启发式合并】

发表于 | 更新于 | 分类于

题目大意：

给出n个不同的仅由小写字母构成的变量名，要求你对其取前缀将其简化，使简化后的变量名各不相同并且最终的总长度最小。

解题思路：

对单词建立字典树，记录每个单词的长度。然后从树的叶子结点开始向上进行启发式合并，这个过程用multiset进行维护。
启发式合并在这道题中的应用，个人的理解为到达这个结点时，发现这个结点还是空的时候，即可以将一个变量名简化为当前结点代表的变量名的时候，我们要选择它下面的所有变量名中名字最长的那个进行简化，为了便于维护，那就从下往上不断记录到此位置时可以简化的单词长度为多少。在代码中的体现就是DFS中的部分。35-37行为向上传递值，29、39-43行为简化操作。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
const int MAX = 1e5 + 5;

char str[MAX];
multiset<int> st[MAX];
int n, tot, now, nex[MAX][26], dep[MAX], res;
void add()
{
    now = 1;
    for(int i = 0; str[i]; ++i)
    {
        if(!nex[now][str[i]-'a'])
        {
            nex[now][str[i]-'a'] = ++tot;
            dep[tot] = dep[now] + 1;
        }
        now = nex[now][str[i]-'a'];
    }
    st[now].insert(dep[now]);
}
void DFS(int u = 1)
{
    bool emp = (u > 1 && st[u].empty());
    for(int i = 0; i < 26; ++i)
    {
        int v = nex[u][i];
        if(!v)  continue;
        DFS(v);
        for(auto t : st[v])
            st[u].insert(t);
        st[v].clear();
    }
    if(emp)
    {
        st[u].erase(--st[u].end());
        st[u].insert(dep[u]);
    }
}
int main()
{
    tot = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s", str);
        add();
    }
    DFS();
    for(auto t : st[1])
        res += t;
    printf("%d\n", res);
    return 0;
}
Donate comment here
0%