Skip to content

百度之星复赛

第一题是计算几何题,我的构图是这样的:每条线段给最终的图贡献几个顶点,两端点、所有交点、离终点最近的点,出自同一条线段的点互相之间的权值为距离,出自不同线段但事实上重合的点(比如说交点事实上出现两次)之间权值为零,其他权值均为正无穷,起点也在图中,在哪条线段上就与这条线段贡献的所有顶点连边。然后做一次Dijkstra,求出所有点到起点的距离,最后按照步行距离为第一关键字,行驶距离为第二关键字找到最小值即可。需要用到的计算几何内容有:判相交、求交点、判点在线段上、求点与线段的最近点,有些东西我甚至是现学的,好在时间充裕。

第二题我比较晕,如果是完全合法的robots.txt我的程序肯定能解析,但最后结果到底是怎么样还得看数据。我忽略了所有的大小写,还忽略了所有’/’与’\’的区别。一开始竟然忘记处理注释,还好最后加上了。

第三题求较优解,我的算法是一次贪心加一次贪心的调整。首先选择能够对整体尽量符合的关键字,然后根据最不匹配的那个人的情况进行一些调整。加了卡时,应该能保证每个点都有分吧。本来想对于所有的字符串进行hash来判重,但又觉得太不保险,就采用了顺序比较来判重的方法,为了保证不超时,如果当前的词汇太多的话就忽略剩下的所有词。考完了以后才想到,其实蛮可以使用hash进行第一步的判重,然后再实际判重,这样会大大提高效率,肯定就不需要采用那个可能使解的质量大打折扣的剪枝了。或者使用STL里面的map也可以呀,都是学OI学的把这些若干个月前还熟稔于心的东西都忘完了。

第四题还是较优解,算法是每次进行BFS,每个维修队都向最近的公司去修。一个剪枝是当前已经完全没有可能修复的公司就放弃(在程序中就是当作已经完全修复处理)。还是用卡时的手段来保证有分,也就是快超时了就全部REST。

题目还是不错的,第一题考察算法基本功(但为什么就考到了我最薄弱的计算几何……),第二题考察工程功底(这点我目前还相当差……),第三题和第四题都是不错的算法设计题。我估计第一题和第四题会分比较多,第二题完全看数据了,第三题多少会得点分。目前进复赛的期望比考前高了一些。

2 Comments

  1. TopBoy wrote:

    呵呵,第四题,快超时了我全部REPAIR

    Sunday, June 10, 2007 at 11:13 | Permalink
  2. evalls wrote:

    ms计算几何不怎么考人的。会的就写,不会就放~从来不想的

    Monday, June 11, 2007 at 20:30 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*