icontofig | 发布于 2019-09-06 22:19:42 | 阅读量 359 | Trie 思维题 hash
发布于 2019-09-06 22:19:42 | Trie 思维题 hash
2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie  Trie 思维题 倍增 Hash
题目大意给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。 求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。 题解暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。 而每一次失配我们都会重新回到起点。 于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,
继续阅读
icontofig | 发布于 2019-08-06 21:47:45 | 阅读量 354 | Trie
发布于 2019-08-06 21:47:45 | 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的环中的两个
继续阅读
icontofig | 发布于 2019-08-03 20:32:45 | 阅读量 228 | Trie 贪心 启发式合并
发布于 2019-08-03 20:32:45 | Trie 贪心 启发式合并
Codeforces 965E Short Code Trie树+贪心(启发式合并)
题目大意给你n个串,让你用每个串的某个前缀串重命名这个串并保证重命名后不会有重复的字符串。 题解题目很显然需要我们处理n个串的前缀,所以很自然的想到用Trie树(字典树)来降低时间复杂度和空间复杂度。 所以我们先对n个串建立一棵Trie树,然后在这个Trie树上进行操作。 很多人都说后面是启发式合并,我也不是很清楚下面的思路算不算是启发式合并。 后面我们直接dfs整棵Trie树,并自叶节点向上维护信息。 对于每一个节点,维护一个大根堆(用优先队列实现即可),记录其与其子树上的所有的字符串的长度,若我们没有把某个字符串缩到当前节点,那么我们就将子树中深度最深节点所表示的字符串重命名为当前节点所表
继续阅读
icontofig | 发布于 2019-04-06 15:14:55 | 阅读量 274 | 字符串 Trie
发布于 2019-04-06 15:14:55 | 字符串 Trie
poj - IMMEDIATE DECODABILITY Trie树模板
 题解本题为Trie(字典树)的模板题。 我们先来说一下Trie的基本构造: Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。 Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。 字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。 有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。 以上是Trie树的基本构造。 对于这个题目,它的要求是判断任意一个字符串不能
继续阅读