楼天城获得Google 2008编程挑战赛冠军
Google 2008编程挑战赛已顺利结束,清华大学计算机系的楼天城获得第一名,南京外国语学校的朱泽园获得第二名。进入最终决赛的一百位选手中有19位来自中国。从Google搜索结果来看,楼天城和朱泽园都有过集训参加国际奥林匹克竞赛的经历,其中楼天城与其他两位选手组成清华代表队参加了2007年ACM国际大学生程序设计竞赛,并获得第二名。
膜拜大牛~
Google 2008编程挑战赛已顺利结束,清华大学计算机系的楼天城获得第一名,南京外国语学校的朱泽园获得第二名。进入最终决赛的一百位选手中有19位来自中国。从Google搜索结果来看,楼天城和朱泽园都有过集训参加国际奥林匹克竞赛的经历,其中楼天城与其他两位选手组成清华代表队参加了2007年ACM国际大学生程序设计竞赛,并获得第二名。
膜拜大牛~
最近公共祖先(LCA)问题都应该很熟悉了。
LCA(T,u,v):在有根树T中,询问一个距离根最远的结点x,使得x同时为结点u、v的祖先
LCA问题可以用朴素的DFS方法解决,但是时间复杂度就很高了,这里介绍一种高级一点的解决LCA问题的Tarjan算法。
Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法,也就是说,它要首先读入所有的询问(求一次LCA叫做一次询问),然后并不一定按照原来的顺序处理这些询问。
首先需要有一些预备知识:
1.基本图论
这个就不多讲了,如果有不知道的可以随便抓一本数据结构的书恶补一下。
2.并查集
并查集其实也是很简单的东西,实现的代码都不超过10行。
这里提一下并查集的概念,并查集是一种处理元素之间等价关系的数据结构,一开始我们假设元素都是分别属于一个独立的集合里的,主要支持两种操作:
需要知道一点,就是并查集的Find操作的时间复杂度是常数级别的。
Tarjan(u)
F(u)<-u;
For each (u,v) in Q(u) do Answer(u,v) <- F(v)
For each v in son(u)
a) Tarjan(v);
b) F(v) <- u;