pascal复赛试题合订本.doc

全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 1 页 共 51 页 第一届全国青少年信息学奥林匹克分区联赛复赛试题第一届全国青少年信息学奥林匹克分区联赛复赛试题 19951995 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 一 编码问题 编码问题 设有一个数组 A ARRAY 0 N 1 OF INTEGER 数组中存放的元素为 0 N 1 之间的整数 且 A i A j 当 i j 时 例如 N 6 时 有 A 4 3 0 5 1 2 此时 数组 A 的编码定义如下 A 0 的编码为 0 A i 的编码为 在 A 0 A 1 A i 1 中比 A i 的值小的个数 i 1 2 N 1 上面数组 A 的编码为 B 0 0 0 3 1 2 程序要求解决以下问题 程序要求解决以下问题 给出数组 A 后 求出其编码 给出数组 A 的编码后 求出 A 中的原数据 二 灯的排列问题 二 灯的排列问题 设在一排上有 N 个格子 N 20 若在格子中放置有不同颜色的灯 每种灯的个数记为 N1 N2 Nk k 表示不同颜色灯的个数 放灯时要遵守下列规则 放灯时要遵守下列规则 同一种颜色的灯不能分开 不同颜色的灯之间至少要有一个空位置 例如 N 8 格子数 R 2 红灯数 B 3 蓝灯数 放置的方法有 R B 顺序 RRBBB RRBBB RRBBB RRBBB RRBBB RRBBB B R 顺序 BBBRR BBBRR BBBRR BBBRR BBBRR BBBRR 放置的总数为 12 种 数据输入的方式为 N P1 颜色 为一个字母 N1 灯的数量 P2 N2 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 2 页 共 51 页 Q 结束标记 Q 本身不是灯的颜色 程序要求 求出一种顺序的排列方案及排列总数 程序要求 求出一种顺序的排列方案及排列总数 三 积木问题三 积木问题 设有一个四层的积木块 1 4 层积木块的数量依次为 5 6 7 8 如下图所示放置 8158516914 23414326 其中 给出第三层与第四层所标示的数字 并已知第三层的数据是由第四层的数据计算 出来的 计算的方法是 第三层的某个数据 A 是由第四层相邻的两个数据 B C 经过某种计 算后产生的 A BC 计算所用到的计算符为 且无优先级之分 自左向右计算 运算符最多为 2 个 如 3 4 5 35 5 4 3 23 可以看出 上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的 A B C B 也就是 8 2 3 2 15 3 4 3 14 2 6 2 程序要求 程序要求 给出第四层与第三层的数据后 将第一 二层的每块积木标上相应的数据 并输出整个 完整的积木图及计算公式 输入数据不存在出错的情况 同时也不会超过整数的范围 计算时可允许出现以下情况 A B 即可理解为运算符的个数为零 A B B B 即全部由 B 产生 第二届全国青少年信息学奥林匹克分区联赛复赛试题第二届全国青少年信息学奥林匹克分区联赛复赛试题 19961996 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 比赛安排 一 比赛安排 2020 分 分 设有有 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 三天 二 数制转换 20 分 设有一个字符串 A 的结构为 A mp 其中 m 为数字串 长度 20 而 n p 均为 1 或 2 位的数字串 其中所表达的内容在 2 10 之间 程序要求 从键盘上读入 A 后 不用正确性检查 将 A 中的数字串 m n 进制 以 p 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 3 页 共 51 页 进制的形式输出 例如 A 488 其意义为 将 10 进制数 48 转换成 8 进制数输出 输出结果为 48 60 三 挖地雷 三 挖地雷 3030 分 分 在一个地图上有 N 个地窖 N 20 每个地窖中埋有一定数量的地雷 同时 给出地窖 之间的连接路径 例如 题目要求 当地窖及其连接的数据 给出之后 某人可以从任 一处开始挖地雷 然后可 以沿着指出的连接往下挖 仅能选择一条路径 当 无连接时挖地雷工作结束 设计一个挖地雷的方案 使某人能挖到最多的地雷 输入格式 N 表示地窖的个数 1 W2 W3 WN 表示每个地窖中埋藏的地雷数量 A12 A1N A23 A2N AN 1 N 输出格式 K1 K2 KV 挖地雷的顺序 MAX 挖地雷的数量 例如 其输入格式为 输出 51 3 4 5 10 8 4 7 6max 27 1 1 1 0 0 0 0 1 1 1 四 砝码称重 四 砝码称重 3030 分 分 设有 1g 2g 3g 5g 10g 20g 的砝码各若干枚 其总重 1000 要求 输入方式 a1 a2 a3 a4 a5 a6 表示 1g 砝码有 a1 个 2g 砝码有 a2 个 20g 砝码有 a6 个 输出方式 Total N N 表示用这些砝码能称出的不同重量的个数 但不包括一个砝码也不用 的情况 如输入 1 1 0 0 0 0 注 下划线表示空格 输出 TOTAL 3 表示可以称出 1g 2g 3g 三种不同的重量 V1 V 2 V3 V4 V5 地窖之间连接路径 其中 ij 1 表示地窖 i j 之间是否有通路 通 Aij 1 不通 Aij 0 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 4 页 共 51 页 第三届全国青少年信息学奥林匹克分区联赛复赛试题第三届全国青少年信息学奥林匹克分区联赛复赛试题 19971997 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 在 N N 的棋盘上 1 N 10 填入 1 2 N N 共 N N 个数 使得任意两个相邻的 数之和为素数 30 例如 当 N 2 时 有 12 43 当 N 4 时 一种可以填写的方案如下 121112 161585 134914 67103 在这里我们约定 左上角的格子里必须填数字 1 程序要求 输入 N 输出 如有多种解 则输出第一行 第一列之和为最小的排列方案 若无解 则输 出 NO 二 代数表达式的定义二 代数表达式的定义如下 例如 下面的式子是合法的代数表达式 a a b a c a a b c 下面的式子是不合法的代数表达式 ab a a b c 程序要求 输入 输入一个字符串 以 结束 本身不是代数表达式中字符 仅作 为结束 输出 若表达式正确 则输出 OK 若表达式不正确 则输出 ERROR 及错误 其相邻数的和为素数的有 1 2 1 4 4 3 2 3 a c b 字母 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 5 页 共 51 页 类型 错误类型约定 1 式了中出现不允许的字符 2 括号不配对 3 其它错误 例如 输入 a b 输出 OK 例如 输入 a b c a 输出 ERROR 2 三 骑士游历 三 骑士游历 设有一个 n m 的棋盘 2 n 50 2 m 50 如下图 在棋盘上左下角有一个中国象 棋马 n m 1 1 马走的规则为 1 马走日字 2 马只能向右走 即如下图如示 任务 1 当 n m 输入之后 找出一条从左下角到右上角的路径 例如 输入 n 4 m 4 输出 路径的格式 1 1 2 3 4 4 若不存在路径 则输出 NO 任务 2 当 n m 给出之后 同时给出马起点的位置和终点的位置 试找出从起点到终 点的所有路径的数目 例如 n 10 m 10 1 5 起点 3 5 终点 马 4 4 1 1 10 9 8 7 6 5 4 3 2 1 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 6 页 共 51 页 输 出 2 即由 1 5 到 3 5 共有 2 条路径 输入格式 n m x1 y1 x2 y2 分别表示 n m 起点坐标 终点坐标 输出格式 路径数目 若不存在从起点到终点的路径 输出 0 第四届全国青少年信息学奥林匹克分区联赛复赛试题第四届全国青少年信息学奥林匹克分区联赛复赛试题 19981998 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 一 火车从始发站 称为第 1 站 开出 在始发站上车的人数为 a 然后到达第 2 站 在第 2 站有人上 下车 但上 下车的人数相同 因此在第 2 站开出时 即在到达第 3 站之前 车上的人数保持为 a 人 从第 3 站起 包括第 3 站 上 下车的人数有一定规律 上车 的人数都是前两站上车人数之和 而下车人数等于上一站上车人数 一直到终点站的前 一站 第 n 1 站 都满足此规律 现给出的条件是 共有 N 个车站 始发站上车的人数 为 a 最后一站下车的人数是 m 全部下车 试问 x 站开出时车上的人数是多少 输入 a n m 和 x 输出 从 x 站开出时车上的人数 20 二 二 设有 n 个正整数 n 20 将它们联接成一排 组成一个最大的多位整数 例如 n 3 时 3 个整数 13 312 343 联接成的最大整数为 34331213 又如 n 4 时 4 个整数 7 13 4 246 联接成的最大整数为 7424613 程序输入 n n 个数 程序输出 联接成的多位数 40 三 三 著名科学家卢斯为了检查学生对进位制的理解 他给出了如下的一张加法表 表中的字 母代表数字 例如 40 其含义为 L L L L K K L V V L E E K L K K K V K V E K E KL E E KV 根据这些规则可推导出 L 0 K 1 V 2 E 3 同时可以确定该表表示的是 4 进制加法 程序输入 n n 9 表示行数 以下 n 行 每行包括 n 个字符串 每个字串间用空格隔开 字串仅有一个为 号 其它都由大写字母组成 程序输出 各个字母表示什么数 格式如 L 0 K 1 加法运算是几进制的 1 2 3 4 5 6 7 8 9 10 LKVE LLKVE KKVEKL VVEKLKK EEKLKK KV 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 7 页 共 51 页 若不可能组成加法表 则应输出 ERROR 第五届全国青少年信息学奥林匹克分区联赛复赛试题第五届全国青少年信息学奥林匹克分区联赛复赛试题 19991999 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 第一题第一题 拦截导弹拦截导弹 28 28 分分 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一 个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发 的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 雷达给出的高度数据是不大于 30000 的正整数 计算这套 系统最多能拦截多少导弹 如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 样例 INPUT OUTPUT 389 207 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 进制的加法 上例最少用了 4 步得到回文数 4884 写一个程序 给定一个 N 2 N 10 或 N 16 进制数 M 求最少经过几步可以得到回文 数 如果在 30 步以内 包含 30 步 不可能得到回文数 则输出 Impossible 样例 INPUT OUTPUT N 9 M 87 STEP 6 第三题第三题 旅行家的预算旅行家的预算 27 27 分分 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 假设出发时油箱是空的 给定两个城市之间的距离 D1 汽车油箱的容量 C 以升为单位 每升汽油能行驶的距离 D2 出发点每升汽油价格 P 和沿途油站数 N N 可以为零 油站 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 每升汽油价格 Pi 1102 02 9 2220 02 2 OUTPUT 26 95 该数据表示最小费用 第四题第四题 邮票面值设计邮票面值设计 40 40 分分 给定一个信封 最多只允许粘贴 N 张邮票 计算在给定 K N K 40 种邮票的情况下 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 8 页 共 51 页 假定所有的邮票数量都足够 如何设计邮票的面值 能得到最大值 MAX 使在 1 MAX 之 间的每一个邮资值都能得到 例如 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 第六届全国青少年信息学奥林匹克分区联赛复赛试题第六届全国青少年信息学奥林匹克分区联赛复赛试题 20002000 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 进制转换一 进制转换 1818 分 分 问题描述问题描述 我们可以用这样的方式来表示一个十进制数 将每个阿拉伯数字乘以一个以该数字所 处位置的 值减 为指数 以 为底数的幂之和的形式 例如 可表示为 这样的形式 与之相似的 对二进制数来说 也可表示成每个二进制数码乘以一个以该数字所处位 置的 值 为指数 以 为底数的幂之和的形式 一般说来 任何一个正整数 或一个 负整数 都可以被选来作为一个数制系统的基数 如果是以 或 为基数 则需要用到 的数码为 例如 当 时 所需用到的数码是 和 这与其是 或 无关 如果作为基数的数绝对值超过 则为了表示这些数码 通常使用英文字母来表示那些大于 的数码 例如对 进制 数来说 用 表示 用 表示 用 表示 用 表示 用 表示 用 表示 在负进制数中是用 作为基数 例如 十进制 相当于 进制 并且它可以被表示为 的幂级数的和数 问题求解问题求解 设计一个程序 读入一个十进制数和一个负进制数的基数 并将此十进制数转换为此负 进制下的数 输入输入 输入的每行有两个输入数据 第一个是十进制数 32768 32767 第二个是负进制数的基数 输出输出 结果显示在屏幕上 相对于输入 应输出此负进制数及其基数 若此基数超过 则 参照 进制的方式处理 样例样例 输入 输出 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 9 页 共 51 页 二 乘积最大乘积最大 2222 分 分 问题描述问题描述 今年是国际数学联盟确定的 2000 世界数学年 又恰逢我国著名数学家华罗庚先 生诞辰 90 周年 在华罗庚先生的家乡江苏金坛 组织了一场别开生面的数学智力竞赛的活 动 你的一个好朋友 XZ 也有幸得以参加 活动中 主持人给所有参加活动的选手出了这样 一道题目 设有一个长度为 N 的数字串 要求选手使用 K 个乘号将它分成 K 1 个部分 找出一种分 法 使得这 K 1 个部分的乘积能够为最大 同时 为了帮助选手能够正确理解题意 主持人还举了如下的一个例子 有一个数字串 312 当 N 3 K 1 时会有以下两种分法 1 3 12 36 2 2 31 2 62 这时 符合题目要求的结果是 31 2 62 现在 请你帮助你的好朋友 XZ 设计一个程序 求得正确的答案 输入输入 程序的输入共有两行 第一行共有 2 个自然数 N K 6 N 40 1 K 6 第二行是一个长度为 N 的数字串 输出输出 结果显示在屏幕上 相对于输入 应输出所求得的最大乘积 一个自然数 样例样例 输入 4 2 1231 输出 62 三 单词接龙三 单词接龙 2727 分 分 问题描述问题描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏 现在我们已知一组单词 且给 定一个开头的字母 要求出以这个字母开头的最长的 龙 每个单词都最多在 龙 中出 现两次 在两个单词相连时 其重合部分合为一部分 例如 beast 和 astonish 如果接成 一条龙则变为 beastonish 另外相邻的两部分不能存在包含关系 例如 at 和 atide 间不 能相连 输入输入 输入的第一行为一个单独的整数 n n 20 表示单词数 以下 n 行每行有一个单词 输 入的最后一行为一个单个字符 表示 龙 开头的字母 你可以假定以此字母开头的 龙 一定存在 输出输出 只需输出以此字母开头的最长的 龙 的长度 样例样例 输入 5 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 10 页 共 51 页 at touch cheat choose tact a 输出 23 连成的 龙 为 atoucheatactactouchoose 四 四 方格取数方格取数 3333 分 分 问题描述问题描述 设有 N N 的方格图 N 1 要求由小到大依次在同一行输出这三个实根 根与根之间留有空 格 并精确到小数点后 2 位 提示 记方程 f x 0 若存在 2 个数 x1 和 x2 且 x1 x2 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 6 n 200 2 k 6 输出 一个整数 即不同的分法 样例样例 输入 7 3 输出 4 四种分法为 1 1 5 1 2 4 1 3 3 2 2 3 题三 统计单词个数 30 分 问题描述问题描述 给出一个长度不超过 200 的由小写英文字母组成的字母串 约定 该字串以每行 20 个字母的 方式输入 且保证每行一定为 20 个 要求将此字母串分成 k 份 1 k 40 且每份中包含 的单词个数加起来总数最大 每份中包含的单词可以部分重叠 当选用一个单词之后 其第 一个字母不能再用 例如字符串 this 中可包含 this 和 is 选用 this 之后就不能包含 th 单词在给出的一个不超过 6 个单词的字典中 要求输出最大的个数 输入格式输入格式 去部输入数据放在文本文件 input3 dat 中 其格式如下 第一行为一个正整数 0 n 5 表示有 n 组测试数据 每组的第一行有二个正整数 p k p 表示字串的行数 k 表示分为 k 个部分 接下来的 p 行 每行均有 20 个字符 再接下来有一个正整数 s 表示字典中单词个数 1 s 6 接下来的 s 行 每行均有一个单词 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 12 页 共 51 页 输出格式输出格式 结果输出至屏幕 每行一个整数 分别对应每组测试数据的相应结果 样例样例 输入 1 1 3 thisisabookyouareaoh 4 is a ok sab 输出 说明 不必输出 7 this isabookyoua reaoh 题四 Car 的旅行路线 30 分 问题描述问题描述 又到暑假了 住在城市 A 的 Car 想和朋友一起去城市 B 旅游 她知道每个城市都有四个飞机 场 分别位于一个矩形的四个顶点上 同一个城市中两个机场之间有一条笔直的高速铁路 第 I 个城市中高速铁路了的单位里程价格为 Ti 任意两个不同城市的机场之间均有航线 所有航线单位里程的价格均为 t 图例 机场 高速铁路 飞机航线 注意 图中并没有 标出所有的铁路与航线 那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢 她发现这并不是一个简单的 问题 于是她来向你请教 任务任务 找出一条从城市 A 到 B 的旅游路线 出发和到达城市中的机场可以任意选取 要求总的花费 最少 输入文件 键盘输入文件名 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 13 页 共 51 页 输 出 到屏幕 输出最小费用 小数点后保留 1 位 输入格式输入格式 第一行为一个正整数 n 0 n 10 表示有 n 组测试数据 每组的第一行有四个正整数 s t A B S 0 S 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 Ai B1 A2 B2 规则的含义为 在 A 中的子串 A1 可以变换为 B1 A2 可以变换为 B2 例如 A abcd B xyz 变换规则为 abc xu ud y y yz 则此时 A 可以经过一系列的变换变为 B 其变换的过程为 abcd xud xy xyz 共进行了三次变换 使得 A 变换为 B 输入输入 键盘输人文件名 文件格式如下 A B A1 B1 A2 B2 变换规则 所有字符串长度的上限为 20 输出输出 输出至屏幕 格式如下 若在 10 步 包含 10 步 以内能将 A 变换为 B 则输出最少的变换步数 否则输 出 NO ANSWER 输入输出样例输入输出样例 b in abcd wyz abc xu ud y y yz 屏幕显示 3 三 自由落体三 自由落体 问题描述问题描述 在高为 H 的天花板上有 n 个小球 体积不计 位置分别为 0 1 2 n 1 在地 面上有一个小车 长为 L 高为 K 距原点距离为 S1 已知小球下落距离计算公式为 d 1 2 g t 2 其中 g 10 t 为下落时间 地面上的小车以速度 V 前进 如下图 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 15 页 共 51 页 小车与所有小球同时开始运动 当小球距小车的距离 0 00001 时 即认为小球被小 车接受 小球落到地面后不能被接受 请你计算出小车能接受到多少个小球 输入输入 键盘输人 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 四 矩形覆盖四 矩形覆盖 问题描述问题描述 在平面上有 n 个点 n 50 每个点用一对整数坐标表示 例如 当 n 4 时 4 个点的坐标分另为 p1 1 1 p2 2 2 p3 3 6 P4 0 7 见图一 这些点可以用 k 个矩形 1 k 4 全部覆盖 矩形的边平行于坐标轴 当 k 2 时 可用如图二的两个矩形 sl s2 覆盖 s1 s2 面积和为 4 问题是当 n 个点坐标和 k 给 出后 怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢 约定 覆盖一个点的矩 形面积为 0 覆盖平行于坐标轴直线上点的矩形面积也为 0 各个矩形必须完全分开 边线 与顶点也都不能重合 输入输入 键盘输人文件名 文件格式为 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 16 页 共 51 页 n k xl y1 x2 y2 xn yn 0 xi yi 500 输出输出 输出至屏幕 格式为 一个整数 即满足条件的最小的矩形面积之和 输入输出样例输入输出样例 d in 4 2 1 1 2 2 3 6 0 7 屏幕显示 4 第九届全国青少年信息学奥林匹克分区联赛复赛试题第九届全国青少年信息学奥林匹克分区联赛复赛试题 20032003 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 神经网络一 神经网络 问题背景 人工神经网络 Artificial Neural Network 是一种新兴的具有自我学习能力的计算 系统 在模式识别 函数逼近及贷款风险评估等诸多领域有广泛的应用 对神经网络的研究 一直是当今的热门方向 兰兰同学在自学了一本神经网络的入门书籍后 提出了一个简化模 型 他希望你能帮助他用程序检验这个神经网络模型的实用性 问题描述 在兰兰的模型中 神经网络就是一张有向图 图中的节点称为神经元 而且两个神经 元之间至多有一条边相连 下图是一个神经元的例子 神经元 编号为 1 图中 X1 X3 是信息输入渠道 Y1 Y2 是信息输出渠道 C1 表示神经元目前的状态 Ui 是阈值 可视为神经元的一个内在参数 神经元按一定的顺序排列 构成整个神经网络 在兰兰的模型之中 神经网络中的神 经无分为几层 称为输入层 输出层 和若干个中间层 每层神经元只向下一层的神经元 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 17 页 共 51 页 输出信息 只从上一层神经元接受信息 下图是一个简单的三层神经网络的例子 兰兰规定 Ci服从公式 其中 n 是网络中所有神经元的数目 公式中的 Wji 可能为负值 表示连接 j 号神经元和 i 号神经元的边的权值 当 Ci 大 于 0 时 该神经元处于兴奋状态 否则就处于平静状态 当神经元处于兴奋状态时 下一秒 它会向其他神经元传送信号 信号的强度为 Ci 如此 在输入层神经元被激发之后 整个网络系统就在信息传输的推动下进行运作 现在 给定一个神经网络 及当前输入层神经元的状态 Ci 要求你的程序运算出最后网 络输出层的状态 输入格式 输入文件第一行是两个整数 n 1 n 20 和 p 接下来 n 行 每行两个整数 第 i 1 行是神经元 i 最初状态和其阈值 Ui 非输入层的神经元开始时状态必然为 0 再下面 P 行 每行由两个整数 i j 及一个整数 Wij 表示连接神经元 i j 的边权值为 Wij 输出格式 输出文件包含若干行 每行有两个整数 分别对应一个神经元的编号 及其最后的状 态 两个整数间以空格分隔 仅输出最后状态非零的输出层神经元状态 并且按照编号由 小到大顺序输出 若输出层的神经元最后状态均为 0 则输出 NULL 输入样例 5 6 1 0 1 0 0 1 0 1 0 1 1 3 1 1 4 1 1 5 1 2 3 1 2 4 1 2 5 1 输出样例 3 1 4 1 E i j ijjii UCWC 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 18 页 共 51 页 5 1 二 侦探推理二 侦探推理 问题描述 明明同学最近迷上了侦探漫画 柯南 并沉醉于推理游戏之中 于是他召集了一群同学 玩推理游戏 游戏的内容是这样的 明明的同学们先商量好由其中的一个人充当罪犯 在明 明不知情的情况下 明明的任务就是找出这个罪犯 接着 明明逐个询问每一个同学 被 询问者可能会说 证词中出现的其他话 都不列入逻辑推理的内容 明明所知道的是 他的同学中有 N 个人始终说假话 其余的人始终说真 现在 明明需要你帮助他从他同学的话中推断出谁是真正的凶手 请记住 凶手只有一 个 输入格式 输入由若干行组成 第一行有二个整数 M 1 M 20 N 1 N M 和 P 1 P 100 M 是参加游戏的明明的同学数 N 是其中始终说谎的人数 P 是证言的总数 接下来 M 行 每行是明明的一个同学的名字 英文字母组成 没有主格 全部大写 往后有 P 行 每行开始是某个同学的名宇 紧跟着一个冒号和一个空格 后面是一句证 词 符合前表中所列格式 证词每行不会超过 250 个字符 输入中不会出现连续的两个空格 而且每行开头和结尾也没有空格 输出格式 如果你的程序能确定谁是罪犯 则输出他的名字 如果程序判断出不止一个人可能是 罪犯 则输出 Cannot Determine 如果程序判断出没有人可能成为罪犯 则输出 Impossible 输入样例 3 1 5 MIKE CHARLES KATE MIKE I am guilty MIKE Today is Sunday CHARLES MIKE is guilty KATE I am guilty KATE How are you 输出样例 MIKE 三 加分二叉树三 加分二叉树 问题描述 设一个 n 个节点的二叉树 tree 的中序遍历为 l 2 3 n 其中数字 1 2 3 n 为 节点编号 每个节点都有一个分数 均为正整数 记第 j 个节点的分数为 di tree 及它的 每个子树都有一个加分 任一棵子树 subtree 也包含 tree 本身 的加分计算方法如下 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 19 页 共 51 页 subtree 的左子树的加分 subtree 的右子树的加分 subtree 的根的分数 若某个子树为主 规定其加分为 1 叶子的加分就是叶节点本身的分数 不考虑它的空 子树 试求一棵符合中序遍历为 1 2 3 n 且加分最高的二叉树 tree 要求输出 1 tree 的最高加分 2 tree 的前序遍历 输入格式 第 1 行 一个整数 n n 30 为节点个数 第 2 行 n 个用空格隔开的整数 为每个节点的分数 分数 100 输出格式 第 1 行 一个整数 为最高加分 结果不会超过 4 000 000 000 第 2 行 n 个用空格隔开的整数 为该树的前序遍历 输入样例 5 5 7 1 2 10 输出样例 145 3 1 2 4 5 四四 传染病控制 传染病控制 问题背景 近来 一种新的传染病肆虐全球 蓬莱国也发现了零星感染者 为防止该病在蓬莱国大 范围流行 该国政府决定不惜一切代价控制传染病的蔓延 不幸的是 由于人们尚未完全认 识这种传染病 难以准确判别病毒携带者 更没有研制出疫苗以保护易感人群 于是 蓬莱 国的疾病控制中心决定采取切断传播途径的方法控制疾病传播 经过 WHO 世界卫生组织 以及全球各国科研部门的努力 这种新兴传染病的传播途径和控制方法已经研究消楚 剩下 的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法 问题描述 研究表明 这种传染病的传播具有两种很特殊的性质 第一是它的传播途径是树型的 一个人 X 只可能被某个特定的人 Y 感染 只要 Y 不 得病 或者是 XY 之间的传播途径被切断 则 X 就不会得病 第二是 这种疾病的传播有周期性 在一个疾病传播周期之内 传染病将只会感染一 代患者 而不会再传播给下一代 这些性质大大减轻了蓬莱国疾病防控的压力 并且他们已经得到了国内部分易感人群的 潜在传播途径图 一棵树 但是 麻烦还没有结束 由于蓬莱国疾控中心人手不够 同时 也缺乏强大的技术 以致他们在一个疾病传播周期内 只能设法切断一条传播途径 而没有 被控制的传播途径就会引起更多的易感人群被感染 也就是与当前已经被感染的人有传播途 径相连 且连接途径没有被切断的人群 当不可能有健康人被感染时 疾病就中止传播 所以 蓬莱国疾控中心要制定出一个切断传播途径的顺序 以使尽量少的人被感染 你的程 序要针对给定的树 找出合适的切断顺序 输入格式 输入格式的第一行是两个整数 n 1 n 300 和 p 接下来 p 行 每一行有两个整数 i 和 j 表示节点 i 和 j 间有边相连 意即 第 i 人和第 j 人之间有传播途径相连 其中节 点 1 是已经被感染的患者 输出格式 只有一行 输出总共被感染的人数 输入样例 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 20 页 共 51 页 7 6 1 2 1 3 2 4 2 5 3 6 3 7 输出样例 3 第十届全国青少年信息学奥林匹克分区联赛复赛试题第十届全国青少年信息学奥林匹克分区联赛复赛试题 20042004 年年 提高组提高组 竞赛用时 竞赛用时 3 3 小时 小时 一 津津的储蓄计划一 津津的储蓄计划 问题描述问题描述 津津的零花钱一直都是自己管理 每个月的月初妈妈给津津 300 元钱 津津会预算这个 月的花销 并且总能做到实际花销和预算的相同 为了让津津学习如何储蓄 妈妈提出 津津可以随时把整百的钱存在她那里 到了年末 她会加上 20 还给津津 因此津津制定了一个储蓄计划 每个月的月初 在得到妈妈给的 零花钱后 如果她预计到这个月的月末手中还会有多于 100 元或恰好 100 元 她就会把整百 的钱存在妈妈那里 剩余的钱留在自己手中 例如 11 月初津津手中还有 83 元 妈妈给了津津 300 元 津津预计 11 月的花销是 180 元 那么她就会在妈妈那里存 200 元 自己留下 183 元 到了 11 月月末 津津手中会剩下 3 元钱 津津发现这个储蓄计划的主要风险是 存在妈妈那里的钱在年末之前不能取出 有可能 在某个月的月初 津津手中的钱加上这个月妈妈给的钱 不够这个月的原定预算 如果出现 这种情况 津津将不得不在这个月省吃俭用 压缩预算 现在请你根据 2004 年 1 月到 12 月每个月津津的预算 判断会不会出现这种情况 如果 不会 计算到 2004 年年末 妈妈将津津平常存的钱加上 20 还给津津之后 津津手中会有 多少钱 输入文件 输入文件 save in 包括 12 行数据 每行包含一个小于 350 的非负整数 分别表示 1 月 到 12 月津津的预算 输出文件 输出文件 save out 包括一行 这一行只包含一个整数 如果储蓄计划实施过程中出现 某个月钱不够用的情况 输出 X X 表示出现这种情况的第一个月 否则输出到 2004 年年 末津津手中会有多少钱 样例输入 1 290 230 280 200 300 170 340 50 90 80 200 60 样例输出 1 7 样例输入 2 290 230 280 200 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 21 页 共 51 页 300 170 330 50 90 80 200 60 样例输出 2 1580 二 合并果子二 合并果子 问题描述 在一个果园里 多多已经将所有的果子打了下来 而且按果子的不同种类分成了不同的 堆 多多决定把所有的果子合成一堆 每一次合并 多多可以把两堆果子合并到一起 消耗的体力等于两堆果子的重量之和 可以看出 所有的果子经过 n 1 次合并之后 就只剩下一堆了 多多在合并果子时总共消耗 的体力等于每次合并所耗体力之和 因为还要花大力气把这些果子搬回家 所以多多在合并果子时要尽可能地节省体力 假 定每个果子重量都为 1 并且已知果子的种类数和每种果子的数目 你的任务是设计出合并 的次序方案 使多多耗费的体力最少 并输出这个最小的体力耗费值 例如有 3 种果子 数目依次为 1 2 9 可以先将 1 2 堆合并 新堆数目为 3 耗费体 力为 3 接着 将新堆与原先的第三堆合并 又得到新的堆 数目为 12 耗费体力为 12 所以多多总共耗费体力 3 12 15 可以证明 15 为最小的体力耗费值 输入文件 输入文件 fruit in 包括两行 第一行是一个整数 n 1 n 10000 表示果子的种类 数 第二行包含 n 个整数 用空格分隔 第 i 个整数 ai 1 ai 20000 是第 i 种果子的数 目 输出文件 输出文件 fruit out 包括一行 这一行只包含一个整数 也就是最小的体力耗费值 输 入数据保证这个值小于 231 样例输入 3 1 2 9 样例输出 15 数据规模 对于 30 的数据 保证有 n 1000 对于 50 的数据 保证有 n 5000 对于全部的数据 保证有 n 10000 三 合唱队形三 合唱队形 问题描述 N 位同学站成一排 音乐老师要请其中的 N K 位同学出列 使得剩下的 K 位同学排成 合唱队形 合唱队形是指这样的一种队形 设 K 位同学从左到右依次编号为 1 2 K 他们的身 高分别为 T1 T2 TK 则他们的身高满足 T1 Ti 1 TK 1 i K 你的任务是 已知所有 N 位同学的身高 计算最少需要几位同学出列 可以使得剩下的 同学排成合唱队形 输入文件 输入文件 chorus in 的第一行是一个整数 N 2 N 100 表示同学的总数 第一行有 n 个整数 用空格分隔 第 i 个整数 Ti 130 Ti 230 是第 i 位同学的身高 厘米 输出文件 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 22 页 共 51 页 输出文件 chorus out 包括一行 这一行只包含一个整数 就是最少需要几位同学出列 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4 数据规模 对于 50 的数据 保证有 n 20 对于全部的数据 保证有 n 100 四 虫食算四 虫食算 问题描述 所谓虫食算 就是原先的算式中有一部分被虫子啃掉了 需要我们根据剩下的数字来判 定被啃掉的字母 来看一个简单的例子 43 9865 045 8468 6633 44445506978 其中 号代表被虫子啃掉的数字 根据算式 我们很容易判断 第一行的两个数字分别 是 5 和 3 第二行的数字是 5 现在 我们对问题做两个限制 首先 我们只考虑加法的虫食算 这里的加法是 N 进制加法 算式中三个数都有 N 位 允许有前导的 0 其次 虫子把所有的数都啃光了 我们只知道哪些数字是相同的 我们将相同的数字用 相同的字母表示 不同的数字用不同的字母表示 如果这个算式是 N 进制的 我们就取英文 字母表午的前 N 个大写字母来表示这个算式中的 0 到 N 1 这 N 个不同的数字 但是这 N 个字 母并不一定顺序地代表 0 到 N 1 输入数据保证 N 个字母分别至少出现一次 BADC CRDA DCCC 上面的算式是一个 4 进制的算式 很显然 我们只要让 ABCD 分别代表 0123 便可以让 这个式子成立了 你的任务是 对于给定的 N 进制加法算式 求出 N 个不同的字母分别代表 的数字 使得该加法算式成立 输入数据保证有且仅有一组解 输入文件 输入文件 alpha in 包含 4 行 第一行有一个正整数 N N 26 后面的 3 行每行有一个 由大写字母组成的字符串 分别代表两个加数以及和 这 3 个字符串左右两端都没有空格 从高位到低位 并且恰好有 N 位 输出文件 输出文件 alpha out 包含一行 在这一行中 应当包含唯一的那组解 解是这样表示的 输出 N 个数字 分别表示 A B C 所代表的数字 相邻的两个数字用一个空格隔开 不 能有多余的空格 样例输入 5 ABCED BDACE EBBAA 样例输出 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 23 页 共 51 页 1 0 3 4 2 数据规模 对于 30 的数据 保证有 N 10 对于 50 的数据 保证有 N 15 对于全部的数据 保证有 N80 并且在本学期内发表 1 篇 或 1 篇以上论文的学生均可获得 2 五四奖学金 每人 4000 元 期末平均成绩高于 85 分 85 并且班级评议成绩高于 80 分 80 的学生均可获得 3 成绩优秀奖 每人 2000 元 期末平均成绩高于 90 分 90 的学生均可获得 4 西部奖学金 每人 1000 元 期末平均成绩高于 85 分 85 的西部省份学生均可获得 5 班级贡献奖 每人 850 元 班级评议成绩高于 80 分 80 的学生干部均可获得 只要符合条件就可以得奖 每项奖学金的获奖人数没有限制 每名学生也可以同时获得 多项奖学金 例如姚林的期末平均成绩是 87 分 班级评议成绩 82 分 同时他还是一位学生 干部 那么他可以同时获得五四奖学金和班级贡献奖 奖金总数是 4850 元 现在给出若干学生的相关数据 请计算哪些同学获得的奖金总数最高 假设总有同学能 满足获得奖学金的条件 输入文件 输入文件 scholar in 的第一行是一个整数 N 1 N 100 表示学生的总数 接下来 的 N 行每行是一位学生的数据 从左向右依次是姓名 期末平均成绩 班级评议成绩 是否 是学生干部 是否是西部省份学生 以及发表的论文数 姓名是由大小写英文字母组成的长 度不超过 20 的字符串 不含空格 期末平均成绩和班级评议成绩都是 0 到 100 之间的整数 包括 0 和 100 是否是学生干部和是否是西部省份学生分别用一个字符表示 Y 表示是 N 表示不是 发表的论文数是 0 到 10 的整数 包括 0 和 10 每两个相邻数据项之间用一个 空格分隔 输出文件 输出文件 scholar out 包括三行 第一行是获得最多奖金的学生的姓名 第二行是这名学生 获得的奖金总数 如果有两位或两位以上的学生获得的奖金最多 输出他们之中在输入文件 中出现最早的学生的姓名 第三行是这 N 个学生获得的奖学金的总数 样例输入 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 样例输出 ChenRuiyi 9000 28700 全国青少年信息学奥林匹克联赛初赛试题汇编 提高组 复赛 2010 年 4 月 16 日 张二伟 第 24 页 共