01 May 10 HDOJ Monthly Contest – 2010.05.01 Line belt
这题是我最早想给HDOJ月赛的，现在借lxh达到了这个目的-.-!
http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1004&cid=289
没啥特别意思的几何题。。做法就是双重三分，也就是三分里面套一个三分。
放在这里记录一下我的出题成果：） (more…)
Tags: HDOJ Monthly, 三分, 计算几何
18 Apr 10 武汉大学第八届程序设计竞赛部分决赛题目分析
在这里简单说一些我出的题目。
F: Pie
此题很明显的是一个最小匹配的模型。而后根据题目数据的特点可以利用DP来解决。
简单说一下性质：
1. 排序之后的匹配是不存在交叉线的。也就是说，如果第i高的男的和第j高的女的匹配，那么比i矮的男的就不能和比j高的女的匹配。同理，比i高的男的也就不能和比j矮的女的匹配。
2. 题目里有说男女的人数相差不到100，所以我们可以知道一个人的的可选匹配数量最多是100个。再加上这个性质，我们就可以用O(n * 100) = O(1000000)的DP来解决这个问题。相关的实现要用到滚存。
附上代码： (more…)
Tags: WHU2010校赛决赛, 动态规划, 匹配, 图论, 计算几何
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, 二维线段树, 计算几何
05 Apr 10 WHU2010校赛预赛J题：Guard
http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=288
题意：给定一个简单多边形，问内部哪个点可以看到的面积最大。（可视范围是已知的R，也就是说，如果没有遮挡，那个可视面积就是一个半径为R的圆）
这题是我出的另一个复杂几何，说一下做法： (more…)
Tags: WHU2010校赛预赛, 计算几何
05 Apr 10 WHU2010校赛预赛G题：Pseudoforest
http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1007&cid=288
题目大意：给一个图，求这个图的最大伪森林生成树。所谓的伪森林就是图中的任意两个圈都没有公共部分。 (more…)
Tags: WHU2010校赛预赛, 图论
05 Apr 10 WHU2010校赛预赛C题：Ice-sugar Gourd
http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=288
题目大意：给一个由两种水果组成的冰糖葫芦，现在需要把这两种水果平均送给两个人。问最少需要切割多少次。（切割不能把水果切开）
这题是我出的，在这里说一下做法： (more…)
Tags: WHU2010校赛预赛
05 Apr 10 WHU2010校赛预赛B题：fix
题目地址：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=288
题目意思是告诉很多点（最多18个），然后有一些点是固定住了的，有一些点是没有固定的。现在需要用小木棍连接，使得所有的点都固定住。
问小木棍的总长度最短是多少。
这个题目是我出的，在这里说一下这个题目的做法： (more…)
Tags: WHU2010校赛预赛, 动态规划
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个之多，怎么求得高效的求得所有的点割是这个题目的另一个关键。
仔细观察残余网络的性质之后，可以得出一下算法：
- 在残余网络中bfs，直到走不动了，就找到了第一个割。
- 而后把这个割在残余网络中连通，并且继续bfs（进行第一步的操作）。
这个做法的精巧实现使可以做到线性的。
Tags: HDOJ Monthly, 图论, 网络流
07 Feb 10 POJ Monthly Contest – 2010.1.24 – Problem A "Cake"
http://poj.grids.cn/contest/1774/problem-A/
这个题目是我出的，题意写的有点晦涩-.-!
不过简单表述起来还是挺简单的。
就是在一个圆上进行切割，每一次切割都要跨过整个圆。然后需要检查切割线，检查切割线的方法就是碰触切割出来的每一个小块。
说白了就是小块为点，相邻的小块连边，然后问进行点涂色，使得每一个边的两个端点至少有一个是涂色过了的。
解法：
通过一系列比较麻烦的几何处理之后，所求出来的图是一个二分图。然后求得二分匹配就是答案。
关于这个图是二分图的证明也有比较形象的理解，就是这个图是明显没有奇环的，所以就是二分图咯。。。
Tags: Poj 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:
- If the first lantern is off then install a switch to change the states of first k lanterns.
- Let the second lantern be the first one and repeat Step 1 until there are less than k lanterns.
- 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.
- Find the states of one lantern.
- Change all states of an interval.
Segment Tree will be worked.
这里说的线段树其实就是区间覆盖那种，统计一个点的奇偶值就查看这个点被覆盖的总数就好了。
因为这里的区间的大小总是K，所以其实用不着线段树，线性扫描就好了。。。
Tags: HDOJ Monthly, 线段树, 贪心
1,106 | Unique Visitors |
