BYVoid魔兽世界邀请赛-NOIP2011模拟赛4.doc

BYVoid魔兽世界邀请赛-NOIP2011模拟赛 v（搜索与DP）之血精灵AND娜迦专场测试时间：3小时【题目一览】题号第一题第二题第三题第四题题目名称寻找尤迪安横渡法斯琪条件巴尔泽那被证实的预言提交文件find.pas/c/cppthrough.pas/c/cppcondition.pas/c/cppsyndicate.pas/cpp输入文件hrough.incondition.insyndicate.in输出文件find.outthrough.outcondition.outsyndicate.out时间限制1s1s1s1s空间限制64MB64MB64MB64MB分值100100100100寻找尤迪安【问题描述】 “阿尔萨斯王子在那刺向寒冰之冠的辉煌的那一剑，也就注定了他数年后的消亡。”麦迪文手记之守护者的预言在诺德森一役中，幸存下来的血精灵王凯尔得知他忠效的主人恶魔猎手尤迪安没有死在霜之哀伤之下，而是被之前耐奥祖分流出来的力量所困住！这是一个重要的消息。但是，耐奥祖的力量形成了一个庞大的磁场矩阵，而在这个磁场内行走需要魔法，这对魔法充满渴望的血精灵来说是一个噩梦，但是必须找到主人！血精灵们发现，这个矩阵内有许多能量溢出点，他们可以用这些溢出的能量来补充魔法。能量溢出点的能量用完后，则变为平地。你就是凯尔，你需要在磁场矩阵中走最少的步数来救你的主人，当然，聪明的你会使用最少的魔法的。【输入格式】 第一行为一个整数N，表示一个N*N的矩阵。（N50） 接下来N+1行为矩阵的描述，其中0为空地，1为磁场，不可通行，3为能量溢出点。 接下来一行，为两个整数A，B，表示凯尔的魔法初始值和每个能量溢出点能补充的魔法。 提示（凯尔初始位置默认为（1,1），尤迪安的默认位置为（N，N）【输出格式】 输出文件为两行，第一行为最少步数，第二行为最少使用魔法值。（由于剧情需要，数据不提供无解）。 【输入输出样例】输入：50 0 0 0 30 1 0 0 01 1 0 3 00 1 1 1 00 0 0 0 05 4输出：84（能量溢出点提供的魔法所消耗不算）横渡法斯琪【问题描述】 你成功的就出了主人尤迪安，他召集了部下-娜迦族。但他发现，海妖们并没有过来。他通过横渡的瓦格里尔-娜迦暴徒们口中的知海妖们和她们的领袖法斯琪女士正在与洛伦丹边境的亡灵们作战。尤迪安召集了一些船只运送他的部队。但是，光靠现有的部队去击溃亡灵们是远远不够的。幸运的是，在海洋上，有许多正在横渡的娜迦族们。如果靠近他们，他们会自愿加入。但是航行需要时间，你必须在最短的时间内到达并援助法斯琪女士。【输入格式】第一行为两个整数N，M，表示一个N*M的矩阵。（M=N75）接下来N+1行为矩阵的描述，其中每个格子都有一个数字来描述航行所要的时间。如果该格子有娜迦族，则用字母表示。A代表有1名娜迦族人，B表示有两名，以此类推，而航行时间默认为1。接下来的一行为两个整数A,B，表示初始兵力A与所需兵力B。【输出格式】 输出文件为一行，表示最短天数。（由于剧情需要，数据不提供无解）。【输入输出样例】输入：5 50 2 5 6 92 A B 1 10C E 1 6 57 7 1 1 5A A A A 012 19输出：8条件巴尔泽那【问题背景】 你成功的消灭了洛伦丹边境的亡灵军队。但是细心的法斯琪女士发现，他们的力量似乎不来自于巫妖王-阿尔萨斯。而且缺失了重要的成员-亡灵巫师。那是巫妖-克尔德加苏的信徒们。似乎在洛伦丹，亡灵的统治发生了巨变。翌日，法斯琪的想法得到了证实。洛伦丹亡灵新的统治者之一，恐惧魔王-巴尔泽那找上了尤迪安。原来，在阿尔萨斯王子的诺德森之战中，巴尔泽那与追风者-西瓦娜动了政变，攻占了洛伦丹人类人类联盟的首都并杀死了原先的统治者-恐惧魔王-德拉瑞克特与联盟首脑之一的黑暗骑士-加里瑟斯。他们创立了新的种族-遗族。阿尔萨斯王子回来之后，与地穴领主-阿尔克萨在克尔德加苏的迎接下，又重新占领了拉达然，以变重新汲取召唤阿克蒙德时遗留下来的庞大能量，来增强他们不死疫军的战斗力。这引起了所有拉达然生物的愤怒。安东达尼斯之子他们在西边的瑞斯特山脉集结了部队进行进攻，而遗族也已经与他们结盟，共同抗击亡灵。尤迪安希望加入这个联盟，以便击溃亡灵，完成主人基尔加丹的任务。但他们似乎不欢迎低智力者，只有通过任务才可以加盟。现在，主人把任务交给了你！【问题描述】 巴尔泽那在之前的战争中，将自己庞大的遗族部队n分成m个支团，由于已经在过去几天前与联盟，部落确定了总攻时间，他急需将自己的部队尽可能集结在一个点上。由于需要，你可以同时调动S支军队。他给了你每支军队的位置（xi，yi）以及每支军队的人数ai。由于每支军队的成员不同，他们的移动速度分别为zi。你的任务是将巴尔泽那的军队尽可能多的集结。【输入格式】 第一行为两个整数N表示共有N个支团。 第二行为一个整数K，S为最少集结的军队数目和你可以调动的军队数。 第三行为两个整数C，D，为集结地点。 第四行为一个整数，Q表示共有的Q个时间。 接下来的M行，为四个整数（xi，yi，ai，zi）其中xi与yi描述的是第I支军队的位