选拔题目第二试选拔题目第二试.docVIP

JSOI2008江苏省代表队组队第三轮选拔赛 本次竞赛共分两试，本试卷为第二试 第二试试题 竞赛时间：2008年4 月 28 日7:30—12:30 试题说明 试题名称 分值 源文件 输入文件 输出文件 限时 星球大战 85 starwar starwar.in starwar.out ≤3s 魔兽地图 100 DotR DotR.in DotR.out ≤2s 巨额奖金 115 Award Award.in Award.out ≤1s 分数分布 第一试共三道题，满分为300 分。 文件命名 选手提交源程序，名字见每题标题，并最终拷贝到指定硬盘的相应目录。 源文件的名字应与编译后的可执行程序同名。 选手程序应从 .IN中读入输入数据，不需要进行判错处理。执行结果存放到 .OUT中。输入输出文件均不需指定目录。 程序运行要求 评测时采用黑盒测试。每题均为十个测试点。对每个测试点有一定的时间限制和分数。选手程序必须在此时限内运行结束并输出正确的结果才能得到这个点的分数。 程序运行时仅对指定的文件读写，不应在屏幕上显示任何信息或者等待键盘输入。文件各行所有数据均用一个空格隔开。 输出结果应按题面要求，不应有多余的字符。 题一 星球大战 StarWar/.IN/.OUT/.PAS/.EXE 问题描述 很久以前，在一个遥远的银河系……对反抗军来说，这是一个黑暗的时刻。虽然帝国军的终极武器“死亡星球”已经被摧毁，帝国的军队仍然把反抗军从隐藏的军事基地中赶出，并在整个银河系展开追逐。 考虑到邪恶的帝国完全有能力在短时间内制造出“死亡星球”的替代品，为了避免被一次全部歼灭，反抗军的指挥官决定把部队分散在很多星球上。可是，这样会带来通讯上的问题。某些星球之间可以通过“以太”隧道直接通讯，而没有隧道相连的星球之间的通讯就需要其他星球帮忙转发。因此，只有两个星球之间存在一条由“以太”隧道拼接成的路径，它们才可以正常通讯。 银河历2008年4月1日凌晨，反抗军最担心的事情还是发生了。反抗军司令部收到间谍的秘密通知：帝国军成功制造出第二代“死亡星球”，并将依次摧毁如下星球（星球列表略）。指挥官希望迅速计算出每次攻击之后通讯网络的连通情况，即反叛军所占据的星球被分成了多少个连通支，从而帮助决定在何时发动反击。 输入 输入文件starwar.in的第一行包含两个整数N (2 ≤ N ≤ 2M)和M (1 ≤ M ≤ 200,000)，分别表示星球的数目和 “以太”隧道的数目。星球用0到N – 1的整数编号。 接下来的M行，每行包含两个整数X和Y (0 ≤ X ≠ Y N)，表示星球X和星球Y之间有“以太”隧道，可以直接通讯。 接下来的一行包含一个整数K，表示将遭受攻击的星球的数目。 接下来的K行，每行一个整数，按照顺序列出了帝国军的攻击目标。这K个数互不相同，且都在0到N – 1的范围内。 输出 请将输出写至文件starwar.out。 输出文件应该包含K + 1行，每行一个整数。 第一个整数表示开始时通讯网络的连通支个数。 接下来的第I (1 ≤ I ≤ K)个整数，表示在攻击列表上的第I个星球被摧毁后，通讯网络的连通支个数。 样例 starwar.in starwar.out 8 13 0 1 1 6 6 5 5 0 0 6 1 2 2 3 3 4 4 5 7 1 7 2 7 6 3 6 5 1 6 3 5 7 1 1 1 2 3 3 样例说明 题二 　魔兽地图 DotR/.IN/.OUT/.PAS/.EXE 问题描述 DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，它的规则简单于同样流行的地图DotA (Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。它们需要购买装备来提升自己的力量值。每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。 装备分为基本装备和高级装备两种，基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线图可以用一棵树来表示，如下图所示。例如，Sange and Yasha的合成需要Sange、Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe、Belt of Giant Strength和Sange Recipe Scroll合成