信息学奥赛2003吉林省选试题.doc

6 2003吉林省选试题 试题说明试题名称分值可执行文件输入文件输出文件限时字符串变换90String.exeString.inString.out15s穿 墙 人60wall.exeWall.inWall.out3s 选陪审团90Jury.exeJury.inJury.out3s方格中置160Grid.exeGrid.inGrid.out3s第一试共四道题，满分为300分。竞赛时间：2003年7月6 日8:3012:00题一 字符串变换【问题描述】为了简化问题，我们只考虑仅由字符a和b组成的字符串。且只有两个变换规则：n 规则1：a Pa , 表示字符a可以变换为字符串Pa；n 规则2：b Pb , 表示字符b可以变换为字符串Pb；对字符串中的某个字符应用一次规则将其替换成Pa或Pb的过程，称为一次变换。现在的问题是，给定一个初始串S和目标串T，给定两个变换规则中的Pa和Pb，问是否存在一个从初始串到目标串的变换序列，并且该序列的变换次数不超过m。例如：m = 4Pa = aaPb = bbS = abT = aaabb则存在一个变换次数不超过4次的变换序列，如下所示：ab aab aaab aaabb注意：上述序列只经过了3次变换。每次变换可以根据规则替换掉当前串中的任意一个字符，但一次变换只能替换一个字符。【输入格式】String.in输入文件的第一行为一个整数m，其中1 m 30，表示最多允许的变换次数。接下来有4行，分别是Pa, Pb, S, T，其中S不等于T。每个字符串仅由字符a和b组成，不包含空格，且所有字符串的长度都不超过30。【输出格式】String.out如果不存在从S到T且变换次数小于等于m的变换序列，则输出一个字符串”NO”（注意要大写，不包含引号）；否则输出最短的变换序列的变换次数。【输入样例1】4aabbabaaabb【输出样例1】3【输入样例2】4ababaaabb【输出样例2】NO 题二 穿墙人【问题描述】穿墙术是现代魔术表演中常见的一个节目。魔术中的穿墙人可以穿过预先设计好的若干道墙。所有的墙被安置在一个网格区域中，如图所示，？表示墙所占据的网格，所有的墙都水平放置，宽度为1个单位，但长度可能不同。任何两道墙不会相互重叠，即任何一个？不能同时属于两道或两道以上的墙。穿墙人的能量有限，每次表演至多只能穿过k道墙。表演开始时，主持人让观众任选网格的某一列，然后穿墙人开始沿着此列从网格的上端穿过中间的每一道墙到达网格的底部。但如果观众所选择的那一列中有大于k道墙，则穿墙人的表演会失败。012345678012345678例图所示，如果k=3，则穿墙人可以自上而下地穿过除第6列外的任何列，因为只有第6列需要穿越4道墙，但穿墙人在同一列上最多只能穿过3道墙。当所有的墙给出之后，如果知道穿墙人当前的能量K，我们希望移去最少数目的墙，才能使得穿墙人能够穿越任何一列。对于图中的例子，如果k=3，穿墙人无法穿越第6列，但是只要把第3行的墙移去（不唯一），则穿墙人就可以穿过任意一列。因此对于这个例子最少需要移去1道墙。【输入格式】wall.in输入文件的第一行是用空格隔开的两个整数n和k，其中1 n 100，0 k 100；n表示墙的数目，k表示穿墙人在同一列上最多能穿过多少道墙。接下来有n行，每行是用空格隔开的四个整数x1, y1, x2, y2，其中(x1, y1)和(x2, y2)分别表示一道墙的两个端点（注意，根据题意，一定有y1=y2）。x, y坐标的范围为0, 100，左上角的坐标定为(0, 0)。【输出格式】wall.out输出文件只包含一个整数，即为了让穿墙人能够穿越任意一列所需要移去的最少的墙的数目。【输入样例】 7 3 0 0 3 0 6 1 8 1 2 3 6 3 4 4 6 4 0 5 1 5 5 6 7 6 1 7 3 7【输出样例】 1题三 选陪审团【问题描述】在古埃及时代也有法庭。法庭的裁决取决于陪审团的决定，陪审团的人员来自当地的居民。每次开庭前，法庭会聘请n人作为侯选陪审员，其编号分别为1，2，n；然后由法官从n位侯选陪审员中选出m人作为正式陪审员。具体的选择过程如下：由原告和被告分别给每一位候选陪审员打分，分值范围为0, 20，0分表示完全不喜欢，20分表示此人非常适合做陪审员。法官将根据原告和被告双方对每一位侯选陪审员打出的分数来选择m人作为正式的陪审员。为了保证公平审判，原告被告双方对最终陪审团的喜好程度应该尽量平衡。具体而言，给定n个侯选陪审员以后，选出m个人组成陪审团的原则是：原告方和被告方对这m个人的所打的分数之和应该尽量接近（两个数“尽量接近”表示他们的差的绝对值尽量小）；若存在多个方案，则应该选择其中一个方案，使原告和被告方对这m个人所打的分数的总和最大。例如：n = 4, m = 2原告方打分： 5 11 7 9被告方打分： 9 11 8 14此时最佳方案是选择第和第号侯选人，这是因为这个方案中原告对打分之和为11718，被告对打分之和为11819，两者之差的绝对值为1，这是所有方案中最小的。再比如：n = 4, m = 2原告方打分： 10 1 1 2被告方打分： 1 2 10 1 如果选择，则原告对的打分和 = 10 + 1 = 11被告对的打分和 = 1 + 10 = 11原告和被告对的打分和的差的绝对值 = |11-11| = 0原告和被告对的打分和的总和 = 11 + 11 = 22如果选择，则原告对的打分和 = 1 + 2 = 3被告对的打分和 = 2 + 1 = 3原告和被告对的打分和的差的绝对值 = |3-3| = 0原告和被告对的打分和的总和 = 3 + 3 = 6 虽然这两种方案中原告和被告打分和同样地接近，但是选择可使原告和被告打分和的总和达到最大，所以最佳方案应该选择。【输入格式】Jury.in输入文件的第一行是两个被空格隔开的整数n和m，其中n为侯选人的数目，1 n 200；m为需要选择的陪审员的数目，1 m 20且m n。接下来有n行，每行包含两个用空格隔开的整数，分别表示原告和被告对某个侯选人所打的分，分值在0到20之间（包含0和20）。【输出格式】Jury.out输出文件只有一行，包含两个用空格隔开的整数，第一个数表示原告和被告对所选择的m个人打分和的差的绝对值，第二个数表示原告和被告对所选择的m个人的打分总和。样例第一组样例【输入样例】4 25 911 117 89 11【输出样例】1 37第二组样例【输入样例】4 210 11 21 102 1【输出样例】0 22题四 方格置1【问题描述】在一个nn的网格中填满了数字0或1。相邻的1可以组成一块连通的区域，我们将该区域中1的数目称为该区域的面积。两个格子相邻是指他们有一条公共边，仅有公共顶点并不算相邻。例如下图是一个88的网格，图中有三块区域，其中第一块区域在左上角，面积为7；第二块区域在左下角，面积为8；第三块区域在右边，面积为10。11111010000100100001001000000011把这个格子变为110000001100000111000011011111000问题一：统计出有多少区域，最大区域面积多大；问题二：如果允许将方格中的某个数字从0变为1，则变化一个格子以后所能得到的最大区域面积多大？（具体变换哪个格子需要由你的程序来选择，你的选择必须使得变换过后得到的网格中的最大区域面积最大）【输入格式】Grid.in输入文件第一行包含一个整数n，其中1 n 30。接下来n行每行有n个数字，每个数字是0或1，两个数字之间用一个空格隔开。【输出格式】Grid.out输出文件只有一行，包含三个用空格隔开的整数，分别表示原来的网格中区域的数目和最大区域的