UOJ Logo negiizhao的博客

博客

<del>noip退役选手的another扯淡</del>Top tree 的理论、用法和实现

2019-03-09 18:18:54 By negiizhao

The cruel world...

在一切之前,把微小的工作尽可能做好吧。


该来的,总是要来的呢……

过了这么久,总算是下决心写一个较完整的介绍了啊……

这次要写的是,top tree 相关的东西究竟是什么,为什么说这东西实际上远强于 OI 中所流传的版本。

阅读更多……

<del>noip退役选手的另一些扯淡</del>维护双向加字符的字符串的隐式后缀树

2018-12-25 00:00:01 By negiizhao

凛冽的风……

仿佛要将这最后的,仅剩的,微不足道的,存在的意义,剥下呢……


大概今年 6 月的时候用后缀树推了一遍 Blumer 的后缀自动机构造算法,还考虑了一些其他相关的东西,不过并没想清楚……前不久听说北大集训出了这样的题,于是就把这个坑填上了……这次要写的是,写起来要考虑的东西略多的维护双向加字符的字符串的隐式后缀树,就当是给大家的圣诞节礼物吧。

6 月时写过用后缀树解释 Blumer 的后缀自动机构造算法,但可能不是很能看,所以就没有发出来了。

阅读更多……

<del>noip退役选手的一些扯淡</del>关于优化形式幂级数计算的牛顿法的常数

2018-11-27 18:16:44 By negiizhao

非常抱歉……又让您失望了呢……

2 年过去了……我还是一点进步都没有……一次大型比赛都没打好……

真的会有那样一天……像您那样强吗?……


想写的那些东西果然还是太麻烦了……根本写不动……就写一些没什么意思的东西吧……关于优化求形式幂级数的牛顿法的常数。

虽然写得很糟糕但还算是能看的,所以就发出来了。

阅读更多……

Top trees用于仙人掌?O(log n)时间?带link和cut的QCACTUS?。。。

2017-12-31 23:53:07 By negiizhao

//为防止误解,还是声明一下。。下面标引用的东西是照着某著名slide写的(

阅读更多……

科技小论文?一些奇怪的东西?QTREE系列加上link和cut?。。。

2017-12-21 01:58:29 By negiizhao

emmmmmm...前段时间学校要写个科技小论文。。。

也不知怎么的,莫名就写了个奇怪东西,反正不是论文

大概就是找来一堆论文(主要也就那几个),翻译拼凑一番(参考文献都不需要找了)。。。

把(一部分)动态树数据结构(ET-trees、ST-trees和top trees)粗略介绍了一遍。

顺便说一下,真正的top trees使用姿势可能在11页。。。对应的模板题大概是QTREE系列加上link和cut。。。

(Alstrup et al.: "Top trees generalize balanced binary search trees!")

(模板题可能还有link cut 找类似重心的东西。。。)

阅读更多……

共 5 篇博客