浅析tarjan算法

 OI

几乎网上所有有关tarjan算法的介绍都会有下面这一段话:

Tarjan老爷子一生发明了许多算法下到 NOIP 上到 CTSC 难度的都有。

(Tarjan 算法,并查集,Splay 树,Tarjan 离线求 lca)

我们这里要介绍的是图论中的 Tarjan 算法,用来处理各种连通性相关的问题。

期望与微积分

 OI

以NOIp2018初赛第7题为例:

1
2
3
4
5
 7. 在一条长度为1 的线段上随机取两个点,则以这两个点为端点的线段的期望长度是( )。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5