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