1、BYVoid 魔兽世界模拟赛,Stage.3 2009年10月31日,题目一览,比赛情况,共60人参赛400分有1人，Winmad。 300分以上有6人。 200分以上有23人。,比赛情况,首先，我们来理清一下题意。题述大意是在一个数轴上，有N条线段被依次画上。后画上的线段会将原来的部分线段覆盖。最后问到能够在数轴上看到多少条线段，比如样例数据,40 5（红）3 8（黄）5 6（盖）4 7（蓝）,彩色穿孔卡片,算法一我们可以模仿NOIP2005普及组校门外的树的做法，用一个标志数组f(i)表示数轴上第i个单元格的最上层线段的标号。一次读入线段的始点与终点，更新之间单元格的最上层线段。最后扫描一
2、遍即可。显然，对于题目中给出的数据范围，这种方法只能拿到50%的分数。这个方法之所以慢的原因是什么呢？因为这个方法把数轴分成了一个一个的单元格，但是线段的数目又是相对较少的，也就是说会有大段大段的相同标号的格子，我们设法尽量将相同标号的格子合在一起。下面将给出基于离散化思想的两种算法。,算法二对于给定的两条线段a(A1,B1)和b(A2,B2)（假设b在a之后被放在数轴上），两者若满足 B1=A2或B2=A1 则两者不相交。否则，两者相交。现在分析一下两者相交的情况。 1、b将a完全覆盖(A2=A1且B1=B2) 2、b将a部分覆盖，此时，两条线段将被分为几部分，如下图,原本的两条线段a、b被
3、分为三条线段(A1,A2),(A2,B2),(B2,B1)（此三条线段若终点大于起点，则线段不存在）,有了上述分析，我们可以构造出来这样一个算法。按照题给顺序依次读入线段b，建一队列来保存所有互不相交的线段。若队为空，则将b入栈。否则，用b更新队列，因为b的优先级大于队列中所有元素的优先级。所以，更新时，先取出队头元素a（并将队列中的队首删除）,根据相交情况，将a与b分解为若干条不相交的线段，将a的部分加入队列，直到将队列中的元素更新完毕，再将b加入队列。最后扫描一遍即可。时间复杂度：O(n2),算法三首先，将所有的起点与终点放在一起排序*，对于样例，如下图,每个点都有两个属性，一个表明它是起
4、点还是终点，一个表明它的优先级。如上图，我们从左向右扫描。 K的意义为当前点到下一个点的区间的最高优先级。,K=1,K=2,K=4,K=4,K=4,K=2,K=0,对于这个算法，我们需要维护位于某个点时，当前的优先级都有哪些，比如在区间(3,4)，此时存在的优先级有(1,2)，而在区间(5,6)，优先级包含(2,3,1)（因为1号优先级在5点位置已经结束）。在从左向右的扫描过程中，K的意义为当前点到下一个点的区间的最高优先级。如果遇到起点，应当把这个起点的优先级加入优先级集合，并在优先级集合中取出最大的一个为K的当前值；如果遇到终点，应当把终点所对应的优先级从优先级集合中去除，并取一个最大的优
5、先级作为K的值。若优先级集合为空，则K=0。最后的答案即为K曾出现的优先级的种数。,因为K的特殊意义，我们需要在排序的时候注意以下细节 排序细节安排a点与b点的前后顺序如果a与b的坐标不相等，则将坐标小的放前面，坐标大的放后面。否则，如果a与b同为起点，则将优先级大的放在前面，将优先级小的放在后面，如果a与b同为终点，则将优先级小的放在前面，优先级大的放在后面。否则，如果a与b一个为起点一个为终点，应该把起点放在前面，终点放在后面。这个算法的时间复杂度因维护优先级集合的方法而异。若用线性表维护，总时间复杂度为O(n*n)；若用堆或排序二叉树来维护，总的时间复杂度为O(n*log n),当前扫描
6、点：,优先级集合：,K的当前值：,K曾出现的值：,(0,s,1),1,1,1,(3,s,2),2,2,2,(4,s,4),(5,t,1),(5,s,3),(6,t,3),(7,t,4),(8,t,2),4,4,4,3,2,ANS=3,分析此题，我们可以知道，从上游到下游，每过单位时间，船舶将向下游移动一个单位，而在移动的这个单位时，船舶可以选择与河流流向垂直的方向移动一格或者不动。目标为在整个过程中，使经过的格子的宝藏的数目之和尽量多。,艾萨拉的激流,很显然，这是一个多阶段决策的动态规划问题。设状态为f(i,j)示离上游距离为i，距岸边（指面向下游的左岸）距离为j时，能够吊上的最多的鱼的数目。
7、状态转移方程：f(i,j)=maxf(i-1,j),f(i-1,j-1),f(i-1,j+1)+fish(i,j) 如果(i,j)位置为障碍物，则f(i,j)=INF。初始状态f(0,j)0目标状态maxf(L,j)(j=1W)时间复杂度 O(W*L)这是一道比较简单的动态规划题目。,本題的变量比较多，有些麻烦。我们再来理清一下船、联盟港口、结界的关系。船每天都有一个燃料的需求，而这个需求需要从港口或者结界来补充，掠夺港口需要一定的代价，而携带燃料同样有一定的代价，且携带燃料有一个上限。更直白一些，需求者为船，商品供应者为港口，而结界就是一个燃料仓库。,阿鲁高的阴谋,由于在每个港口都需要做一个
8、决策，那就是要上岸掠夺多少燃料。这样，就让我们看到了问题的解决思路多阶段决策的动态规划在每个港口，我都需要做一个掠夺多少燃料的决策，我们把状态设为(k,s),k表示这是第几天，s表示在这一天的开始，魔法结界中保存的燃料数。令f(k,s)表示第k天开始时结界中存有s单位燃料时，从第k天开始至旅程结束的最少魔法消耗。,如果一个状态为(k,s)，那么如果在第k天掠夺x单位燃料。那么，下一个阶段(k,s)即为(k+1,s+x-N(k) (N(k)表示第k天的消耗)，而从(k,s)跳转到(k,s)，连结这两个状态的法力消耗为B(k)*x+W*(s+x-N(k)，其中，B(k)*x为抢夺燃料的法力消耗，W
9、*(s+x-N(k)为保存燃料所需的法力值。由于每个港口的存储量A与魔法结界的最大存储量V的限制，我们必须保证x=A , s+x-N(k)=V由于需求必须被满足，则0=s+x-N(k)。综上，得出 N(k)-s=x 0=x=A x=V+N(k)-s同时，s本身也必须满足实际的要求(0=s=V),通过上述分析，我们可以写出状态转移方程,f(k,s)=min(f(k+1,s+x-N(k)+B(k)*x+W*(s+x-N(k)MAX(N(k)-s,0)=x=MIN(A,V+N(k)-s)初始状态：f(k+1,s)=0 (s=0V)目标状态：f(1,0)时间复杂度：O(T*V*A),本题的模型在日常生
10、活中很常见。题目中的结界为抽象的仓库，而燃油即为商品。我们可以购买一些商品放入仓库。每天都有一个需要值，我们可以购买物品来满足需求，也可以从仓库中取出来满足需求。仓库有一定的存储费用，物品的价值不断变化。这是一个很典型的多阶段决策问题。在的2.17中有详细介绍。,模型,潜入辛迪加,这是一道经典的分层搜索问题。该题来自CTSC1999 拯救大兵瑞恩。原题为走迷宫问题，要使用钥匙开门。而该题仍然是走迷宫，破坏防御系统，与拿钥匙开门本质上是相同的。,问题简述,在迷宫中只能上下左右四个方向移动，不能进入障碍物和卫兵的视线。不能进入没有被摧毁的监视器。摧毁供电装置，对应的监视器失效。起点为(1,1)终点
11、为（N,N)。,问题简化,可见，卫兵的监视范围和障碍物是没有区别的，我们可以把卫兵的监视范围初始化为障碍物。监视器为一种特殊的障碍物，可以被摧毁。,算法设计,假如没有监视器的存在，这道题怎么做？广度优先搜索！搜索从起点到终点的步数。记录走过的点，不再访问。有了监视器怎么办？,算法设计,还是广搜。但是我们不能简单的记录走过的点一定不再走，因为我们会去专门破坏供电装置，然后返回。思考，什么情况下返回？ 当然，一般情况下，返回是毫无意义的，只有破坏了供电装置 ，返回才是有必要的。,算法设计,用哈希表再加一维记录当前破坏的状态下走过的顶点。广搜到新的位置时，如果改变了破坏状态，那么用一维新的哈希表记录走过的顶点。,算法设计,这就是分层搜索的思想，想象我们破坏了新的装置时，进入了新的一层地图，一切脚步都要重走。用二进制表示装置破坏的状况，开辟2M个哈希表。,谢谢,作者：BYVoid欢迎访问 http:/,
