05 Apr 10 HDOJ Monthly Contest – 2010.04.04 Problem 1003 Point

http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1003&cid=276

题目大意就是用下面的距离定义来求每一个点的最近点对。

Distance (A, B) = max (|Ax – Bx|, |Ay – By|)

这题是我最初给我们学校去年的区域赛准备的题目。说一下做法： (more…)

Tags: HDOJ Monthly, 二维线段树, 计算几何

07 Feb 10 HDOJ Monthly Contest – 2010.02.06 Problem “Key vertex”

http://acm.hdu.edu.cn/showproblem.php?pid=3313

这个题目的意思给一个有向图，然后问有多少个key vertexes。一个点是key vertex的定义是，删掉这个点之后这个图的S-T就不连通了。

网络流的做法是比较显然的。在拆点然后跑网络流之后，所有的点割就都是key vertex。

题目里的点数比较多，有100000个之多，怎么求得高效的求得所有的点割是这个题目的另一个关键。

仔细观察残余网络的性质之后，可以得出一下算法：

1. 在残余网络中bfs，直到走不动了，就找到了第一个割。
2. 而后把这个割在残余网络中连通，并且继续bfs（进行第一步的操作）。

这个做法的精巧实现使可以做到线性的。

Tags: HDOJ Monthly, 图论, 网络流

07 Feb 10 HDOJ Monthly 2009.01 Problem "Light"

http://acm.hdu.edu.cn/showproblem.php?pid=3275

这个题目比较简单。。。

我刚开始写的解题报告里面说：

Greedy algorithm and Segment Tree will be worked at this problem.

We need change all “0” to “1”, so let’s put our attention on the first lantern of the given string. There is only one way to change states of first lantern which is installing a switch to control the first k lanterns.

Algorithm:

1. If the first lantern is off then install a switch to change the states of first k lanterns.
2. Let the second lantern be the first one and repeat Step 1 until there are less than k lanterns.
3. If all of the remaining lanterns are on then output the answer else output “-1”.

Native solution will get TLE as it’s running in O(n * k).

A new accelerated date structure should be used to storage all the states of lanterns. This date structure should support two operators.

1. Find the states of one lantern.
2. Change all states of an interval.

Segment Tree will be worked.

这里说的线段树其实就是区间覆盖那种，统计一个点的奇偶值就查看这个点被覆盖的总数就好了。

因为这里的区间的大小总是K，所以其实用不着线段树，线性扫描就好了。。。

Tags: HDOJ Monthly, 线段树, 贪心