12 May 10 浙江理工大学邀请赛流水帐 by momodi@OpenLegend
Open是武大长期流传下来的人文精神，也是我们集训队一直的宝贵财富。因此我们在Legend的基础上取名OpenLegend，作为本次比赛的队名。
比赛前一天：
本来是想周六中午BG大家的，结果发现了浙江理工在下沙之后就知道中午来不及BG了，所以改到晚上。晚上的湘菜馆还是挺不错的，虽然我感觉不够辣。。吃饭的时候看大家的状态都不错，都挺Happy的。
周六下午热身赛的时候，Dumbear问了我一句：“我们的比赛策略是什么？”
听到这个问题之后，我顿时感觉大脑空白了几秒。
思索了良久这个问题的答案，回想起了以前在ChaeYeon队伍的时候制定的种种策略，比如赛前要制定表格，说好每个人的读题顺序，想好卡题了怎么办，碰到什么类型的题目让谁做，谁负责主要读题，谁负责帮队友debug等等等等。
在回想完这种种之后，不知道为什么感觉这些策略都不值得提出来，于是跟Dumbear说:“到时候看情况，该怎么样就怎么样吧。”
不过虽然没有继续讨论“策略”这个问题，我仍然在那里静静的思考了良久，或许真正的策略便跟武侠里面一样“重剑无锋，无招胜有招”。
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校赛预赛, 动态规划
14 Feb 10 推荐一个vim的配色方案desertEx
可以在这里下载：http://vimcolorschemetest.googlecode.com/svn/colors/desertEx.vim
使用方法：
将文件下载到vim目录下的colors。然后在vimrc里面加入colo desertEx就好了。
感觉比默认的desert清爽一点。
效果图：
14 Feb 10 SRM 461
300P: ColoringRectangle
Greedy algorithm works to this problem:
After we sort the red disks and blue disks by descending order, the final disk placed order would be determined if we choose one of the largest red and blue disks as the left-most disk, where the red disks alternate with the blue disks.
Trick: The disk cannot be used whose diameter is less the height of the rectangle.
500: BuildingCities
Build a graph with at most 50 * 2000 (f[i][j]) vertexes, which means the minimum distance of vertex i which has used j new cities.
Then run shortest path algorithm (SPFA or Dijkstra) on this graph to find the answer.
950: FencingGarden
Tags: SRM
826 | Unique Visitors |
