Tag-Trie

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-08-06 21:47:45 |  0 Comments  |  Trie

2019 Multi-University Training Contest 5 1002 three arrays Trie树+思维题

题目大意

给出两个长度为n的序列a,b,重新排列a、b使得两个序列各个位置上的数异或起来得到的序列C字典序最小,并输出最小字典序的c

题解

这题思路甚为巧妙。

关于异或的题目,我们总是分为各个二进制位置上的0/1来看,例如线性基、0/1Trie。此题就是通过0/1Trie来实现的。

首先我们对于两个序列,建立两个0/1Trie。

然后我们首先从第一个Trie中找出一个数,放入当前的候选答案的栈内,之后去另外一棵Trie中找与之异或值最小的数,再放入栈中,再去当前找到的值所在Trie的另一棵Trie中找与之异或值最小的数放入栈中,如此往复。

直到我们找到一个长度为2的环,此时这个长度为2的环中的两个数就是c中的一组答案了。因为他们两个相互为异或的最小值。就把他们存入c,并且从栈中pop掉,并将这两个数在自己的Trie树中删除,继续循环上面的步骤。

按照这种方法,直到我们把所有n个异或值都找出来,后面只需要排一遍序就是我们需要的最终答案了。

至于为什么环的长度一定为2而不可能为更多,这个东西是有证明的,不过暂时还没理解,暂时不写了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+10;
int ch[maxn*32][2],cnt[maxn*32][2];
int n,T;
int v,c[maxn];
int tot = 0
 2019-08-03 20:32:45 |  0 Comments  |  Trie 贪心 启发式合并

Codeforces 965E Short Code 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;
        
 2019-04-06 15:14:55 |  0 Comments  |  字符串 Trie

poj - IMMEDIATE DECODABILITY Trie树模板

 题解

本题为Trie(字典树)的模板题。

我们先来说一下Trie的基本构造:

Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。

Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。

字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。

有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。

以上是Trie树的基本构造。

对于这个题目,它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。

所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。

所以题意在我们的思路中,就变为了:

在建Trie树的过程中,如果当前访问的节点打上了flag标记(一个单词的结尾)并且访问次数大于了1,则说明出现一个单词为其它单词的前缀。就输出not immediately decodable,如果建完Trie都不存在这样的单词,就输出immediately decodable。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
    int cnt;
    bool flag;
    int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
    memset(pool,0,sizeof(pool));
    num = 0;
    root = pool[0];
    pp = false;
    return;
}
int sum = 0;
int main(){
    init();
    while(cin >> s){
        int len = s.size();
        if
Title - Artist
0:00