《选拔题目第二试.doc》由会员分享，可在线阅读，更多相关《选拔题目第二试.doc（9页珍藏版）》请在金锄头文库上搜索。
1、6命题：江苏省青少年信息学奥赛委科学委员会 JSOI2008江苏省代表队组队第三轮选拔赛 本次竞赛共分两试，本试卷为第二试 第二试试题 竞赛时间：2008年4 月 28 日7:3012:30n 试题说明试题名称分值源文件输入文件输出文件限时星球大战85starwarstarwar.instarwar.out3s魔兽地图100DotRDotR.inDotR.out2s 巨额奖金115AwardAward.inAward.out1sl 分数分布 第一试共三道题，满分为300 分。l 文件命名选手提交源程序，名字见每题标题，并最终拷贝到指定硬盘的相应目录。源文件的名字应与编译后的可执行程序同名。选手
2、程序应从 .IN中读入输入数据，不需要进行判错处理。执行结果存放到 .OUT中。输入输出文件均不需指定目录。l 程序运行要求评测时采用黑盒测试。每题均为十个测试点。对每个测试点有一定的时间限制和分数。选手程序必须在此时限内运行结束并输出正确的结果才能得到这个点的分数。程序运行时仅对指定的文件读写，不应在屏幕上显示任何信息或者等待键盘输入。文件各行所有数据均用一个空格隔开。输出结果应按题面要求，不应有多余的字符。题一 星球大战StarWar/.IN/.OUT/.PAS/.EXE 问题描述很久以前，在一个遥远的银河系对反抗军来说，这是一个黑暗的时刻。虽然帝国军的终极武器“死亡星球”已经被摧毁，帝国
3、的军队仍然把反抗军从隐藏的军事基地中赶出，并在整个银河系展开追逐。 A long time ago in a galaxy far, far away It is a dark time for the Rebellion. Although the Death Star has been destroyed, Imperial troops have driven the Rebel forces from their hidden base and pursued them across the galaxy. 摘自Star Wars Episode V, The Empire Strik
4、es Back考虑到邪恶的帝国完全有能力在短时间内制造出“死亡星球”的替代品，为了避免被一次全部歼灭，反抗军的指挥官决定把部队分散在很多星球上。可是，这样会带来通讯上的问题。某些星球之间可以通过“以太”隧道直接通讯，而没有隧道相连的星球之间的通讯就需要其他星球帮忙转发。因此，只有两个星球之间存在一条由“以太”隧道拼接成的路径，它们才可以正常通讯。银河历2008年4月1日凌晨，反抗军最担心的事情还是发生了。反抗军司令部收到间谍的秘密通知：帝国军成功制造出第二代“死亡星球”，并将依次摧毁如下星球（星球列表略）。指挥官希望迅速计算出每次攻击之后通讯网络的连通情况，即反叛军所占据的星球被分成了多少个连
5、通支，从而帮助决定在何时发动反击。输入输入文件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行，每行一个整数。第一个整数表示开始时通讯网络的连
6、通支个数。接下来的第I (1 I K)个整数，表示在攻击列表上的第I个星球被摧毁后，通讯网络的连通支个数。样例starwar.instarwar.out8 130 11 66 55 00 61 22 33 44 57 17 27 63 6516357111233样例说明20513674 题二 魔兽地图 DotR/.IN/.OUT/.PAS/.EXE 问题描述DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，它的规则简单于同样流行的地图DotA (Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性力
7、量。它们需要购买装备来提升自己的力量值。每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种，基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线图可以用一棵树来表示，如下图所示。例如，Sange and Yasha的合成需要Sange、Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe、Belt of Giant Strength和Sange Recipe Scroll合成。
8、Sange and YashaSangeYashaaaOgre AxeBelt of Giant StrengthSange and Yasha Recipe ScrollSange Recipe ScrollYasha Recipe ScrollBlade of AlacrityBoots of Elvenskin每件基本装备都有数量限制，这限制了你不能无限制地合成某些性价比很高的装备。现在，英雄Spectre有 M个金币，它想用这些钱购买装备使自己的力量值尽量高。你能帮帮它吗？它会教你魔法Haunt（幽灵附体）作为回报的。输入输入文件dotr.in的第一行包含两个整数N (1 N 51)和
9、M (0 M 2,000)。分别表示装备的种类数和金币数。装备用1到N的整数编号。接下来的N行，按照从装备1到装备N的顺序，每行描述一种装备。每一行的第一个正整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高级装备，后面紧跟2C个数，表示合成这种装备需要C种低级的装备。第2I 1个数表示这个合成方案中第I种装备的编号，第2I个数表示该装备所需的个数。输出请将输出写入dotr.out。输出文件的第一行包含一个整数S，表示最多可以提升多
10、少点力量值。接下来的N行，每行一个整数，描述你提供的方案。第I行的整数表示你提供的方案中编号为I的装备的购买数目。输入数据保证正确的S不会超过231 1。如果有多种方案都能获得最大的力量值，输出任意一种即可。对于每个测试点，你的答案必须完全正确才能得分。样例dotr.indotr.out10 595 A 3 6 1 9 2 10 11 B 5 31 B 4 31 B 2 38 A 3 2 1 3 1 7 11 B 5 35 B 3 315 A 3 1 1 5 1 4 11 B 3 51 B 4 3330002200100样例说明装备合成图和问题描述中的图相似。注意装备1的合成需要两个装备9。1
11、2345678910*2 题三 巨额奖金Award/.IN/.OUT/.PAS/.EXE 问题描述NJ市的快速发展得益于其便捷的交通。可是，随着经济的发展，大量的人进入NJ市，NJ市的交通也承受着巨大的压力。现在，NJ市正在筹划建设一个新型的交通枢纽，从而减轻交通的压力。NJ市包含n个区，有些区之间有双向的干道存在。新型交通枢纽建设在这些干道的基础上，将其中的部分干道改进为新型干道。改进后，干道能承受的压力可以比原来增加几十倍。为了和谐发展，在新型的交通枢纽建成后，要求任何两个区之间都可以只通过新型干道（直接或间接地）连接。政府已经预测出每条干道改进为新型干道的费用。政府希望建设新型交通枢纽的
12、总费用最小，并以巨额奖金向市民征集方案。政府很快发现费用最小的方案不一定唯一，所以决定将奖金平分给每一种方案的第一个设计者，即如果一个人设计的费用是最小的而且前面没人和他设计出一模一样的方案，则他可获奖。Js08被奖金深深的吸引，准备设计一种方案。可是，他发现方案可能会很多，如果最后获奖者太多，巨额的资金分到每个人头上的也不会太多。所以他决定先算一下可行的方案数是多少。输入输入的第一行包含两个数n (1 n 100)，m (1 m 1,000)，分别表示该市有多少个区和有多少条干道。接下来m行，每行三个数ai、bi、ci (1 ai, bi n, 1 ci 1,000,000,000)，表示ai区和bi区之间有一条干道，如果改进需要ci的费用。输入保证任何两个区之间至多有一条干道。对于任何一个费用c，不会有超过10条干道的费用都是c。输出输出费用最小的方案有多少种。由于答案可能很大，你只要输出方案数除以31011的模即可。样例award.inaward.out4 61 2 11 3 11 4 12 3 22 4 13 4 18 不经许可不得使用 JSOI2008江苏省代表队组队选拔赛试题 常州 2008/二试
