Tag Archives: Trie

可持久化01trie

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

可持久化01trie 类似主席树,在已有的基础上修改,空间。 Thu Summer Camp 2015异或运算 考虑到比较大,对建可持久化01trie然后最多同时查询次(同一棵01trie)。 #pragma GCC optimize(2) #include <cstdio> using namesp

Read More

[二进制trie+贪心]CSUOJ1216异或最大值

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

CSUOJ1216异或最大值 题目传送门 过了好久,终于重新开始写博客了。。。 这是一道二进制trie树的模板题。 二进制trie树,理解一下就是一颗二叉树,左右儿子为0或1。 然后每插入一个数就进行一次Find操作。 Find:对于一个数x,我们在trie上总是走x在二进制下第i位的相反的那个节点。(当存在此节

Read More

[trie+vector][TSC2016]补退选

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

[Thu Summer Camp 2016]补退选 题目传送门 题目大意:维护一个可以支持以下功能的数据结构。 插入字符串S 删除字符串S 询问最早在第几个事件之后,姓名以S为前缀的学生数量超过了(a*|ANS|+b)%c,|ANS|表示上次查询事件的答案的绝对值 前两个是trie的基本操作,第三个用vector

Read More