资源描述：
《byvoid魔兽世界模拟赛解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、BYVoid魔兽世界模拟赛Stage.32009年10月31日题目一览题目算法难易度彩色穿孔卡片区间扫描合并★★★艾萨拉的激流动态规划★★阿鲁高的阴谋动态规划背包问题★★★潜入辛迪加搜索★★★★比赛情况共60人参赛400分有1人，Winmad。300分以上有6人。200分以上有23人。比赛情况100分0分彩色穿孔卡片15人15人艾萨拉的激流44人3人阿鲁高的阴谋15人33人潜入辛迪加2人44人首先，我们来理清一下题意。题述大意是在一个数轴上，有N条线段被依次画上。后画上的线段会将原来的部分线段覆盖。最后问到能够在数轴上看到多少条线段，比如样例数据405（红）38（
2、黄）56（盖）47（蓝）彩色穿孔卡片算法一我们可以模仿NOIP2005普及组校门外的树的做法，用一个标志数组f(i)表示数轴上第i个单元格的最上层线段的标号。一次读入线段的始点与终点，更新之间单元格的最上层线段。最后扫描一遍即可。显然，对于题目中给出的数据范围，这种方法只能拿到50%的分数。这个方法之所以慢的原因是什么呢？因为这个方法把数轴分成了一个一个的单元格，但是线段的数目又是相对较少的，也就是说会有大段大段的相同标号的格子，我们设法尽量将相同标号的格子合在一起。下面将给出基于离散化思想的两种算法。算法二对于给定的两条线段a(A1,B1)和b(A2,B2)（假
3、设b在a之后被放在数轴上），两者若满足B1<=A2或B2<=A1则两者不相交。否则，两者相交。现在分析一下两者相交的情况。1、b将a完全覆盖(A2<=A1且B1<=B2)2、b将a部分覆盖，此时，两条线段将被分为几部分，如下图原本的两条线段a、b被分为三条线段(A1,A2),(A2,B2),(B2,B1)（此三条线段若终点大于起点，则线段不存在）有了上述分析，我们可以构造出来这样一个算法。按照题给顺序依次读入线段b，建一队列来保存所有互不相交的线段。若队为空，则将b入栈。否则，用b更新队列，因为b的优先级大于队列中所有元素的优先级。所以，更新时，先取出队头元素a（
4、并将队列中的队首删除）,根据相交情况，将a与b分解为若干条不相交的线段，将a的部分加入队列，直到将队列中的元素更新完毕，再将b加入队列。最后扫描一遍即可。时间复杂度：O(n^2)算法三首先，将所有的起点与终点放在一起排序*，对于样例，如下图每个点都有两个属性，一个表明它是起点还是终点，一个表明它的优先级。如上图，我们从左向右扫描。K的意义为当前点到下一个点的区间的最高优先级。K=1K=2K=4K=4K=4K=2K=0对于这个算法，我们需要维护位于某个点时，当前的优先级都有哪些，比如在区间(3,4)，此时存在的优先级有(1,2)，而在区间(5,6)，优先级包含(2,
5、3,1)（因为1号优先级在5点位置已经结束）。在从左向右的扫描过程中，K的意义为当前点到下一个点的区间的最高优先级。如果遇到起点，应当把这个起点的优先级加入优先级集合，并在优先级集合中取出最大的一个为K的当前值；如果遇到终点，应当把终点所对应的优先级从优先级集合中去除，并取一个最大的优先级作为K的值。若优先级集合为空，则K=0。最后的答案即为K曾出现的优先级的种数。因为K的特殊意义，我们需要在排序的时候注意以下细节排序细节安排a点与b点的前后顺序如果a与b的坐标不相等，则将坐标小的放前面，坐标大的放后面。否则，如果a与b同为起点，则将优先级大的放在前面，将优先级小
6、的放在后面，如果a与b同为终点，则将优先级小的放在前面，优先级大的放在后面。否则，如果a与b一个为起点一个为终点，应该把起点放在前面，终点放在后面。这个算法的时间复杂度因维护优先级集合的方法而异。若用线性表维护，总时间复杂度为O(n*n)；若用堆或排序二叉树来维护，总的时间复杂度为O(n*logn)当前扫描点：优先级集合：K的当前值：K曾出现的值：(0,s,1)111(3,s,2)222(4,s,4)(5,t,1)(5,s,3)(6,t,3)(7,t,4)(8,t,2)44432ANS=3分析此题，我们可以知道，从上游到下游，每过单位时间，船舶将向下游移动一个单位
7、，而在移动的这个单位时，船舶可以选择与河流流向垂直的方向移动一格或者不动。目标为在整个过程中，使经过的格子的宝藏的数目之和尽量多。艾萨拉的激流很显然，这是一个多阶段决策的动态规划问题。设状态为f(i,j)示离上游距离为i，距岸边（指面向下游的左岸）距离为j时，能够吊上的最多的鱼的数目。状态转移方程：f(i,j)=max{f(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目标状态max{f(L,j)}(j=1..W)时间复杂度O(W*L)这是一道比较简单的动
8、态规划题目
