历届noip提高组复赛试题

1、 1 / 56NOI95 “同创杯同创杯”全国青少年信息学（计算机）奥林匹克竞赛全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）分区联赛复赛试题（高中组） （上机编程，完成时间：（上机编程，完成时间：210 分钟）分钟） 编码问题：编码问题： 设有一个数组 A:ARRAY0.N-1 OF INTEGER； 数组中存放的元素为 0N-1 之间的整数，且 AiAj（当 ij 时） 。 例如：N=6 时，有： A=（4，3，0，5，1，2） 此时，数组 A 的编码定义如下： A0的编码为 0； Ai的编码为：在 A0，A1，Ai-1中比 Ai的值小的个数（i=1，2，N-1） 上面数

2、组 A 的编码为： B=（0，0，0，3，1，2） 程序要求解决以下问题：程序要求解决以下问题：给出数组 A 后，求出其编码。给出数组 A 的编码后，求出 A 中的原数据。 灯的排列问题：灯的排列问题： 设在一排上有 N 个格子（N20） ，若在格子中放置有不同颜色的灯，每种灯的个数记为 N1，N2，Nk（k 表示不同颜色灯的个数） 。 放灯时要遵守下列规则：放灯时要遵守下列规则：同一种颜色的灯不能分开；不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B 顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB 2

3、/ 56 B-R 顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR 放置的总数为 12 种。 数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2 Q（结束标记，Q 本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。程序要求：求出一种顺序的排列方案及排列总数。 设有一个四层的积木块，14 层积木块的数量依次为：5，6，7，8 如下图所示放置：815851691423414326 其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。 计算的方法是：第三层的某个数据 A 是由第四层相邻的两个数据 B，C 经过某种计算

4、后产生的：ABC 计算所用到的计算符为：+，-，且无优先级之分（自左向右计算） ，运算符最多为2 个。 如：3+45=35 54+3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求：程序要求： 给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。 3 / 56 输入数据不存在出错的情况，同时也不会超过整数的范围。 计算时可允许出现以下情况： A=B （即可理解为运算符的个数为零） A=BB+B （即全部由 B 产生）第二届全国青少年信息学（

5、计算机）奥林匹克分区联赛复赛试题第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组（高中组 竞赛用时：竞赛用时：3 小时）小时）1比赛安排（20 分） 设有有 2 n（n=6）个球队进行单循环比赛，计划在 2 n 1 天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在 2 n 1 天内每个队都与不同的对手比赛。例如 n=2 时的比赛安排： 队 1 23 4 比赛 1=23=4 一天 1=32=4 二天 1=4 2=3 三天2数制转换（20 分） 设有一个字符串 A$的结构为： A$=mp 其中 m 为数字串（长度=20） ，而 n,p 均为 1 或 2 位的数字串（其中

6、所表达的内容在2-10 之间） 。 程序要求：从键盘上读入 A$后（不用正确性检查） ，将 A$中的数字串 m(n 进制)，以p 进制的形式输出。 例如：A$=488 其意义为：将 10 进制数 48，转换成 8 进制数输出。 输出结果为：48=604挖地雷（30 分） 在一个地图上有 N 个地窖（N=20） ，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。例如：题目要求当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径） ，当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。 输入格式： N： （表示地窖

7、的个数）V1 V 2 V3 V4 V5 4 / 56 1，W2，W3，WN （表示每个地窖中埋藏的地雷数量） A12 . A1N A23.A2N . AN-1 N 输出格式： K1-K2-.KV （挖地雷的顺序） MAX （挖地雷的数量）例如： - -其输入格式为： 输出： 51 3 -4 -510，8，4，7，6max=27 1 1 1 0 0 0 0 1 1 14砝码称重（30 分）设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重=1000） ，要求： 输入方式：a1 a2 a3 a4 a5 a6 （表示 1g 砝码有 a1 个，2g 砝码有 a2 个，20g 砝码有

8、a6 个） 输出方式：Total=N （N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0 （注：下划线表示空格） 输出：TOTAL=3 表示可以称出 1g，2g，3g 三种不同的重量。第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组（高中组 竞赛用时：竞赛用时：3 小时）小时）1在 N*N 的棋盘上（1N10） ，填入 1，2，N*N 共 N*N 个数，使得任意两个相邻的数之和为素数。 （30%） 例如：当 N=2 时，有：1243地窖之间连接路径（其中ij=1 表示

9、地窖 i,j之间是否有通路：通 Aij=1,不通 Aij=0）其相邻数的和为素数的有：1+2，1+4，4+3，2+3 5 / 56 当 N=4 时，一种可以填写的方案如下： 12111216158513491467103 在这里我们约定：左上角的格子里必须填数字 1。 程序要求： 输入：N； 输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！” 。2代数表达式的定义如下： 例如，下面的式子是合法的代数表达式： a； a+b*(a+c); a*a/(b+c) 下面的式子是不合法的代数表达式：ab; a+a*/(b+c); 程序要求： 输入：输入一个字符串，以“；”

10、结束， “；”本身不是代数表达式中字符，仅作为结束） ； 输出：若表达式正确，则输出“OK” ；若表达式不正确，则输出“ERROR” ，及错误类型。错误类型约定：1式了中出现不允许的字符；2括号不配对；3其它错误。acb字母 6 / 56 例如：输入：a+(b); 输出：OK 例如：输入：a+(b+c*a; 输出：ERROR 23骑士游历： 设有一个 n*m 的棋盘（2n50，2m50） ，如下图，在棋盘上左下角有一个中国象棋马。 （n,m） (1,1)马走的规则为：（1）马走日字；（2）马只能向右走即如下图如示： 任务 1：当 n,m 输入之后，找出一条从左下角到右上角的路径。 例如，输入：

11、n=4，m=4 输出：路径的格式：(1,1)(2,3)(4,4)。若不存在路径，则输出NO 任务 2：当 n，m 给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终点的所有路径的数目。 例如：（n=10,m=10） ， （1，5） （起点） ， （3，5） （终点） 输 出：2（即由（1，5）到（3，5）共有 2 条路径） 输入格式：n,m,x1,y1,x2,y2 (分别表示 n,m,起点坐标，终点坐标)马(4,4)(1,1)109876543211 2 3 4 5 6 7 8 9 10 7 / 56 输出格式：路径数目（若不存在从起点到终点的路径，输出 0）第四届全国青少年信息学（

12、计算机）奥林匹克分区联赛复赛试题第四届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组（高中组 竞赛用时：竞赛用时：3 小时）小时）1火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 n-1 站） ，都满足此规律。现给出的条件是：共有 N 个车站，始发站上车的人数为 a，最后一站下车的人

13、数是 m（全部下车） 。试问 x 站开出时车上的人数是多少？ 输入：a，n，m 和 x 输出：从 x 站开出时车上的人数。 20%2设有 n 个正整数（n20） ，将它们联接成一排，组成一个最大的多位整数。例如：n=3 时，3 个整数 13，312，343 联接成的最大整数为：34331213又如：n=4 时，4 个整数 7，13，4，246 联接成的最大整数为：7424613程序输入：n n 个数程序输出：联接成的多位数 40%3著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如： 40%其含义为：L+L=L，L+K=K，L+V=V，L+E=EK+

14、L=K，K+K=V，K+V=E，K+E=KL E+E=KV 根据这些规则可推导出：L=0，K=1，V=2，E=3 同时可以确定该表表示的是 4 进制加法程序输入： n（n9）表示行数。以下 n 行，每行包括 n 个字符串，每个字串间用空格隔开。 （字串仅有一个为+号，+LKVELLKVEKKVEKLVVEKLKKEEKLKK KV 8 / 56其它都由大写字母组成）程序输出： 各个字母表示什么数，格式如：L=0，K=1， 加法运算是几进制的。 若不可能组成加法表，则应输出“ERROR！”第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛

15、试题 （提（提 高高 组组 竞赛用时：竞赛用时：3 小时）小时）第一题第一题 拦截导弹拦截导弹(28(28 分分) ) 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例： INPUT OUTPUT 389 20

16、7 155 300 299 170 158 65 6（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数）第二题第二题 回文数回文数(25(25 分分) )若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个 10 进制数 56，将 56 加 65（即把 56 从右向左读） ，得到 121 是一个回文数。 又如：对于 10 进制数 87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次 N 进制的加法，上

17、例最少用了 4 步得到回文数 4884。 写一个程序，给定一个 N（2=N=10 或 N=16）进制数 M，求最少经过几步可以得到回文数。 9 / 56 如果在 30 步以内（包含 30 步）不可能得到回文数，则输出“Impossible！” 样例： INPUT OUTPUT N = 9 M= 87 STEP=6第三题第三题 旅行家的预算旅行家的预算(27(27 分分) ) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的） 。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位） 、每升汽油能行驶的距离 D2、出发点每升汽油价格 P 和沿途油站数 N（N

18、可以为零） ，油站 i 离出发点的距离Di、每升汽油价格 Pi（i=1，2，N） 。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution” 。 样例： INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号 I离出发点的距离 Di每升汽油价格 Pi1102.02.92220.02.2 OUTPUT26.95（该数据表示最小费用）第四题第四题 邮票面值设计邮票面值设计(40(40 分分) )给定一个信封，最多只允许粘贴 N 张邮票，计算在给定 K（N+K40）种邮票的情况下（假定所有的邮票数量都足够） ，如何设计邮票的面值，能得到最大值

19、 MAX，使在 1MAX之间的每一个邮资值都能得到。 例如，N=3，K=2，如果面值分别为 1 分、4 分，则在 1 分6 分之间的每一个邮资值都能得到（当然还有 8 分、9 分和 12 分） ；如果面值分别为 1 分、3 分，则在 1 分7 分之间的每一个邮资值都能得到。可以验证当 N=3，K=2 时，7 分就是可以得到的连续的邮资最大值，所以 MAX=7，面值分别为 1 分、3 分。 样例： INPUT OUTPUT N=3 K=2 1 3 MAX=7 10 / 562000 年年 题一题一 进制转换进制转换 （18 分）分） 问题描述问题描述 我们可以用这样的方式来表示一个十进制数： 将

20、每个阿拉伯数字乘以一个以该数字所处位置的（值减）为指数，以为底数的幂之和的形式。例如：可表示为 这样的形式。 与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值）为指数，以为底数的幂之和的形式。一般说来，任何一个正整数或一个负整数都可以被选来作为一个数制系统的基数。如果是以或为基数，则需要用到的数码为 ， 。例如，当时，所需用到的数码是，和，这与其是或无关。如果作为基数的数绝对值超过，则为了表示这些数码，通常使用英文字母来表示那些大于的数码。例如对进制数来说，用表示，用表示，用表示，用表示，用表示，用表示。在负进制数中是用 作为基数，例如（十进制）相当于（进制）

21、，并且它可以被表示为的幂级数的和数： （）（）（）（） （） （） 问题求解问题求解 设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数： ， ， 输输 入入 输入的每行有两个输入数据。 第一个是十进制数（3276832767） ； 第二个是负进制数的基数。 输输 出出 结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过，则参照进制的方式处理。 样样 例例 输入 11 / 56输出（）（）（）（） 提高组 题二题二 乘积最大乘积最大 （22 分）分） 问题描述问题描述 今年是国际数学联盟确定的“2000世界数学年” ，又恰逢我国著名数学家

22、华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为 N 的数字串，要求选手使用 K 个乘号将它分成 K+1 个部分，找出一种分法，使得这 K+1 个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312， 当 N=3，K=1 时会有以下两种分法：1） 3*12=362） 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。 输

23、输 入入 程序的输入共有两行： 第一行共有 2 个自然数 N，K（6N40，1K6） 第二行是一个长度为 N 的数字串。 输输 出出 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数） 。 样样 例例 12 / 56输入4 21231输出62提高组 题三题三 单词接龙单词接龙 （27 分）分） 问题描述问题描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙” （每个单词都最多在“龙”中出现两次） ，在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为

24、 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。 输输 入入 输入的第一行为一个单独的整数 n (n=20)表示单词数，以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在. 输输 出出 只需输出以此字母开头的最长的“龙”的长度 样样 例例 ： 输入5attouchcheatchoosetacta输出23 （连成的“龙”为 atoucheatactactouchoose） 13 / 56 14 / 56 提高组 题四题四 方格取数方格取数 （33 分）分） 问题描述问题描述 设有

25、 N*N 的方格图(N=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。提示：记方程 f(x)=0，若存在 2 个数 x1 和 x2，且 x1x2，f(x1)*f(x2)0，则在(x1，x2)之间一定有一个 根。样例样例输入：1 -5 -4 20输出：-2.00 2.00 5.00 题二 数的划分(20 分)问题描述问题描述将整数 n 分成 k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。输入：n，k (6n=200，2=k=6)输

26、出：一个整数，即不同的分法。样例样例输入： 7 3输出：4 四种分法为：1，1，5;1，2，4;1，3，3;2，2，3; 题三 统计单词个数(30 分)问题描述问题描述给出一个长度不超过 200 的由小写英文字母组成的字母串(约定;该字串以每行 20 个字母的方式输入，且保证每行一定为 20 个)。要求将此字母串分成 k 份(1k=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能 16 / 56再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th)。单词在给出的一个不超过 6 个单词的字典

27、中。要求输出最大的个数。输入格式输入格式去部输入数据放在文本文件 input3.dat 中，其格式如下：第一行为一个正整数(0n=5)表示有 n 组测试数据每组的第一行有二个正整数(p，k)p 表示字串的行数;k 表示分为 k 个部分。接下来的 p 行，每行均有 20 个字符。再接下来有一个正整数 s，表示字典中单词个数。(1=s=6)接下来的 s 行，每行均有一个单词。输出格式输出格式结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。样例样例输入： 11 3thisisabookyouareaoh4isaoksab输出： /说明：(不必输出)7 / this/isabookyou

28、a/reaoh 题四 Car 的旅行路线(30 分) 问题描述问题描述又到暑假了，住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第 I 个城市中高速铁路了的单位里程价格为 Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为 t。图例 17 / 56机场 高速铁路飞机航线 注意：图中并没有标出所有的铁路与航线。那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。任务任务找出一条从城市 A 到 B 的旅游

29、路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。输入文件：键盘输入文件名输 出：到屏幕(输出最小费用，小数点后保留 1 位。)输入格式输入格式第一行为一个正整数 n(0=n=10)，表示有 n 组测试数据。每组的第一行有四个正整数 s，t，A，B。S(0S=100)表示城市的个数，t 表示飞机单位里程的价格，A，B 分别为城市 A，B 的序号，(1=A，B 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10） 。输输 入入：键盘输入文件名。文件格式：N（N 堆纸牌，1 = N = 100）A1 A2 An （N 堆纸牌，每堆纸牌初始数，l

30、= Ai B1$A2$ - B2$规则的含义为：在 A中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。例如：A$abcdB$xyz变换规则为：abc-xuud-yy-yz则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：abcd-xud-xy-xyz共进行了三次变换，使得 A$ 变换为 B$。 输入输入 :键盘输人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 变换规则. . / 所有字符串长度的上限为 20。 输出输出 :输出至屏幕。格式如下：若在 10 步（包含 10 步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出N

31、O ANSWER!输入输出样例输入输出样例b.in:abcd wyzabc xuud yy yz屏幕显示：3 题三 自由落体（存盘名:NOIPG3） 问题描述问题描述 :在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，n-1。在地面上 20 / 56有一个小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d1/2*g*(t2)，其中 g=10，t 为下落时间。地面上的小车以速度 V 前进。如下图：小车与所有小球同时开始运动，当小球距小车的距离 = 0.00001 时，即认为小球被小车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个

32、小球。 输入输入 ：键盘输人：H，S1，V，L，K，n （l=H，S1，V，L，K，n =100000） 输出输出 ：屏幕输出：小车能接受到的小球个数。输入输出样例输入输出样例输入:5.0 9.0 5.0 2.5 1.8 5输出:1题四 矩形覆盖（存盘名 NOIPG4） 问题描述问题描述 :在平面上有 n 个点（n = 50），每个点用一对整数坐标表示。例如：当 n4 时，4 个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。 21 / 56这些点可以用 k 个矩形（1=k=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，

33、s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为 0。各个矩形必须完全分开（边线与顶点也都不能重合）。 输入输入 :键盘输人文件名。文件格式为n kxl y1x2 y2. .xn yn （0=xi,yi=500) 输出输出 :输出至屏幕。格式为：一个整数，即满足条件的最小的矩形面积之和。 输入输出样例输入输出样例d.in :4 21 12 23 60 7屏幕显示：42003 年 22 / 56第九第九届届全全国青国青少年信息少年信息学奥学奥

34、林匹克林匹克联赛联赛（N0IP2003N0IP2003）2003 年 11 月 29 日 提高组试题 三小时完成试题输入：苏州高斌大榕树 http:/题一题一 神经网络神经网络【问题背景】 人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。【问题描述】 在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间

35、至多有一条边相连，下图是一个神经元的例子： 神经元编号为 1） 图中，X1X3 是信息输入渠道，Y1Y2 是信息输出渠道，C1 表示神经元目前的状态，Ui 是阈值，可视为神经元的一个内在参数。 神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。兰兰规定，Ci服从公式：（其中 n 是网络中所有神经元的数目） 23 / 56 公式中的 Wji（可能为负值）表示连接 j 号神经元和 i 号神经元的边的权值。当 Ci 大于 0 时

36、，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为 Ci。 如此在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci） ，要求你的程序运算出最后网络输出层的状态。【输入格式】输入文件第一行是两个整数 n（1n20）和 p。接下来 n 行，每行两个整数，第 i1行是神经元 i 最初状态和其阈值（Ui） ，非输入层的神经元开始时状态必然为 0。再下面 P行，每行由两个整数 i，j 及一个整数 Wij，表示连接神经元 i、j 的边权值为 Wij。【输出格式】 输出文件包

37、含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！ 若输出层的神经元最后状态均为 0，则输出 NULL。【输入样例】5 61 01 00 10 10 11 3 11 4 11 5 12 3 12 4 12 5 1【输出样例】3 14 15 1题二题二 侦探推理侦探推理【问题描述】E) i , j (ijjiiUCWC 24 / 56明明同学最近迷上了侦探漫画柯南并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知

38、情的情况下） ，明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有 N 个人始终说假话，其余的人始终说真。现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！【输入格式】 输入由若干行组成，第一行有二个整数，M（1M20） 、N（1NM）和P（1P100） ；M 是参加游戏的明明的同学数，N 是其中始终说谎的人数，P 是证言的总数。接下来 M 行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写） 。往后有 P 行，每行开始是某个同学的名宇，紧跟着一个冒号和

39、一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过 250 个字符。 输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。【输出格式】 如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。【输入样例】3 1 5MIKECHARLESKATEMIKE:I am guilty.MIKE:Today is Sunday.CHARLES:MIKE is guiltyKATE:I am guilty.KATE:How are you?【输出样例】MIK

40、E 25 / 56题三题三 加分二叉树加分二叉树【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为（l,2,3,n） ，其中数字 1,2,3,n 为节点编号。每个节点都有一个分数（均为正整数） ，记第 j 个节点的分数为 di，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下： subtree 的左子树的加分 subtree 的右子树的加分subtree 的根的分数 若某个子树为主，规定其加分为 1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树 tree。

41、要求输出； （1）tree 的最高加分 （2）tree 的前序遍历【输入格式】 第 1 行：一个整数 n（n30） ，为节点个数。 第 2 行：n 个用空格隔开的整数，为每个节点的分数（分数100） 。【输出格式】 第 1 行：一个整数，为最高加分（结果不会超过 4,000,000,000） 。 第 2 行：n 个用空格隔开的整数，为该树的前序遍历。【输入样例】 5 5 7 1 2 10【输出样例】 145 3 1 2 4 5题四题四 传染病控制传染病控制 【问题背景】 近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓

42、延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。 26 / 56 【问题描述】 研究表明，这种传染病的传播具有两种很特殊的性质； 第一是它的传播途径是树型的，一个人 X 只可能被某个特定的人 Y 感染，只要 Y 不得病，或者是 XY 之间的传播途径被切断，则 X 就不会得病。 第二是，这种疾病的传播有周期性，在一个

43、疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。 这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树） 。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群） 。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序。【输入格式】

44、输入格式的第一行是两个整数 n（1n300）和 p。接下来 p 行，每一行有两个整数 i和 j，表示节点 i 和 j 间有边相连（意即，第 i 人和第 j 人之间有传播途径相连） 。其中节点1 是已经被感染的患者。【输出格式】 只有一行，输出总共被感染的人数。【输入样例】 7 6 1 2 1 3 2 4 2 5 3 6 3 7【输出样例】 32004 年第十届全国青少年信息学奥林匹克联赛复赛试题第十届全国青少年信息学奥林匹克联赛复赛试题 ( (提高组提高组 3 3 小时完成小时完成) ) http:/ 27 / 56一、津津的储蓄计划一、津津的储蓄计划 (Save.pasdprccpp) 【问

45、题描述】 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 20还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 100 元或恰好 100 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。 例如 11 月初津津手中还有 83 元，妈妈给了津津 300 元。津津预计 11 月的花销是 180 元，那么她就会在妈妈那里存 200 元，自己留下 183 元。到了 1

46、1 月月末，津津手中会剩下 3 元钱。 津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。 现在请你根据 2004 年 1 月到 12 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 2004 年年末，妈妈将津津平常存的钱加上 20还给津津之后，津津手中会有多少钱。 【输入文件】 输入文件 save.in 包括 12 行数据，每行包含一个小于 350 的非负整数，分别表示 1 月到 12 月津津的预算。 【输出文件】 输出文件

47、 save.out 包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X 表示出现这种情况的第一个月；否则输出到 2004 年年末津津手中会有多少钱。 【样例输入 1】 290230 28 / 5628020030017034050 90 80 20060 【样例输出 1】 -7 【样例输入 2】 290 230 280 200 300 170 330 50 90 80 200 60 【样例输出 2】 1580 二、合并果子二、合并果子 (fruit.pasdprccpp) 【问题描述】 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分

48、成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子 29 / 56的重量之和。可以看出，所有的果子经过 n-1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有 3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。接着，将新堆与原先

49、的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明 15 为最小的体力耗费值。 【输入文件】 输入文件 fruit.in 包括两行，第一行是一个整数 n(1n=10000)，表示果子的种类数。第二行包含 n 个整数，用空格分隔，第 i 个整数ai(1ai=20000)是第 i 种果子的数目。 【输出文件】 输出文件 fruit.out 包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 231。 【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】 对于 30的数据，保证有 n=1000： 对于 50

50、的数据，保证有 n=5000； 对于全部的数据，保证有 n=10000。 三、合唱队形三、合唱队形(chorus.pasdprccpp) 30 / 56【问题描述】 N 位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的 K位同学排成合唱队形。 合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为1，2，K，他们的身高分别为 T1，T2，TK， 则他们的身高满足T1.Ti+1TK(1=i=K)。 你的任务是，已知所有 N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】 输入文件 chorus.in 的第一行是一个整数 N(2=N=1

51、00)，表示同学的总数。第一行有 n 个整数，用空格分隔，第 i 个整数 Ti(130=Ti=230)是第 i 位同学的身高(厘米)。【输出文件】 输出文件 chorus.out 包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】8186 186 150 200 160 130 197 220【样例输出】4【数据规模】对于 50的数据，保证有 n=20；对于全部的数据，保证有 n=100。四、虫食算四、虫食算(alpha.pas/dpr/c/cpp)【问题描述】 31 / 56 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看

52、一个简单的例子： 43#9865#045 + 8468#6633 44445506978 其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是 5 和 3，第二行的数字是 5。 现在，我们对问题做两个限制： 首先，我们只考虑加法的虫食算。这里的加法是 N 进制加法，算式中三个数都有 N 位，允许有前导的 0。 其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是 N 进制的，我们就取英文字母表午的前 N 个大写字母来表示这个算式中的 0到 N-1 这 N 个不同的数字：但是这 N 个字母

53、并不一定顺序地代表 0 到 N-1)。输入数据保证 N 个字母分别至少出现一次。 BADC + CRDA DCCC 上面的算式是一个 4 进制的算式。很显然，我们只要让 ABCD 分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的 N 进制加法算式，求出 N 个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，【输入文件】 输入文件 alpha.in 包含 4 行。第一行有一个正整数 N(N=26)，后面的 3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这 3 个字符串左右两端都没有空格，从高位到低位，并且恰好有 N 位。【输出文件】 输出

54、文件 alpha.out 包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出 N 个数字，分别表示 A，B，C所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。 32 / 56【样例输入】5ABCEDBDACEEBBAA【样例输出】1 0 3 4 2【数据规模】对于 30的数据，保证有 N10；对于 50的数据，保证有 N15；对于全部的数据，保证有 N26。2005 年第十二届全国青少年信息学奥林匹克第十二届全国青少年信息学奥林匹克联赛复赛试题联赛复赛试题（NOIP2006NOIP2006 普及组）普及组）竞赛时间：竞赛时间：20062006 年年 1111 月月

55、1818 日日 下午下午 1:30-4:301:30-4:30试题名称试题名称randomrandomHappyHappycountcountsequencesequence目录目录randomrandomHappyHappycountcountsequencesequence输入文件名输入文件名random.inrandom.inhappy.inhappy.incount.incount.insequence.insequence.in输出文件名输出文件名random.outrandom.outhappy.outhappy.outcount.outcount.outsequence.outs

56、equence.out试题类型试题类型非交互式程序非交互式程序题题非交互式程序题非交互式程序题非交互式程序非交互式程序题题非交互式程序非交互式程序题题附加文件附加文件无无无无无无无无时限时限1 1 秒秒1 1 秒秒1 1 秒秒1 1 秒秒 33 / 56关于竞赛中不同语言使用限制的说明关于竞赛中不同语言使用限制的说明一关于使用一关于使用 PascalPascal 语言与编译结果的说明语言与编译结果的说明1 1对于对于 PascalPascal 语言的程序，当使用语言的程序，当使用 IDEIDE 和和 fpcfpc 编译结果不一致时，以编译结果不一致时，以 fpcfpc 的的编译结果为准。编译结

57、果为准。2 2允许使用数学库允许使用数学库(uses(uses mathmath 子句子句) )，以及，以及 ansistringansistring。但不允许使用编译开。但不允许使用编译开关（最后测试时关（最后测试时 pascalpascal 的范围检查开关默认关闭：的范围检查开关默认关闭：$R-,Q-,S-$R-,Q-,S-），也不支），也不支持与优化相关的选项。持与优化相关的选项。二关于二关于 C+C+语言中模板使用的限制说明语言中模板使用的限制说明1 1允许使用的部分允许使用的部分：标准容器中的布尔集合，迭代器，串，流。相关的头文件： 2 2禁止使用的部分禁止使用的部分：序列：vect

58、or，list，deque序列适配器：stack, queue, priority_queue关联容器：map, multimap, set, multiset拟容器：valarray 散列容器：hash_map, hash_set, hash_multimap, hash_multiset所有的标准库算法相关头文件： 34 / 56 1.明明的随机数明明的随机数（random.pas/c/cpp）【问题描述】明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉

59、，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。【输入文件】输入文件 random.in 有 2 行，第 1 行为 1 个正整数，表示所生成的随机数的个数：N第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。【输出文件】输出文件 random.out 也是 2 行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例】 10 20 40 32 67 40 20 89 300 400 15【输出样例】 8 15 2

60、0 32 40 67 89 300 400 35 / 562.开心的金明开心的金明(happy.pas/c/cpp)【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 15 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N元（可以等于 N 元）的前提下，使每件物品的价