在NOIp来之前,赶快奶一口会出逆序对毒瘤数学题,RP++。
在面对超大数据的读入时,我们不得不面对快速的读入方式。
即将参加NOIp2018考试,在此做一个备忘录。
几乎网上所有有关tarjan算法的介绍都会有下面这一段话:
Tarjan老爷子一生发明了许多算法下到 NOIP 上到 CTSC 难度的都有。
(Tarjan 算法,并查集,Splay 树,Tarjan 离线求 lca)
我们这里要介绍的是图论中的 Tarjan 算法,用来处理各种连通性相关的问题。
此题可以用动态规划求解。
以NOIp2018初赛第7题为例:
1 | 7. 在一条长度为1 的线段上随机取两个点,则以这两个点为端点的线段的期望长度是( )。 |
线段树是一种基于分治思想的二叉树结构。用于在区间上进行信息统计。于树状数组相比,线段树更为通用。
1 / 4