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%