liaoyOI副站

目录见下

一个Dijkstral的板子

如果是最短路,应该用Dijkstral。复杂度有保证罢。

https://code.csdn.net/snippets/2318657

注意堆优化的堆的大小应该是与m同阶。


看了一些关于SPFA的报告,第一次提出SPFA的西安大学的论文,2009年中山纪念中学集训队爷姜碧野的集训队论文,还有上海交通大学一个团队关于SPFA的修正。

最后结论就是SPFA没有复杂度保证。

不过最后那一篇上海交通大学那一篇文章提出了一些比较强大的优化,可以应付一些卡掉SPFA的数据。同时,指出SLF与LLL的不科学性,以及被卡到指数级别的例子。


所以不到万不得已(比方说求最长路),使用Dijkstral...

一个线段树合并的板子

不是很清楚为什么建树永远不能用vector?

无法推行vector计划?

拿BZOJ_2733当模板好了……

https://code.csdn.net/snippets/2288840

上面那个只需要Seginsert。

有的时候我们面临着修改。尝试了一下,把Segchange与Seginsert放在了一起。然后注意叶子节点的更新。

拿BZOJ_3307当模板好了……

https://code.csdn.net/snippets/2288840

一个块状链表的板子

每次都写得炒鸡长……

这次自认为写得比较好的一次……

拿codeforces_455D做例子。题目很简单,支持插入删除,维护桶:

https://code.csdn.net/snippets/2277818

一个SAM的板子

代码都差不多的感觉。

那SPOJ 1811为例

https://code.csdn.net/snippets/2224236

vector计划

想把一大堆代码全部调成vector。顺便敲出自己的模板。

一棵可用的LCT

写了一个板子。

https://code.csdn.net/snippets/2221589

代码总是越写越短的。以后时常更新。

 
1 / 7

© liaoyOI副站 | Powered by LOFTER