省选福建noi2002选拔赛试卷.pdfVIP

NOI’2002 福建省选手选拔赛试卷 考生须知 *若试卷中试题字迹不清，考生可以在审题时举手请求解释，由考务 加以说明。涉 及题意理解问题，则不得提问且考务 不予解答。 *考生上机编程时应在指定目录下工作，并请每隔5 分钟存盘一次。发生机器故障时由 考务 确认补给修复时间，且最长不超过 10 分钟。 *对考生答题测试有严格时间限制，若超时则该测试 为0 分。考生应注意优化算法。 *考生应严格遵守考场规则，不得 。 * 时间为8 时30 分至12 时，计210 分钟（其中30 分钟为审题时间）。 试卷满分为100 分 试题一、蚯蚓的 问题 (30 分) 问题描述： 在一块田地上，一群蚯蚓在做收集食物 。蚯蚓们把梯形田地上的食物堆积整理如下： a(1,1) a(1,2) … a(1,m) a(2,1) a(2,2) a(2,3) …a(2,m) a(2,m+1) a(3,1) a(3,2) a(3,3) … a(3,m+1) a(3,m+2) a(n,1) a(n,2) a(n,3) … a(n,m+n-1) 它们把食物分成n 行，第1 行有m 堆食物，每堆的食物量分别是a(1,1),a(1,2), …,a(1,m); 第2 行有m+1 堆食物，每堆的食物量分别是a(2,1),a(2,2),…,a(2,m+1); 以下依次有m+2 堆、 m+3 堆、… 、m+n- 1 堆食物。 现在蚯蚓们选择了 k 条蚯蚓来测试它们的合作能力 1 2 5 0 2 1 10 0 6 试题二、最小交换合并问题(30 分) 问题描述： 在操场上沿一直线排列着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选 相邻的两堆石子合并成新的一堆，并将新的一堆石子数计为该次合并的得分，允许在第一次 合并前对调一次相邻两堆石子的次序。 编程任务：计算在上述条件下，将n 堆石子合并成一堆的最小累计得分和初次交换的位置。 数据输入：输入数据由文件名为INPUT2.*的文本文件提供。 其中，第1 行是石子的堆数n≤100； 第2 行是顺序排列的各堆石子数（≤20 ），每两个数之间用空格分隔。 结果输出: 在屏幕上输出合并的最小得分和初次交换的位置(k,k+1) 。如果没有进行对调， 则初次交换的位置输出为（0 ，1）。 输入示例 输出文件示例 INPUT2.001 3 最小得分=11 2 5 1 交换的位置：（1，2 ）或（2 ， 3 ） 试题三、DNA 序列 问题 （本题满分40 分）