2011年05月 存档

2011.5.24

2011年05月25日,星期三

DELETED ~ DON’T YY ~ OK ?

ZOJ 3195 Design the city (lca + st )

2011年05月12日,星期四

ZOJ 3195 Design the city

给出n个区域,有n-1条路去连接这些区域,显然他是一个带权无根树。首先把它以0为根看成有根树,对于给出的三个点,每两个点之间的距离是固定的,因为他们之间只有一条路,但是对于这么多查询(at most 70000 ),直接找距离代价太大,找出每两个点的LCA,这样就可以两个点之间的距离了,(需要知道从0点开始到这两个点的距离)。 我们把这三对点的距离加起来再除以2,就能得到连接着三个点的最短路径。

(更多…)

ZOJ 2067 White Rectangles (greedy)

2011年05月2日,星期一

ZOJ 2067 White Rectangles

好久没有更新博客了,突然间想做几个贪心题目,于是就照着大黄的贪心题目分类开始刷。

题目描述的很清楚,给出n*n的地图,需要找出全部由白色点组成的矩形的个数。刚开始想到的是枚举,不过这个复杂度也太高了。需要做一个预处理,需要统计处从某一点开始向右最长的连续白点个数,保存在rightt中。然后进行枚举每个点,统计以他为左上角的矩形的个数,其间还要枚举高度。。时间复杂度O(N^3)

(更多…)