icontofig | 发布于 2020-02-19 22:10:38 | 阅读量 1155 | 字符串 可持久化线段树 可持久化数据结构 Trie
Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树
Input5 5 a ab abab ababab b 1 5 1 3 5 1 1 5 2 1 5 3 1 4 5Output7 5 6 3 6题目大意给出n个字符串,q次询问,每次询问l,r,k,求问 字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。 题解多模式串匹配肯定是AC自动机 但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。 AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。 而
继续阅读
icontofig | 发布于 2020-02-11 17:05:57 | 阅读量 346 | Trie
发布于 2020-02-11 17:05:57 | Trie
CodeForces - 1055F  Tree and XOR 01-Trie
题目大意有n个节点的有根树,根为1,每条边有权值,点对(u,v)的路径长度为从u到v路径上所有权值的异或值,认为点对(u,v)与(v,u)表示两个路径,总共有n2个点对路径(自己到自己也算一个),求问其中路径长度第k小的路径长为多少。 题解n的范围是很大的,不可能通过枚举计算。 两点(u,v)之间的路径长度,可以通过lca转化为: (u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root); 所以可以将每个点到根节点的路径异或长度预处理出来,之后再进行下面的操作。
继续阅读
icontofig | 发布于 2020-02-06 20:52:24 | 阅读量 368 | 最小生成树 Trie
发布于 2020-02-06 20:52:24 | 最小生成树 Trie
51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心
题解每条边的权值都是根据每个点的定值通过二进制异或得出的。 如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。 假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。 这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。 于是所有的答案统计全部都在01trie上。 接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。 所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。 假如一个叶节点上有k个点(k > 2),
继续阅读
icontofig | 发布于 2019-09-06 22:19:42 | 阅读量 439 | 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 | 阅读量 380 | 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 | 阅读量 289 | 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 | 阅读量 320 | 字符串 Trie
发布于 2019-04-06 15:14:55 | 字符串 Trie
poj - IMMEDIATE DECODABILITY Trie树模板
 题解本题为Trie(字典树)的模板题。 我们先来说一下Trie的基本构造: Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。 Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。 字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。 有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。 以上是Trie树的基本构造。 对于这个题目,它的要求是判断任意一个字符串不能
继续阅读