icontofig | 发布于 2019-08-03 20:32:45 | 阅读量 231 | Trie 贪心 启发式合并
发布于 2019-08-03 20:32:45 | Trie 贪心 启发式合并

题目大意

给你n个串,让你用每个串的某个前缀串重命名这个串并保证重命名后不会有重复的字符串。

题解

题目很显然需要我们处理n个串的前缀,所以很自然的想到用Trie树(字典树)来降低时间复杂度和空间复杂度。

所以我们先对n个串建立一棵Trie树,然后在这个Trie树上进行操作。

很多人都说后面是启发式合并,我也不是很清楚下面的思路算不算是启发式合并。

后面我们直接dfs整棵Trie树,并自叶节点向上维护信息。

对于每一个节点,维护一个大根堆(用优先队列实现即可),记录其与其子树上的所有的字符串的长度,若我们没有把某个字符串缩到当前节点,那么我们就将子树中深度最深节点所表示的字符串重命名为当前节点所表示的字符串,并回溯更新父节点的信息。

最终回溯到根后,直接将根所有的大根堆内维护的所有的字符串的深度(也就是最终长度)加入答案,最终输出就可以了。

最终的时间复杂度大概是O(nlogn)

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
string s[maxn];
int cnt = 0;
struct tree_node{
    int ch[26];
    int dep;
    int en;
}tr[maxn<<4];
int dep[maxn];
typedef pair<int,int>PI;
priority_queue<PI>q[maxn];
int ans = 0;
void build(int x,int now,int depth){
    int len = s[x].size();
    for(int i = 0;i < len;++i){
        char t = s[x][i];
        if(tr[now].ch[t - 'a'] == -1){
            tr[now].ch[t-'a'] = ++cnt;
            tr[cnt].dep = tr[now].dep + 1;
            for(int i = 0;i < 26;++i)
                tr[cnt].ch[i] = -1;
            tr[cnt].en = 0;
        }
        now = tr[now].ch[t-'a'];
    }
    tr[now].en = 1;
    return;
}
void check(int now){
    if(now == -1)return;
    while(!q[now].empty())q[now].pop();
    for(int i = 0;i < 26;++i){
        int v = tr[now].ch[i];
        check(v);
        while(!q[v].empty()){
            q[now].push(q[v].top());
            q[v].pop();
        }
    }
    if(now != 0 && !q[now].empty() && !tr[now].en){
        tr[now].en++;
        tr[q[now].top().second].en--;
        q[now].pop();
    }
    if(tr[now].en == 1){
        q[now].push(make_pair(tr[now].dep,now));
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(tr,-1,sizeof(tr));
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> s[i];
    }
    tr[0].dep = 0;
    tr[0].en = 0;
    for(int i = 1;i <= n;++i){
        build(i,0,0);
    }
    check(0);
    while(!q[0].empty()){
        ans += tr[q[0].top().second].dep;
        q[0].pop();
    }
    cout << ans << endl;
}



内容更新于: 2019-08-03 20:32:45
链接地址: http://blog.leanote.com/post/icontofig/1c71d4d2e578

上一篇: HDU 1512 Monkey King 左偏树 并查集

下一篇: 2019 Multi-University Training Contest 4 1008 K-th Closest Distance 二分答案+可持久化线段树(主席树)

231 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航