我对计算几何一无所知
FHQ Treap
\(\text{FHQ Treap}\)是一种好写好用的平衡树。
它的平衡策略和普通\(\text{Treap}\)相似,采用在维护\(\text{BST}\)性质的同时维护随机的堆的形态来维持平衡;
但是维护结构的方式和\(\text{Treap}\)不同,不采用旋转,而是采用拆和合并的方法来维持树和堆的特性。
同时,由于\(\text{FHQ Treap}\)的操作所涉及的节点和基于旋转的其他平衡树相比少(仅\(\log n\)个),它支持可持久化。
bzoj刷题记录 (1)
[BZOJ1011] [HNOI2008] 遥远的行星
题目链接,首先理解题意
有一条数轴,\([1,n]\)每个点上都有一个行星,每个行星\(i\)都有质量\(M_i\),同时有一个很小的实数常量\(A\);
当\(i,j\)两个行星有着\(i\leq Aj\)的关系时,\(i\)对\(j\)有着大小为\(\frac{M_i M_j}{j-i}\)的作用力,求每个星球受到的作用力大小
NOIP2018提高组题解
请注意发布时间,以免引起不必要的麻烦。
继续阅读“NOIP2018提高组题解”
Treap
\(\text{Treap}\)是一种通过维护堆和二叉搜索树两重性质来限制树高的平衡树。
每一个节点都被赋予了两个值,称作\(val\)和\(key\),分别按照BST和堆的性质维护:
- 小根堆:每一个节点的\(key\)都小于等于他的两个子节点的\(key\)
- 二叉树:每一个节点的\(key\)都比他左子的\(val\)大,比右子的\(val\)小
每一个节点的\(key\)是随机指定的,这样可以保证期望树高为\(\log n\)
考试用 C++ IDE 向的 Vim 启动设置文件(~/.vimrc)
NOIP2018集训日志
后缀自动机与线性构造后缀树——转自fanhq666(fhq范爷)
转自范爷的blog:http://fanhq666.blog.163.com/blog/static/8194342620123352232937/
原始文件:https://blog.edgaru089.ml/custom-items/后缀自动机与线性构造后缀树.txt
冬令营上我犯了最大的一个错误,就是在陈立杰讲后缀自动机的时候睡觉。
这导致了,我在冬令营之后只能花费好几个不眠之夜来思考后缀自动机到底是什么。
突然,在某天的梦里,我看到了一幅神奇的图景,我突然发现,一切都是那么的明晰了。
洛谷P4911 河童重工的计算机
题面见 https://www.luogu.org/problemnew/show/P4911
作为出题人,我有责任写一篇题解(逃
这题的初衷就是一个庞大的大模拟,刚刚见到未来程序改这道题有着一种自然的熟悉感呢(笑)
但是不像那道题,这道题没有什么语义树之类的高深的东西呢,只有对代码能力的考察,像我这种初中三年荒废在搞项目的人,代码功底还可以说是十分扎实的呢(笑)