Skip to content

Tag Archives: 百度之星

百度之星复赛

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

AStar2007进复赛了

复赛名单:http://astar.baidu.com/main/id.htm 我在D字头里面。 分数太惨了,一个18、一个23……也不知道是靠哪个进的。进决赛估计无望了。不过有个TShirt也不错。 这两天没事的时候写个中文字符串的库算了。

“彩球游戏”题解

郑重声明:本人并不自认为“会”此题,只是AC了,说说自己程序的思路而已。 原题:http://hi.baidu.com/astar/blog/item/fe22ab18c3c54b0635fa4192.htm 首先要对输入的数据进行预处理,按照“有连续的X个颜色为Y的小球”的格式,将连续的同色小球一起考虑。s[i]表示第i组小球的数量,type[i]表示第i组小球的类型。注意,所有连续的大于等于M个小球,都可以等价地当作M-1个小球来处理。 设计状态为v[i,j,k1,k2],表示第i组小球到第j组小球的左边多了k1个与s[i]同色的小球右边多了k2个与s[j]同色的小球时被完全消去的最小代价。平凡的状态包括:i>j时,状态的值为0;s[i]+k1>=M时,状态的值为v[i+1,j,0,k2];s[j]+k2>=M时,状态的值为v[i,j-1,k1,0];i==j时,状态的值为M-(s[i]+k1)。 对于非平凡的状态,只需要考虑最左边的一组小球或最右边的一组小球如何处理。以左边的这组小球为例,可取的策略有两种:使用M-(s[i]+k1)个小球将它们单独消去;设s[i]与s[x]同色,在[i+1..x-1]这个序列被先行消除后,将这组小球与s[x]合并后再消除。右边的小球也可以同样定义这两种策略。还有一种策略就是,当s[i]与s[j]同色时,将[i+1..j-1]这个序列先行消除,再将s[i]、s[j]以及k1+k2个小球同时消除。状态转移方程如下: v[i,j,k1,k2]=min{ M-(s[i]+k2) + v[i+1,j,0,k2]; M-(s[j]+k2)+v[i,j-1,k1,0]; v[i+1,x,0,0]+v[x,j,s[i]+k1,k2] (if type[x]=type[i]); v[i,x,k1,s[j]+k2]+v[x+1,j-1,0,0] (if type[x]=type[j]); v[i+1,j-1,0,0] (if type[i]=type[j]&&s[i]+s[j]+k1+k2>=M); v[i+1,j-1,0,0]+(M-(s[i]+s[j]+k1+k2)) (if type[i]=type[j]&&s[i]+s[j]+k1+k2<M); }(i<x<j) 很麻烦吧……我也觉得很麻烦。 如果谁能简化一下那真是太好了。 这样的话,一共有O(N^2*M^2)个 状态,每组状态的转移需要O(N)的时间,总复杂度是O(N^3*M^2),不就严重TLE了么……话是这么说,也许这道题就能告诉我们Big O这种关于复杂度上界的分析有时是会不靠谱的。 具体实现时一定要采用自顶向下的DP实现,也就是所谓的记忆化搜索了。这时你会发现,实际需要计算出来的状态只占总状态数的一小部分。我对这题的4320个数据做了简单的统计,需要计算的非平凡状态的数量平均为2057.766个,其中此数量为0~1000的有2244个,1001~5000的有1541个,5001~10000的有393个, 10001~20000的有139个,20000以上的只有3个,最多的需要计算26621个状态。 我想这个题应该可以得到一个比O(N^2*M^2)更好的需要计算的非平凡状态数的上界,可本人算法分析的能力有限,希望有高人能够在这一点上指教一二。 最后说一下空间问题,如果开一个200x200x20x20的四维数组的话似乎太浪费空间了,另外,由于“内存分页”等我也不太理解的原因,程序的空间用量对实际运行时间(并非“用户时间”或CPU时间)是有影响的。我采用的方法是每次动态分配一个N*N*M*M的一维数组,用来模拟四维数组。例如状态v[i,j,k1,k2]在这个数组中的下标就应该是((i*N+j)*M+k1)*M+k2。当然,也可以将它理解成一种没有冲突的hash——将取值有限制的四元组映射为一个整数。对于本题的数据来说,我的程序最多时用了4128KB的空间。 于是,这道题的4320个数据就被比较完美的解决了。注意我并不是说这道题被完美的解决了,因为算法的理论复杂度仍然很高,不能保证无法设计出达到理论复杂度上界的数据。 欢迎批评指正。 zuma.rar 这是我做的cena评测包,内有我的程序,数据由陈启峰提供,共10组输入输出文件,每个输入文件中含432组数据。