全国试题.pdf

《全国试题.pdf》由会员分享，可在线阅读，更多相关《全国试题.pdf（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第 1 1 题题9.29.2 两数之和两数之和pair. pas【问题描述】【问题描述】我们知道从 n 个非负整数中任取两个相加共有 n*(n-1)/2 个和，现在已知这 n*(n-1)/2个和值，要求 n 个非负整数。【输入】【输入】输入文件仅有一行，包含n*(n-1)/2+1 个空格隔开的非负整数，其中第一个数表示n(2n10)，其余 n*(n-1)/2 个数表示和值，每个数不超过 100000。【输出】【输出】输出文件仅一行，按从小到大的次序依次输出一组满足要求的 n 个非负整数， 相邻两个整数之间用一个空格隔开；若问题无解则输出“Impossible” 。【样例】【样例】pair.i

2、n3 1269 1160 1663pair.out383 777 886第 2 题3.8马拉松接力赛 marathon. pas【问题描述】【问题描述】某城市冬季举办环城 25km 马拉松接力赛，每个代表队有 5 人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑 1km、最多只能跑 10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。刘老师作为学校代表队的教练，精心选择了 5 名长跑能手，进行了训练和测试，得到了这 5 名选手尽力连续跑 1km、2km、10km 的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km 所用的时间

3、最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。根据测试情况及一般运动员的情况得知，连续跑 1km 要比连续跑 2km 速度快，连续跑2km 又要比连续跑 3km 速度快也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。【输入】【输入】5 行数据，分别是 1 到 5 号队员的测试数据，每行的 10 个整数，表示某一个运动员尽力连续跑 1km、2km、10km 所用的时间。【输出】【输出】两行，第一行是最短的时间，第二行是五个数据，分别是 1 到 5 号队员各自连续跑的公里数。【样例】【样例】marath.in333 700 1200

4、1710 2240 2613 3245 3956 4778 5899300 610 960 1370 1800 2712 3834 4834 5998 7682298 612 990 1560 2109 2896 3790 4747 5996 7654289 577 890 1381 1976 2734 3876 5678 6890 9876312 633 995 1467 1845 2634 3636 4812 5999 8123第 3 题3.6 种树 trees. pas【问题描述】【问题描述】一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成 1.

5、N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码 B，E，T。这三个数表示该居民想在 B和 E 之间最少种 T 棵树。marath.out97486 5 5 4 5当然，BE，居民必须记住在指定区不能种多于区域地块数的树，所以 TE-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。写一个程序完成以下工作：* 从 trees.in 读入数据* 计算最少要种树的数量和位置* 把结果写到 trees.out【输入】【输入】第一行包含数据 N，区域的个数(0N30000)；第二行包含 H，房子的数目(0H5000)；下面的 H

6、 行描述居民们的需要：B E T，0BE30000，TE-B+1。输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格【输出】【输出】隔开。【样例】【样例】trees.in941 4 24 6 28 9 23 5 2trees.out51 4 5 8 9第第 4 4 题题 3.23.2智力大冲浪智力大冲浪riddle. pas【问题描述】【问题描述】小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 m 元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为 n 个时段(

7、n500)，它又给出了很多小游戏，每个小游戏都必须在规定期限 ti 前完成(1tin)。如果一个游戏没能在规定期限前完成，则要从奖励费 m 元中扣去一部分钱 wi，wi 为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!【输入】【输入】输入文件 riddle.in，共 4 行。第 1 行为 m，表示一开始奖励给每位参赛者的钱；第 2 行为 n，表示有 n 个小游戏；第 3 行有

8、n 个数，分别表示游戏 1 到 n 的规定完成期限；第 4 行有 n 个数，分别表示游戏 1 到 n 不能在规定期限前完成的扣款数。【输出】【输出】输出文件 riddle.out，仅 1 行。表示小伟能赢取最多的钱。【样例】【样例】riddle.in10000riddle.out995074 2 4 3 1 4 670 60 50 40 30 20 10第第 5 5 题题 3.53.5最大乘积最大乘积maxmul. pas【问题描述】【问题描述】一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+2， 4=1+3， 51+4=2+3，6=1+52+4，。现在你的任务是将指定的正整数 n

9、 分解成若干个互不相同的自然数的和， 且使这些自然数的乘积最大。【输入】【输入】只一个正整数 n，(3n10000)。【输出】【输出】第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。第二行是最大的乘积。maxmul.in10maxmul.out2 3 530【样例】【样例】第第 6 6 题题 2.112.11编码编码encode. pas【问题描述】【问题描述】编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数宇。字母表中共有 26 个字母a，b，z，这些特殊的单词长度不超过6 且字母按升序排列。把所有这样的单词放在一起，按字

10、典顺序排列，一个单词的编码就对应着它在字典中的位置。例如：a1b2z26ab27ac28你的任务就是对于所给的单词，求出它的编码。【输入】【输入】仅一行，被编码的单词。【输出】【输出】仅一行，对应的编码。如果单词不在字母表中，输出 0。【样例】【样例】encode.inabencode.out27第第 7 7 题题 2.102.10电话号码电话号码phone. pas【问题描述】【问题描述】电话机上每一个数字下面都写了若干个英文字母。分布如下：1abc2def3ghi4ikl5mn6opq7rst8uvw9xyz现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。【输入】【输入

11、】第一行为一个正整数 N 表示单词表中单词的个数(N100)；第二行为一个长度不超过 100 的数字串，表示密码；接下来的 N 行，每行一个长度不超过 20 的单词，表示单词表。【输出】【输出】仅一行，表示翻译后的原文，如果密码无法翻译，则输出“No Solutions!” ，如果密码有多种翻译方式，则输出任意一种即可。【样例】【样例】phone.inphone.outthi shs b boo k873373711664thishsthisisbabook第第 8 8 题题 2.62.6括号序列括号序列bracket. pas【问题描述】【问题描述】定义如下规则序列(字符串)：1空序列是规则

12、序列；2如果 S 是规则序列，那么(S)和S也是规则序列；3如果 A 和 B都是规则序列，那么 AB也是规则序列。例如，下面的字符串都是规则序列：()，()，()，()，()()而以下几个则不是：(，)(，()，()现在，给你一些由(，)，构成的序列，你要做的，是找出一个最短规则序列，an和序列 bl，使得给你的那个序列是你给出的规则序列的子列。 (对于序列 a1， a2， ，b2， ，bm，如果存在一组下标 1i1i2inm，使得 ajbij对一切 1jn 成立，那么 a1，a2，an就叫做 b1，b2，bm的子列。【输入】【输入】输入文件仅一行，全部由(，)，组成，没有其他字符，长度不超过

13、 100。【输出】【输出】输出文件也仅有一行，全部由(，)，组成，没有其他字符，把你找到的规则序列输出即可。 因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。【样例】【样例】bracket.in()bracket.out()()最多的嵌套层数为 1，如层数为 2 时的一种为()()第第 9 9 题题2.12.1 遍历问题遍历问题travel. pas【问题描述】【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一

14、棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：aaaa/bbbb/cccc所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】【输入】输 A 数据共两行，第一行表示该二叉树的前序遍历结果 s1，第二行表示该二叉树的后序遍历结果 s2。【输出】【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】【样例】trave1.inabcbcatrave1.out4第第 1010 题题 2.22.2 产生数产生数build. pas,【问题描述】【问题描述】给出一个整数 n(n10 )和 m 个变换规则(m20)。约定：一个数字可以变换成

15、另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。现在给出一个整数 n 和 m 个规则，要你求出对 n 的每一位数字经过任意次的变换(0 次或多次)，能产生出多少个不同的整数。【输入】【输入】共 m+2 行，第一行是一个不超过 30 位的整数 n，第 2 行是一个正整数 m，接下来的 m行是 m 个变换规则，每一规则是两个数字 x、y，中间用一个空格间隔，表示 x 可以变换成y。30【输出】【输出】仅一行，表示可以产生的不同整数的个数。【样例】【样例】build.in1 2 321 22 3build.out6第第 1111题题 6.46.4

16、“ “访问访问” ”术馆术馆gallery. pas【问题描述】【问题描述】经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer 知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。【输入】【输入】第 1 行是警察赶到的时间， 以 s 为单位。 第 2 行描述了艺术馆的结构， 是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第 2 个数是它末端的藏画数量

17、；如果第 2 个数是 0， 那么说明这条走廊分叉为两条另外的走廊。 数据按照深度优先的次序给出，请看样例。一个展室最多有 20 幅画。通过每个走廊的时间不超过 20s。艺术馆最多有100 个展室。警察赶到的时间在 10min 以内。【输出】【输出】输出偷到的画的数量。【样例】【样例】gallery.in（如图 6-6）gallery.out2607 0 8 0 3 1 14 2 10 0 12 4 6 2lignja. pas8.38.3尼克的任务尼克的任务【问题描述】【问题描述】尼克每天上班之前都连接上英特网，接收他的上司发来的邮件， 这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任

18、务由一个开始时刻与一个持续时间构成。尼克的一个工作日为 N 分钟，从第一分钟开始到第 N 分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完戍，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去完成，假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第 P 分钟开始，持续时间为 T 分钟，则该任务将在第 P+T-1 分钟结束。写一个程序计算尼克应该如何选取任务，才能获得最大的空暇时间。【输入】【输入】输入数据第一行含两个用空格隔开的整数 N 和 K(1N10000，1K10000)，N 表示尼克的工作时

19、间，单位为分钟，K 表示任务总数。接下来共有 K 行，每一行有两个用空格隔开的整数 P 和 T，表示该任务从第 P 分钟开始，持续时间为 T 分钟，其中 1PN，1P+T-1N。【输出】【输出】输出文件仅一行，包含一个整数，表示尼克可能获得的最大空暇时间。lignja.in15 61 21 64 118 58 111 5lignja.out4【样例】【样例】8.18.1字串距离字串距离blast. pas【问题描述】【问题描述】设有字符串 X，我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串，如字符串 X 为”abcbcd” ，则字符串“abcbcd” ， “abcb

20、cd”和“abcbcd”都是 X 的扩展串，这里“”代表空格字符。如果 A1 是字符串 A 的扩展串，B1是字符串 B的扩展串，A1 与 B1具有相同的长度，那么我扪定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值 K，空格字符与空格字符的距离为 0。在字符串 A、B的所有扩展串中，必定存在两个等长的扩展串 A1、B1，使得 A1 与 B1之间的距离达到最小，我们将这一距离定义为字符串 A、B的距离。请你写一个程序，求出字符串 A、B的距离。【输入】【输入】输入文件第一

21、行为字符串 A，第二行为字符串 B。A、B均由小写字母组成且长度均不超过 2000。第三行为一个整数 K（1K100） ，表示空格与其他字符的距离。【输出】【输出】输出文件仅一行包含一个整数，表示所求得字符串 A、B的距离。【样例】【样例】blast.incmcsnmn2blast.out108.78.7三角形牧场三角形牧场pasture. pas【问题描述】【问题描述】和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 N(3N40)块木板，每块的长度 Li(1Li40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大

22、。请帮助 Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。【输入】【输入】第 1 行：一个整数 N第 2.N+1 行：每行包含一个整数，即是木板长度。仅一个整数：最大牧场面积乘以 100 然后舍尾的结果。如果无法构建，输出-1。pasture.out692【输出】【输出】【样例】【样例】pasture.in5113348.88.8分组分组teams. pas,【问题描述】【问题描述】你的任务是把一些人分成两组，使得：每个人都被分到其中一组；每个组都至少有一个人；一组中的每个人都认识其他同组成员；两组的成员人数尽量接近。这个问题可能有多个解决方案，你只要输出任意一个即可，或者输出这样的分组

23、法不存在。【输入】【输入】为了简单起见，所有的人都用一个整数标记，每个人号码不同，从 1 到 N。输入文件的第一行包括一个整数 N（2N100） ，N 就是需要分组的总人数；接下来的 N 行对应了这 N 个人，按每个人号码的升序排列，每一行给出了一串号码 Aij（1AijN，Aiji） ，代表了第 i 个人所认识的人的号码，号码之间用空格隔开，并以一个“0”结束。【输出】【输出】如果分组方法不存在，就输出信息“No solution” （输出时无需加引号）至输出文件；否则用两行输出分组方案；第一行先输出第一组的人数，然后给出第一组成员的号码，每个号码前有一个空格，同理给出第二组的信息。每组的成

24、员号码顺序和组别顺序并不重要。【样例】【样例】teams.in52 3 5 0teams.out3 1 3 52 2 41 4 5 3 01 2 5 01 2 3 04 3 2 1 08.58.5多米诺骨多米诺骨dom. pas【问题描述】【问题描述】多米诺骨牌有上下 2 个方块组成， 每个方块中有 16 个点。 现有排成行的 n 个多米诺骨牌如图 8-1 所示。1上方块中点数之和记为，下方块中点数之和记为2，它们的差为12。例如在图 8-1 中，1=6+1+1+1=9，2=1+5+3+2=11，12=2。每个多米诺骨牌可以旋转 180，使得上下两个方块互换位置。编程用最少的旋转次数使多米诺骨

25、牌上下 2 行点数之差达到最小。对于图 8-1 中的例子，只要将最后一个多米诺骨牌旋转180，可使上下2 行点数之差为 0。【输入】【输入】输入文件的第一行是一个正整数 n(1n1000)，表示多米诺骨牌数。接下来的n 行表示 n 个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数 a 和 b，且 1a，b6。【输出】【输出】输出文件仅一行，包含一个整数。表示求得的最小旋转次数。【样例】【样例】dom.in46 11 51 31 2dom.out16.36.3 信号放大器信号放大器booster. pas【问题描述】【问题描述】树型网络是最节省材料的网络。所谓树型

26、网络，是指一个无环的连通网络，网络中任意两个结点间有且仅有一条通信道路。网络中有一个结点是服务器，负责将信号直接或间接地发送到各终端机。如图6-4，server 结点发出一个信号给结点 a 和 c，a 再转发给 b。如此，整个网络都收到这个信号了。serverab但是，实际操作中，信号从一个结点发到另一个结点，会出现信号强度的衰减。衰减量server3a2b1如上图， 边上所标的数字为边的衰减量。 假设从 server 出发一个强度为 4 个单位的信号，一般由线路长度决定。发到结点 a 后强度衰减为 4-3=1 个单位。结点 a 再将其转发给结点 b。由于信号强度为 1，衰减量为 2，因此信号

27、无法发送到 b。一个解决这一问题的方法是，安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度（从服务器出发时的强度） 。上图中，若在结点 a 处安装一个信号放大器，则强度为 4 的信号发到 a 处，即被放大至4。这样，信号就可以被发送的网络中的任意一个节点了。为了简化问题，我们假定每个结点只处理一次信号，当它第二次收到某个信号时，就忽略此信号。你的任务是根据给出的树型网络，计算出最少需要安装的信号放大器数量。【输入】【输入】第一行一个整数 n，表示网络中结点的数量。 （n=100000）第 2n+1 行，每行描述一个节点的连接关系。其中第i+1 行，描述的是结点 i 的连接关系

28、：首先一个整数 k，表示与结点 i 相连的结点的数量。此后 2k 个数，每两个描述一个与结点 i 相连的结点，分别表示结点的编号（编号在 1n 之间）和该结点与结点 i 之间的边的信号衰减量。结点 1 表示服务器。最后一行，一个整数，表示从服务器上出发信号的强度。【输出】【输出】一个整数，表示要使信号能够传遍整个网络，需要安装的最少的信号放大器数量。如果不论如何安装信号放大器，都无法使信号传遍整个网络，则输出“No solution.”【样例】【样例】booster.inbooster.out412 2 3 3 12 1 3 4 21 1 11 2 246.56.5 聚会的快乐聚会的快乐par

29、ty. pas【问题描述】【问题描述】你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。 但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定 N 个人(姓名，他幽默的系数，以及他上司的名字)，编程找到能使幽默系数和最大的若干个人。【输入】【输入】第一行一个整数 N(N100)。接下来有 N 行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过 20 的字符串，幽默系数是在 0 到 100 之间的整数。【输出】【输出】所邀请的人最大的幽默系数和。【样例】【样例】party.in5BART 1 HOMERHOMER 2 MONTGOMERYM

30、ONTGOMERY 1 NOBODYLISA 3 HOMERSMITHERS 4 MONTGOMERYparty.out86.26.2 树的重量树的重量weight. pas【问题描述】【问题描述】树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树，其叶节点表示一个物种，两个叶节点之间的距离表示两个物种的差异。现在，一个重要的问题是，根据物种之间的距离，重构相应的“进化树” 。令 N=1.n，用一个 N 上的矩阵 M 来定义树 T。其中，矩阵 M 满足：对于任意的 i，j，k，有 Mi,j+Mj,k=Mi,k。树 T 满足：1叶节点属于集合 N；2边权均为非负整数；3dT(i,j

31、)=Mi,j，其中 dT(i,j)表示树上 i 到 j 的最短路径长度。如下图，矩阵 M 描述了一棵树。 059128508117M 98051121150487140树的重量是指树上所有边权之和。对于任意给出的合法矩阵 M，它所能表示树的重量是惟一确定的，不可能找到两棵不同重量的树，它们都符合矩阵 M。你的任务就是，根据给出的矩阵 M，计算 M 所表示树的重量。下图是上面给出的矩阵 M 所能表示的一棵树，这棵树的总重量为 15。【输入】【输入】输入数据包含若干组数据。每组数据的第一行是一个整数 n(2n30)。其后 n-l 行，给出的是矩阵 M 的一个上三角(不包含对角线)，矩阵中所有元素是不超过 100 的非负整数。输入数据保证合法。输入数据以 n=0 结尾。【输出】【输出】对于每组输入，输出一行，一个整数，表示树的重量。【样例】【样例】weight.in55 9 12 88 11 75 14415 36 6031 55360weight.out1571