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:/,
copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1