《WOW模拟赛Stage.3 BYVoid.doc》由会员分享，可在线阅读，更多相关《WOW模拟赛Stage.3 BYVoid.doc（11页珍藏版）》请在金锄头文库上搜索。
1、BYVoidhttp:/ BYVoid魔兽世界模拟赛 Stage.3题目名称彩色穿孔卡片艾萨拉的激流阿鲁高的阴谋潜入辛迪加源文件名(.c/.cpp/.pas)punchazsharaarugalsyndicate输入文件名punch.inazshara.inarugal.insyndicate.in输出文件名punch.outazshara.outarugal.outsyndicate.out时间限制(s)1111空间限制(MB)512512512512比赛说明l 本次比赛所用题目全部系BYVoid独家原创，转载必须注明作者。l 比赛所有题目背景均来自魔兽世界，本人在其故事上进行再创作。l 请
2、勿在现实生活中模仿故事中任何人物的行为。l 所有题目中涉及到的整数运算，均不超过32位带符号整型范围。彩色穿孔卡片问题描述“在逃离诺莫瑞根的时候，我们留下了太多的数据！非常重要的数据！”大机械师卡斯派普十分着急地说，“尽管我们已经从矩阵打孔计算机上拿回了许多彩色穿孔卡片，但是混乱的数据令人无法忍受！”自从诺莫瑞根陷落以后，侏儒们一直寄居在铁炉堡中。大机械师卡斯派普花了不少钱来悬赏勇士们去诺莫瑞根替他取回一些卡片，现在他已经有了一大堆彩色穿孔卡片。但是这些卡片都是残缺不全的，有的甚至还是无效的，想从这些破烂中恢复数据，实在是一件不容易的事。卡斯派普发现每个卡片的开头和结尾都有标记，记录着它原本在
3、矩阵打孔计算机中序列的位置，于是想出了一个恢复数据的方法。把每张卡片看成数轴上的一条线段，开头和结尾的标记A,B为数轴上的两个点。卡斯派普按拿到的顺序把卡片一张一张地贴到数轴上，每张卡片的颜色都不同。他想知道贴完卡片以后的数轴上一共有多少种不同的颜色。卡斯派普请你帮助他写一个程序来解决这个问题。 输入格式l 第1行：一个整数N，表示卡斯派普收集到的卡片的数量。l 第2行至第N1行：第i+1行给出了第i张卡片的头尾两个标记Ai,Bi，贴卡片的顺序与输入文件中出现的先后顺序一致。输出格式l 一个整数，表示卡斯派普能在数轴上看到的不同的颜色的数目。样例输入40 53 85 64 7样例输出3样例说明
4、如图所示可以看到的不同颜色的卡片数为3，3号卡片被4号卡片所覆盖。数据规模50%的数据满足N=1,000； 0=AiBi=100,000(1=i=N);100%的数据满足N=20,000； 0=AiBi=1,000,000,000(1=i下游1234515-154202171-11033-11075如上表，探险队从(1,1)开始，第1秒向右转一下，被冲到(2,2)。第2秒向左转一下，被冲到(3,1)。接下来第3秒正前行走，经过(4,1),(5,1)，一共拿到5+7+5+4+20=41个单位的宝藏。数据规模1=W=10001=L=10000所有涉及到的数字不会超过32位带符号整型的范围阿鲁高的阴
5、谋问题描述我尝流连于格雷迈恩之墙，叹息着轻抚隔世的沧桑。我曾徜徉于洛丹米尔的水，飘离在腐败的气息之上。卫道士有卫道士的避风港，叛节者有叛节者的理想乡。魔法师有魔法师的墓志铭，造物主有造物主的礼拜堂。影牙城堡的主人，执着于疯狂。牙将被诅咒磨砺，影终被黑夜深藏。我曾抬头看着银松穹顶的冷光，血月的辉耀隐约中露出寒芒。巨大的引力牵动着星辰的轨道，谁又看得到这个世界的真相。在第三次战争中，达拉然被燃烧军团彻底催化。曾经是肯瑞托的一名成员的阿鲁高，在不断的失败和恐惧中，召唤了远古的恶魔贪婪而又凶猛的沃根。沃根恐怖的力量很快清理了附近的亡灵天灾，但是它也开始对肯瑞托发起了攻击。可悲的是，阿鲁高也堕入了恶魔力
6、量的深渊，他把附了沃根魔法的手腕强加在自己的朋友手上，让他们变成了奴仆。一个夜晚，阿鲁高带领沃根悄悄穿越格雷迈恩之墙，进攻了影牙城堡。原来辉煌的城堡，顷刻间被阴影和血腥味所笼罩。隐身于城堡内高高的塔顶不断扩充自己的军队，幻想有一天可以成为这片大陆的主人。终于有一天，巫妖王剥夺了阿鲁高死亡的权利，把阿鲁高变成了他当年痛恨的敌人，亡灵天灾。在诺森德，阿鲁高建立了血月神教，领导狼人们成为了天灾军团的爪牙。在灰陵的海岸上，阿鲁高建立了第一个据点，并让手下变成人形骗取了联盟军团的信任。银溪镇的追随者们为阿鲁高制造了一个船，用于在海岸上扩张。在漫长的旅途中，阿鲁高必须消耗法力创造结界以存储燃料。在途中每一
7、天，阿鲁高都可以驶到一个联盟港口骗取燃料，代价是消耗法力维持幻象。阿鲁高的目标是寒冰皇冠，要航行T天才能到达。由于天气和海域的不同，每天航行所需的燃料消耗也不同。每天都可以到达一个联盟港口，骗取一些燃料（也可以不去，从结界中取得燃料补充所需，注意，每天的消耗必须被满足），骗取每个单位燃料需要一定的法力消耗。如果骗取的燃料除供这一天消耗外还有剩余，则必须把它存到法力结界中，但是限于结界规模，只能把不超过V的燃料存储到结界中。在结界中存储的每个单位的燃料每天会消耗掉阿鲁高的W点法力值。为了留有足够多的法力，阿鲁高必须尽量地减少法力消耗。请你算出阿鲁高到达目标最少的法力消耗是多少。输入格式l 第1行
8、，四个整数，航行的天数T，结界的最大存储量V，每个港口的库存A，结界中每存储一单位燃料一天的法力消耗W。l 第2行至第1+T行，第k+1行有两个整数，分别表示第k天的需要的燃料Nk，抢夺第k天到达的港口的每个单位燃料的法力消耗Bk。输出格式l 第1行，最小的法力消耗。l 第2行至第1+T行，第k+1行有一个整数，表示第k天到达港口后抢夺燃料的数量。如果有多种解，使每天抢夺的燃料数组成一个序列，所有这些序列构成一个集合，对这个集合进行第一位为第一关键字，第二位为第二关键字，的多关键字排序，输出其中最小的一个即可。样例输入2 5 10 55 203 30样例输出17580样例说明在第1天骗取8个单
9、位燃料，法力消耗8*20=160。5个用于当天直接使用，3个放入结界，存储法力消耗3*5=15。在第2天不需骗取，直接使用结界中的3个单位燃料。所以总法力消耗为160+15=175。数据规模1=T=10001=V，A，W，Bi=1001=Ni=V潜入辛迪加问题描述“我们最新的研究成果毒药研究方案被可恶的辛迪加间谍偷走了！”作为拉文霍德的一员，你一定感到很震惊，因为它是我们最尖端的科研人员的一年的研究成果。被辛迪加获得，我们可能会有灭顶之灾。狡猾的辛迪加为了躲避我们的追杀，他们并没有把毒药研究方案带回激流堡，而是藏了起来。但是终究是我们技高一筹，通过购买侏儒的最新研究成果“静电放射探测器”，我们
10、已经发现了他们的藏身之地。原来他们早就在奥特兰克山脉的地下修建了一个巨大的城市，现在，他们就把毒药研究方案放在了城市的最深处。更好的消息是，我们已经发现了地下城的入口。作为一名出色的盗贼，你要学会以彼之道，还施彼身把毒药研究方案偷回来。然而辛迪加布置了严密的防御，更糟糕的是，他们从地精购买了电磁监视器。无论你的潜行技巧有多么高明，只要一接近它，就会出发警报。只有破坏它的供电系统，才能电磁监视器悄无声息得失效。现在，“静电放射探测器”已经为我们生成了一张地图，它可以告诉你整个地下城的布局结构，包括每一个电磁监视器的位置，及其供电装置的位置。辛迪加的地下城可以被描述为一个N*N的表格，城市的入口在
11、(1,1)处，目标毒药研究方案在(N,N)处。每个单元格可能是一片空地、一个障碍物、一个辛迪加卫士、一个电磁监视器、或者一个的供电装置。从入口处开始，每步你只能向上、下、左、右移动到相邻的一个单元格，不可以停留在原地。你只能进入空地，或者失去供电系统的电磁监视器的位置，或者摧毁供电装置。你不能移动到障碍物上，也不能进入辛迪加卫士的视线中。辛迪加卫士可以监视自己所在单元格以及上下左右共五格的位置，而且他们的视线可以重叠。你不能杀死辛迪加卫士，也不能被他们发现。每个电磁监视器的供电装置可能存在，也可能无法破坏或者根本不存在。一个供电装置也可能会对应零个、一个或多个电磁监视器，意味着摧毁它，对应的所
12、有电磁监视器都会失效。(1,1)和(N,N)一定是可以通行的。拉文霍德要求你在执行任务之前首先给出一个计划书，即要求算出至少一共需要多少步，才能拿到我们的毒药研究方案。 输入格式第1行，两个整数N, M。表示地图大小为N*N，供电装置的数量为M。第2-N+1行，每行N个整数，每个整数i可能是0，-1，-2或者一个正整数。i=0表示该位置为一块空地，i=-1表示该位置为一个障碍物，i=-2表示该位置为一个辛迪加卫士。如果i是一个属于1,M的正整数，则表示该位置为一个供电装置，其编号为i。如果i是一个大于M的正整数，则表示该位置为一个电磁监视器，它的电力由编号为i-M的供电装置提供。输出格式一个整数，为拿到毒药研究方案所需的最少的步数。样例输入6 20 0 0 -2 -1 2-1 0 0 0 -1 0-2 0 0 0 3 3-2 0 0 -1 -1 40 -1 0 0 -1 01 0 0 0 -1 0样例输出24样例说明地图如下图，S为入口，T为目标，黑色的单元格为障碍物。每个E表示一个卫兵，(E)为卫兵的监视范围。K1表示供电装置1，K2表示供电装置2。D1表示供电装置为1的电磁监视器，D2表示供电装置为2的电磁监视器。最优的路线为(1,1) (1,2) (2,2
