zcmimi's blog

arrow_back启发式合并共4篇文章

avatar
zc
2020-03-01 11:57:00
查看原题

点击跳转

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

每个节点在父节点的基础上插入自身的值

即每个节点的主席树记录的是自身到根节点的路径

具体看代码

avatar
zc
2020-03-01 00:37:00
查看原题

点击跳转

题意:

给一棵trie树,可以删掉某一层的所有边

求删掉哪一层边后合并出的trie树最小?

解法:

trie的启发式合并

avatar
zc
2020-02-29 13:32:00
查看原题

点击跳转

题目的意思就是相同子树中的点不能分配到同一段内存

每个点都开一个大根堆

合并一个点和它的子节点的时候最大值互相对应

启发式合并

具体看代码

avatar
zc
2020-02-28 21:34:00
查看原题

点击跳转

其实可以说是前向星

每次都把短的链表接到长的链表上

统计短的链表上每个元素改变后造成的影响

1/1
Search
search