Category Archives: 字典树

CodeForces 557E Ann and Half-Palindrome (Trie,dp)

定义奇数回文表示奇数位置对称的回文。计算第k大子串奇数会问。 用dp搞出区间[i, j]是否是奇数回文,然后暴 …

HDU 5845 Best Division (dp,trie)

给出n个数字,将他们分成尽量多的连续块,使得每块的异或和<=X且长度<=L dp[i]表示以i结尾 …

2016 Multi-University Training Contest 5

1001 – ATM Mechine 一个有在ATM机偷钱,他只知道钱的上限是K,他每次可以选择取 …

HDU XOR 游戏 (二分,dp,字典树)

众所周知,度度熊喜欢XOR运算。 今天,它发明了一种XOR新游戏,最开始,它有一个长度为N的数组,度度熊可以任 …

可持久化字典树

可持久化字典树是一种可持久化数据结构,比较懂主席树原理的应该能很快写出这种字典树,类似这种没有后效性的数据结构 …

51nod 1295 XOR key (可持久化字典树)

给出n个数字,然后Q个询问,每个询问计算区间[l, r]中的数字与x异或的最大值。 不放先思考下只有一个询问的 …

Codeforces E 665 Beautiful Subarrays (字典树上分治)

给出n个数字,求连续子序列异或和>=k的个数。 不妨先预处理出前缀的异或和,那么任意一段连续子序列的异或 …

hihoCoder 1107 Shortest Proper Prefix (字典树)

给出n个串,计算多少前缀满足:1.此前缀本身最多是5个串的前缀;2.此前缀的前缀(不包括本身)不满足条件1 建 …

Trie

最近整理了一下字典树的静态模板

 

hihoCoder 1014 Trie树 (字典树水题)

统计字典中以某个字符串为开头的字符串个数。 对于每个插入操作,每当经过树上的一个点时就意味着:以这个点为roo …