作者：百度 来源：百度之星公告 酷勤网收集 2007-08-18
摘要
与初赛相比，复赛的题目更加侧重考查选手的综合素质。mithril, tedcn, zmy等8位选手前两题均获得满分，体现出了扎实的基本功
与初赛相比，复赛的题目更加侧重考查选手的综合素质。mithril, tedcn, zmy等8位选手前两题均获得满分，体现出了扎实的基本功；第三题的最高分为tedcn(龙凡)，得分为299.3814，第四题的最高分为acrush(楼天成)，得分为291.1531。四题总分第一为acrush(950.9242)， 5位选手总分超过了800，11位选手超过700分，29位选手超过600分，60位选手超过500分，91位选手超过400分。
第一题
这是一道图论和计算几何的综合题。虽然不难，但是比赛时却让不少选手花了很多时间。虽然最后有不少选手获得满分，但是不少选手的程序十分冗长，花费了不少时间才调试通过。我们特地邀请本题获得满分的chenqifeng(陈启峰)写了一份简短的分析，希望各位选手可以从中获得启发：
陈启峰的分析：最优驾车路线一定由若干条直线段依次连接，而这些直线段各属于某些高速公路的一部分。设该路线为(p1,p2),(p2,p3)...(pn-1,pn)，则只要找出所有可能成为pi的点，并求出所有可以成为(pi,pi+1)的边，再用最短路算法即可求出答案。算法步骤如下：
求出所有可能成为pi的点集V。这些点可以分为以下4类：
一条高速公路的两个端点；
两条高速公路的交点；
上车点；
目的地到某条高速公路的垂足（只有垂足在该高速公路上时才保留）
构造边集E：对于每一条高速公路AB，求出V中位于这个高速公路上的所有点，按照离A点的距离排序为v1,v2,...,vk，然后添加(v1,v2)，(v2,v3),...,(vk-1,vk)这k-1条无向边。
以上车起点为源点做一次Dijkstra算法，求出上车起点到V中每个点的最短距离。
注意构造出的图不一定连通，因此只应检查V中所有可达点，选出离终点距离最近的点中驾车距离最小的。
chenqifeng的程序只有107行，不到2.7K，单击此处下载。
第二题
这是一道工程性比较强的题目，它的特别之处在于规范放在外部文档中，并且是英文。这份英文文档并不长（在实际的工程中算是非常短了），但是从贴吧、email和热线询问来看，不少选手仍然没有能够仔细阅读。这里举几个典型的例子：
关于Disallow中URL的含义，规范中写到： The value of this field specifies a partial URL that is not to be visited. This can be a full path, or a partial path; any URL that starts with this value will not be retrieved. 后面甚至还举了例子，但是仍然有选手通过各种途径向我们询问这里是不是指的子串匹配。
关于注释，规范中写到： Lines containing only a comment are discarded completely, and therefore do not indicate a record boundary. 但从测试结果看，仍有部分选手没有处理好这一点。
关于Disallow中的星号，规范中写到： If the value is '*', the record describes the default access policy for any robot that has not matched any of the other records. 也就是说，星号不是指所有user-agent，而是指所有"其他"user-agent. 对这一规则的实现需要小心：如果有两个合法行的User-agent分别是*和Baiduspider，这两行的顺序应该和结果无关。
对于可能产生多种理解的地方，设计测试数据时均已避开。
第三题
本题是提交数量最多的一题，因此每个点分数的粒度比较小。有20位选手的得分在250分以上，57位选手的得分为200分以上，101位选手的得分在150分以上。本题由经典的Set Cover问题修改而来，是一个NP完全问题，但这并不意味着本题纯粹是碰运气或者鼓励投机取巧。 tedcn几乎在所有数据中都得到了所有选手中的最优解，而有的纯随机化程序30个数据加起来只得了不到1分。
龙凡的分析：这道题目比的是在有限的竞赛时间内设计优秀，高效，并且能够实现的近似算法的能力。最终我的代码200多行，算是随机贪心算法中非常长的了。由于时间原因，很多细节都没来得及仔细推敲。如果有足够的时间来调整参数，应该能够得到更优秀的结果。我的算法的基本框架分为三步：
计算每个词语的估价函数。
贪心得到一个词语集合，集合的元素个数在题目要求的范围内。
对贪心得到的解进行随机调整。我在提交的程序中调整了一万次。每次调整有两种可能，一种是增加一个词，一种是删除一个词，然后输出在整个贪心和随机的过程中出现过的最优解（我的算法的调整并不保证每次都将答案往更优的方向调整）。这里有一个细节：上限和下限相等怎么办？这时没有办法增减词了，我的方法是放宽上下限（上限加1，下限减1），最终输出答案时只考虑满足条件的。
估价函数：由于题目要求最小权值尽量大，估价函数要正确反映每个词语的优先度，就需要至少考虑到两个量：
N个人对这个词语的权值总和。显然如果所有人对这个词语的权值都很高，这个词语一定要优先。我们将这个量记为S(i)，i为词语编号。
N个人中对这个词语的权值最低的那个人的权值。即是不是选定这个词语会让某个人权值变得非常低。我们将这个量记为M(i)，i为词语编号。
在我的程序中，对于词语i的估价函数为：
if (M(i)<0)
return S(i)-M(i)*M(i);
else
return S(i);
换句话说，当M(i)为负时对估价函数影响很大，而为正时没有影响。需要说明的是，这个估价函数是比赛时仓促选择的，并不是非常的合理。也许M上的指数取1.5左右，并且当M>0时加上M1.5而不是不考虑M可能效果会更好。
调整过程：我实现的贪心就是先随机决定初始集合的大小，然后取估价函数最大的若干个词语作为集合元素。调整时，删除一个元素就是计算删去每一个在集合中的元素后对答案的影响（集合大小最大为30，消耗不了多少时间），然后删去一个元素使得删去后的答案尽量优（但是不一定比删去前要优）。增加元素的时候比较复杂，因为词语总数可能达到一万，不可能所有词语都尝试一遍。我的处理方法是随机找30个元素，然后选择一个最好的增加。但是我这里的随机不是完全随机，随机选取公式是：
Id = (int)(r*r*T+1);
其中r表示0~1之间的随机数，Id表示的是选中的词语的编号。我之前已经将词语按照估价函数排序，编号越小估价函数值越大。使用这样的选取方法，可以让估价函数大的词语有更大的概率被选中。这是我实际提交的程序使用的公式，考后分析也许将r的指数改为3或更大会更好一些。
下面是第二名chenqifeng的分析。他得到了298.6404分，虽然比第一名略少一点，但是算法简单，容易实现。该算法在规模比较小的数据上表现优异，但规模扩大时和tedcn相比略逊一筹。他也是采用的随机调整，但和上面的分析不同，它采取的是类似于bellman-ford的更新方法，尝试了所有可能的交换方式。当某次迭代没有交换时停止（因为下次迭代也不可能交换）。详细算法如下：
陈启峰的分析：设目标函数Z=min{v1,v2,...,vn}，其中vi为第i个人的总分。从min到max枚举选取单词的个数Si，并执行以下操作：
从所有的单词向量中随机选取Si个；
无条件执行以下迭代：
for 每一个已选的向量A do
for 每一个未选的向量B do
if 交换A、B能使得Z变大 then
交换A、B；
if 本次迭代没有进行过交换 then
break;
用本次迭代得到的最优值Z去更新答案。
只需不断地执行以上随机调整算法直到运行时间超过1.6秒即可。注意在“if交换A、B能使得Z变大”本来需要O(n)次运算和比较，但加入两个重要的剪枝优化可以大大提高实际运行速度：
设当前的Z=Vm，如果Bm-Am<=0，则交换不能使Z变大。
对于i=1,2,...,n，一旦发现Vi+Bi-Ai<=Z，则交换不能使Z变大。
第四题
和第三题相比，第四的题意比较复杂，而在规定时限内算出至少有一次成功维修的可行解也要困难一些，因此仅有约150人提交。由于题目本身的复杂性，不同算法对于不同特点的数据表现有所不同。只有acrush(楼天成)取得了250以上的分数， 10人取得200以上的分数，29人取得150以上的分数，57人取得100以上的分数，不到100人的分数超过10分。下面给出两份分析，两个算法都很典型但又很不相同，有兴趣的选手可以继续研究。
楼天成的分析：本题首先需要做的一件事情是求最短路径。需要注意的是这条路径不能有连续两个点都是建筑物，但并不要求中间点全都是空地。这里不需要求任两点之间的最短路径，只要求每一个Company到所有点的最短路径长度。时间复杂度是O(k*r*c)。接下来主要有两种不同思路：
全局分析——得到一个全局估价函数，然后每一步选择一个全局估价函数最优的方案进行。这样的思想对于估价函数的要求很高。
局部分析——让所有Robot"依次"赶到各Company。
我使用了局部分析的方法，由于时间原因，没有尝试全局分析的思想。下面主要介绍局部分析的一些效果很好的优化：
不需要所有Robot都去当前"选中"的Company，一个Robot不参加某Company的修理的条件是：如果这个Robot赶到该Company时，已经不能提早该Company的REPAIR时间，这个Robot就不去相应的Company。当然此时这个Robot不是普通的IDLE，而是等待时机到达后面被"选中"的Company。具体实现方法就是：记录每个Robot的空闲时间，然后对于每一个新"选中"的Company，按照Robot到达Company的时间前后进行判断是否让该Robot过去。如果不需要构造方案，上述过程的时间复杂度是O(kn)的，和地图的大小无关。
选择合适的修理Comany的顺序，修理的顺序对结果的影响很大。由于O(kn)不是很大，我们可以通过随机调整或者模拟退火法得到比较理想的修理Company的顺序。
朱泽园的分析：由于花费了比较多的时间实现和比较第三题的遗传算法和随机调整，本题我采用的是从开始时刻一个一个时间单位地“模拟”算法。换句话说，每个时间单位依次处理每个修理队。如果他正在修理，并且大厦还没完全修理好，则强制他去修理；否则，让修理队在能走到的所有需要修理的大厦中，选取一个他认为最合适的。这里要有一个估价函数，大约是：
剩余未修理指数B越小，越值得修
已经去修理的人越多，越值得去修
距离除以速度（即时间）越短，越值得去修
P值越大越值得去修（尽可能减小损失）
我在程序中将上述因子直接相乘，事实上还需要作若干修正，就是如果已经去修的人过多，就没太大必要去修了）需要注意的是两点小优化：
计算每个点能走道的其它点，需要一个bfs。这个bfs的hash判重函数可以重复利用，而不要每次进入bfs的时候都重新memset一次，可以大大加快程序运行速度
如果一个维修队已经REST了，以后只能REST，因为他永远走不到任意一个未修完的大厦，就不要再bfs了（这个优化非常重要，在维修队过多的时候可以几百倍地降低程序运行时间）
由于上述程序运行非常快，因此我在估价函数中加入随机因子（即每次不一定选最好的，可能是次好的……），然后运行多次，效果良好。
第一题
这是一道图论和计算几何的综合题。虽然不难，但是比赛时却让不少选手花了很多时间。虽然最后有不少选手获得满分，但是不少选手的程序十分冗长，花费了不少时间才调试通过。我们特地邀请本题获得满分的chenqifeng(陈启峰)写了一份简短的分析，希望各位选手可以从中获得启发：
陈启峰的分析：最优驾车路线一定由若干条直线段依次连接，而这些直线段各属于某些高速公路的一部分。设该路线为(p1,p2),(p2,p3)...(pn-1,pn)，则只要找出所有可能成为pi的点，并求出所有可以成为(pi,pi+1)的边，再用最短路算法即可求出答案。算法步骤如下：
求出所有可能成为pi的点集V。这些点可以分为以下4类：
一条高速公路的两个端点；
两条高速公路的交点；
上车点；
目的地到某条高速公路的垂足（只有垂足在该高速公路上时才保留）
构造边集E：对于每一条高速公路AB，求出V中位于这个高速公路上的所有点，按照离A点的距离排序为v1,v2,...,vk，然后添加(v1,v2)，(v2,v3),...,(vk-1,vk)这k-1条无向边。
以上车起点为源点做一次Dijkstra算法，求出上车起点到V中每个点的最短距离。
注意构造出的图不一定连通，因此只应检查V中所有可达点，选出离终点距离最近的点中驾车距离最小的。
chenqifeng的程序只有107行，不到2.7K，单击此处下载。
第二题
这是一道工程性比较强的题目，它的特别之处在于规范放在外部文档中，并且是英文。这份英文文档并不长（在实际的工程中算是非常短了），但是从贴吧、email和热线询问来看，不少选手仍然没有能够仔细阅读。这里举几个典型的例子：
关于Disallow中URL的含义，规范中写到： The value of this field specifies a partial URL that is not to be visited. This can be a full path, or a partial path; any URL that starts with this value will not be retrieved. 后面甚至还举了例子，但是仍然有选手通过各种途径向我们询问这里是不是指的子串匹配。
关于注释，规范中写到： Lines containing only a comment are discarded completely, and therefore do not indicate a record boundary. 但从测试结果看，仍有部分选手没有处理好这一点。
关于Disallow中的星号，规范中写到： If the value is '*', the record describes the default access policy for any robot that has not matched any of the other records. 也就是说，星号不是指所有user-agent，而是指所有"其他"user-agent. 对这一规则的实现需要小心：如果有两个合法行的User-agent分别是*和Baiduspider，这两行的顺序应该和结果无关。
对于可能产生多种理解的地方，设计测试数据时均已避开。
第三题
本题是提交数量最多的一题，因此每个点分数的粒度比较小。有20位选手的得分在250分以上，57位选手的得分为200分以上，101位选手的得分在150分以上。本题由经典的Set Cover问题修改而来，是一个NP完全问题，但这并不意味着本题纯粹是碰运气或者鼓励投机取巧。 tedcn几乎在所有数据中都得到了所有选手中的最优解，而有的纯随机化程序30个数据加起来只得了不到1分。
龙凡的分析：这道题目比的是在有限的竞赛时间内设计优秀，高效，并且能够实现的近似算法的能力。最终我的代码200多行，算是随机贪心算法中非常长的了。由于时间原因，很多细节都没来得及仔细推敲。如果有足够的时间来调整参数，应该能够得到更优秀的结果。我的算法的基本框架分为三步：
计算每个词语的估价函数。
贪心得到一个词语集合，集合的元素个数在题目要求的范围内。
对贪心得到的解进行随机调整。我在提交的程序中调整了一万次。每次调整有两种可能，一种是增加一个词，一种是删除一个词，然后输出在整个贪心和随机的过程中出现过的最优解（我的算法的调整并不保证每次都将答案往更优的方向调整）。这里有一个细节：上限和下限相等怎么办？这时没有办法增减词了，我的方法是放宽上下限（上限加1，下限减1），最终输出答案时只考虑满足条件的。
估价函数：由于题目要求最小权值尽量大，估价函数要正确反映每个词语的优先度，就需要至少考虑到两个量：
N个人对这个词语的权值总和。显然如果所有人对这个词语的权值都很高，这个词语一定要优先。我们将这个量记为S(i)，i为词语编号。
N个人中对这个词语的权值最低的那个人的权值。即是不是选定这个词语会让某个人权值变得非常低。我们将这个量记为M(i)，i为词语编号。
在我的程序中，对于词语i的估价函数为：
if (M(i)<0)
return S(i)-M(i)*M(i);
else
return S(i);
换句话说，当M(i)为负时对估价函数影响很大，而为正时没有影响。需要说明的是，这个估价函数是比赛时仓促选择的，并不是非常的合理。也许M上的指数取1.5左右，并且当M>0时加上M1.5而不是不考虑M可能效果会更好。
调整过程：我实现的贪心就是先随机决定初始集合的大小，然后取估价函数最大的若干个词语作为集合元素。调整时，删除一个元素就是计算删去每一个在集合中的元素后对答案的影响（集合大小最大为30，消耗不了多少时间），然后删去一个元素使得删去后的答案尽量优（但是不一定比删去前要优）。增加元素的时候比较复杂，因为词语总数可能达到一万，不可能所有词语都尝试一遍。我的处理方法是随机找30个元素，然后选择一个最好的增加。但是我这里的随机不是完全随机，随机选取公式是：
Id = (int)(r*r*T+1);
其中r表示0~1之间的随机数，Id表示的是选中的词语的编号。我之前已经将词语按照估价函数排序，编号越小估价函数值越大。使用这样的选取方法，可以让估价函数大的词语有更大的概率被选中。这是我实际提交的程序使用的公式，考后分析也许将r的指数改为3或更大会更好一些。
下面是第二名chenqifeng的分析。他得到了298.6404分，虽然比第一名略少一点，但是算法简单，容易实现。该算法在规模比较小的数据上表现优异，但规模扩大时和tedcn相比略逊一筹。他也是采用的随机调整，但和上面的分析不同，它采取的是类似于bellman-ford的更新方法，尝试了所有可能的交换方式。当某次迭代没有交换时停止（因为下次迭代也不可能交换）。详细算法如下：
陈启峰的分析：设目标函数Z=min{v1,v2,...,vn}，其中vi为第i个人的总分。从min到max枚举选取单词的个数Si，并执行以下操作：
从所有的单词向量中随机选取Si个；
无条件执行以下迭代：
for 每一个已选的向量A do
for 每一个未选的向量B do
if 交换A、B能使得Z变大 then
交换A、B；
if 本次迭代没有进行过交换 then
break;
用本次迭代得到的最优值Z去更新答案。
只需不断地执行以上随机调整算法直到运行时间超过1.6秒即可。注意在“if交换A、B能使得Z变大”本来需要O(n)次运算和比较，但加入两个重要的剪枝优化可以大大提高实际运行速度：
设当前的Z=Vm，如果Bm-Am<=0，则交换不能使Z变大。
对于i=1,2,...,n，一旦发现Vi+Bi-Ai<=Z，则交换不能使Z变大。
第四题
和第三题相比，第四的题意比较复杂，而在规定时限内算出至少有一次成功维修的可行解也要困难一些，因此仅有约150人提交。由于题目本身的复杂性，不同算法对于不同特点的数据表现有所不同。只有acrush(楼天成)取得了250以上的分数， 10人取得200以上的分数，29人取得150以上的分数，57人取得100以上的分数，不到100人的分数超过10分。下面给出两份分析，两个算法都很典型但又很不相同，有兴趣的选手可以继续研究。
楼天成的分析：本题首先需要做的一件事情是求最短路径。需要注意的是这条路径不能有连续两个点都是建筑物，但并不要求中间点全都是空地。这里不需要求任两点之间的最短路径，只要求每一个Company到所有点的最短路径长度。时间复杂度是O(k*r*c)。接下来主要有两种不同思路：
全局分析——得到一个全局估价函数，然后每一步选择一个全局估价函数最优的方案进行。这样的思想对于估价函数的要求很高。
局部分析——让所有Robot"依次"赶到各Company。
我使用了局部分析的方法，由于时间原因，没有尝试全局分析的思想。下面主要介绍局部分析的一些效果很好的优化：
不需要所有Robot都去当前"选中"的Company，一个Robot不参加某Company的修理的条件是：如果这个Robot赶到该Company时，已经不能提早该Company的REPAIR时间，这个Robot就不去相应的Company。当然此时这个Robot不是普通的IDLE，而是等待时机到达后面被"选中"的Company。具体实现方法就是：记录每个Robot的空闲时间，然后对于每一个新"选中"的Company，按照Robot到达Company的时间前后进行判断是否让该Robot过去。如果不需要构造方案，上述过程的时间复杂度是O(kn)的，和地图的大小无关。
选择合适的修理Comany的顺序，修理的顺序对结果的影响很大。由于O(kn)不是很大，我们可以通过随机调整或者模拟退火法得到比较理想的修理Company的顺序。
朱泽园的分析：由于花费了比较多的时间实现和比较第三题的遗传算法和随机调整，本题我采用的是从开始时刻一个一个时间单位地“模拟”算法。换句话说，每个时间单位依次处理每个修理队。如果他正在修理，并且大厦还没完全修理好，则强制他去修理；否则，让修理队在能走到的所有需要修理的大厦中，选取一个他认为最合适的。这里要有一个估价函数，大约是：
剩余未修理指数B越小，越值得修
已经去修理的人越多，越值得去修
距离除以速度（即时间）越短，越值得去修
P值越大越值得去修（尽可能减小损失）
我在程序中将上述因子直接相乘，事实上还需要作若干修正，就是如果已经去修的人过多，就没太大必要去修了）需要注意的是两点小优化：
计算每个点能走道的其它点，需要一个bfs。这个bfs的hash判重函数可以重复利用，而不要每次进入bfs的时候都重新memset一次，可以大大加快程序运行速度
如果一个维修队已经REST了，以后只能REST，因为他永远走不到任意一个未修完的大厦，就不要再bfs了（这个优化非常重要，在维修队过多的时候可以几百倍地降低程序运行时间）
由于上述程序运行非常快，因此我在估价函数中加入随机因子（即每次不一定选最好的，可能是次好的……），然后运行多次，效果良好。