崔添翼 § 翼若垂天之云

第一题是计算几何题，我的构图是这样的：每条线段给最终的图贡献几个顶点，两端点、所有交点、离终点最近的点，出自同一条线段的点互相之间的权值为距离，出自不同线段但事实上重合的点（比如说交点事实上出现两次）之间权值为零，其他权值均为正无穷，起点也在图中，在哪条线段上就与这条线段贡献的所有顶点连边。然后做一次Dijkstra，求出所有点到起点的距离，最后按照步行距离为第一关键字，行驶距离为第二关键字找到最小值即可。需要用到的计算几何内容有：判相交、求交点、判点在线段上、求点与线段的最近点，有些东西我甚至是现学的，好在时间充裕。 第二题我比较晕，如果是完全合法的robots.txt我的程序肯定能解析，但最后结果到底是怎么样还得看数据。我忽略了所有的大小写，还忽略了所有’/’与’\’的区别。一开始竟然忘记处理注释，还好最后加上了。 第三题求较优解，我的算法是一次贪心加一次贪心的调整。首先选择能够对整体尽量符合的关键字，然后根据最不匹配的那个人的情况进行一些调整。加了卡时，应该能保证每个点都有分吧。本来想对于所有的字符串进行hash来判重，但又觉得太不保险，就采用了顺序比较来判重的方法，为了保证不超时，如果当前的词汇太多的话就忽略剩下的所有词。考完了以后才想到，其实蛮可以使用hash进行第一步的判重，然后再实际判重，这样会大大提高效率，肯定就不需要采用那个可能使解的质量大打折扣的剪枝了。或者使用STL里面的map也可以呀，都是学OI学的把这些若干个月前还熟稔于心的东西都忘完了。 第四题还是较优解，算法是每次进行BFS，每个维修队都向最近的公司去修。一个剪枝是当前已经完全没有可能修复的公司就放弃（在程序中就是当作已经完全修复处理）。还是用卡时的手段来保证有分，也就是快超时了就全部REST。 题目还是不错的，第一题考察算法基本功（但为什么就考到了我最薄弱的计算几何……），第二题考察工程功底（这点我目前还相当差……），第三题和第四题都是不错的算法设计题。我估计第一题和第四题会分比较多，第二题完全看数据了，第三题多少会得点分。目前进复赛的期望比考前高了一些。

我就是这么矫情，喜欢一个歌手时，便会害怕听到他的新碟。因为生怕找不到当初的激动，害怕那种好友不再般的失落，所以才会将Linkin Park五月的新碟Minutes to Midnight拖到今日才听。可是，无意的谶言还是应验了。我何会想到一时翘楚的Linkin Park有朝一日也会变得这般平和无力，甚至波澜不惊。卖力的吉他只是掩饰，鼓点却已懈怠，剩下单薄的人声，哪还有半点当年睥睨天下的气象。我只能无奈的承认，曾让我那样喜欢的Linkin Park已然江郎才尽，剩下的只是媚俗。可还是不能太过责怪他们吧，他们不过是游走于音乐与金钱之间的几个青年而已。他们曾引领时代，却终究被时代裹挟而不能自己。失去了Linkin Park的时代，我们仍然不缺好音乐听。也许，这就是这个时代既最好又最坏的含义吧。