NOIP+提高组复赛试题汇编(1998-2009).pdf

1 NOIP 1998 1 火车从始发站 称为第 1 站 开出 在始发站上车的人数为 a 然后到达第 2 站 在第 2 站有人上 下车 但上 下车的人数相同 因此在第 2 站开出时 即在到达第 3 站之前 车上的人数保持为 a 人 从第 3 站起 包括第 3 站 上 下车的人数有一定规律 上车的人数都是前两站上车人数之和 而下车人数等于上一站上车人数 一直到终点站的前一站 第 n 1 站 都满足此规律 现给出的 条件是 共有 N 个车站 始发站上车的人数为 a 最后一站下车的人数是 m 全部下车 试问 x 站 开出时车上的人数是多少 2 设有 n 个正整数 n 20 将它们联接成一排 组成一个最大的多位整数 例如 n 3 时 3 个整数 13 312 343 联接成的最大整数为 34331213 又如 n 4 时 4 个整数 7 13 4 246 联接成的最大整数为 7424613 3 著名科学家卢斯为了检查学生对进位制的理解 他给出了如下的一张加法表 表中的字母代表数字 例如 其含义为 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 进制加法 NOIP 1999 第一题拦截导弹第一题拦截导弹 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽 然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕 捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 雷达给出的高度数据是不大于 30000 的正整数 计算这套系统最多能 拦截多少导弹 如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 样例 INPUTOUTPUT 389 207 155 300 299 170 158 656 最多能拦截的导弹数 2 要拦截所有导弹最少要配备的系统数 输入 a n m 和 x输出 从 x 站开出时车上的人数 程序输入 n n 个数 程序输出 联接成的多位数 程序输入 n n 9 表示行数 以下 n 行 每行包括 n 个字符串 每个字串间 用空格隔开 字串仅有一个为 号 其它都 由大写字母组成 程序输出 各个字母表示什么数 格式如 L 0 K 1 加法运算是几进制的 若不可能组成加法表 则应输出 ERROR LKVE LLKVE KKVEKL VVEKLKK EEKLKKKV 2 第二题回文数第二题回文数 若一个数 首位不为零 从左向右读与从右向左读都一样 我们就将其称之为回文数 例如 给定一个 10 进制数 56 将 56 加 65 即把 56 从右向左读 得到 121 是一个回文数 又如 对于 10 进制数 87 STEP1 87 78 165STEP2 165 561 726 STEP3 726 627 1353STEP4 1353 3531 4884 在这里的一步是指进行了一次 N 进制的加法 上例最少用了 4 步得到回文数 4884 写一个程序 给定一个 N 2 N 10 或 N 16 进制数 M 求最少经过几步可以得到回文数 如果在 30 步以内 包含 30 步 不可能得到回文数 则输出 Impossible 样例 INPUTOUTPUT N 9M 87STEP 6 第三题旅行家的预算第三题旅行家的预算 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 假设出发时油箱是空的 给定两 个城市之间的距离 D1 汽车油箱的容量 C 以升为单位 每升汽油能行驶的距离 D2 出发点每升汽油 价格 P 和沿途油站数 N N 可以为零 油站 i 离出发点的距离 Di 每升汽油价格 Pi i 1 2 N 计算结果四舍五入至小数点后两位 如果无法到达目的地 则输出 No Solution 样例 INPUT D1 275 6C 11 9D2 27 4P 2 8N 2 OUTPUT 26 95 该数据表示最小费用 第四题邮票面值设计第四题邮票面值设计 给定一个信封 最多只允许粘贴 N 张邮票 计算在给定 K N K 40 种邮票的情况下 假定所有 的邮票数量都足够 如何设计邮票的面值 能得到最大值 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 分 样例 INPUTOUTPUT N 3K 213 MAX 7 油站号 I离出发点的距离 Di每升汽油价格 Pi 1102 02 9 2220 02 2 3 NOIP 2000 题一进制转换 问题描述 题一进制转换 问题描述 我们可以用这样的方式来表示一个十进制数 将每个阿拉伯数字乘以一个以该数字所处位置的 值 减 1 为指数 以 10 为底数的幂之和的形式 例如 123 可表示为 1 102 2 101 3 100这样的形式 与之相似的 对二进制数来说 也可表示成每个二进制数码乘以一个以该数字所处位置的 值 1 为指数 以 2 为底数的幂之和的形式 一般说来 任何一个正整数 或一个负整数 都可以被选来作 为一个数制系统的基数 如果是以 或 为基数 则需要用到的数码为 0 1 1 例如 当 7 时 所需用到的数码是 0 1 2 3 4 5 和 6 这与其是 或 无关 如果作为基数的数绝 对值超过 10 则为了表示这些数码 通常使用英文字母来表示那些大于 9 的数码 例如对 16 进制数来 说 用 表示 10 用 表示 11 用 表示 12 用 表示 13 用 表示 14 用 表示 15 在负进制数中是用 作为基数 例如 15 十进制 相当于 110001 2 进制 并且它可以被表 示为 2 的幂级数的和数 110001 1 2 5 1 2 4 0 2 3 0 2 2 0 2 1 1 2 0 问题求解问题求解 设计一个程序 读入一个十进制数和一个负进制数的基数 并将此十进制数转换为此负进制下的 数 2 3 4 20 样例样例 题二乘积最大 问题描述 题二乘积最大 问题描述 今年是国际数学联盟确定的 2000 世界数学年 又恰逢我国著名数学家华罗庚先生诞辰 90 周 年 在华罗庚先生的家乡江苏金坛 组织了一场别开生面的数学智力竞赛的活动 你的一个好朋友 XZ 也有幸得以参加 活动中 主持人给所有参加活动的选手出了这样一道题目 设有一个长度为 N 的数字串 要求选手使用 K 个乘号将它分成 K 1 个部分 找出一种分法 使得 这 K 1 个部分的乘积能够为最大 同时 为了帮助选手能够正确理解题意 主持人还举了如下的一个例子 有一个数字串 312 当 N 3 K 1 时会有以下两种分法 1 3 12 36 2 31 2 62 这时 符合题目要求的结果是 31 2 62 现在 请你帮助你的好朋友 XZ 设计一个程序 求得正确的答案 样例样例 输入输入 输入的每行有两个输入数据 第一个是十进制数 32768 32767 第二个是负进制数的基数 输出输出 结果显示在屏幕上 相对于输入 应输出此负 进制数及其基数 若此基数超过 10 则参照 16 进 制的方式处理 30000 2 20000 2 28800 16 25000 16 30000 11011010101110000 base 2 20000 1111011000100000 base 2 28000 19180 base 16 25000 7 8 base 16 输入输入 程序的输入共有两行 第一行共有 2 个自然数 N K 6 N 40 1 K 6 第二行是一个长度为 N 的数字串 输出输出 结果显示在屏幕上 相对于输入 应输出所求 得的最大乘积 一个自然数 42 1231 62 4 题三 单词接龙 问题描述 题三 单词接龙 问题描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏 现在我们已知一组单词 且给定一个开头 的字母 要求出以这个字母开头的最长的 龙 每个单词都最多在 龙 中出现两次 在两个单词相连 时 其重合部分合为一部分 例如 beast 和 astonish 如果接成一条龙则变为 beastonish 另外 相邻的两部分不能存在包含关系 例如 at 和 atide 间不能相连 样例样例 题四 方格取数 问题描述 题四 方格取数 问题描述 设有 N N 的方格图 N 10 我们将其中的某些方格中填入正整数 而其他的方格中则放入数字 0 如下图所示 见样例 某人从图的左上角的 A 点出发 可以向下行走 也可以向右走 直到到达右下角的 B 点 在走过的 路上 他可以取走方格中的数 取走后的方格中将变为数字 0 此人从 A 点到 B 点共走两次 试找出 2 条这样的路径 使得取得的数之和为最大 样例样例 输入输入 输入的第一行为一个单独的整数 n n 1 要求由小到大依次在同一行输出这三个实根 根与根之间留有空格 并精确到小数点后 2 位 提示 记方程 f x 0 若存在 2 个数 x1 和 x2 且 x1 x2 f x1 f x2 0 则在 x1 x2 之间 一定有一个 根 样例样例 题二 数的划分 问题描述 题二 数的划分 问题描述 将整数 n 分成 k 份 且每份不能为空 任意两份不能相同 不考虑顺序 例如 n 7 k 3 下面三种分法被认为是相同的 1 1 5 1 5 1 5 1 1 问有多少种不同的分法 样例样例 题三 统计单词个数 问题描述 题三 统计单词个数 问题描述 给出一个长度不超过 200 的由小写英文字母组成的字母串 约定 该字串以每行 20 个字母的方式输入 且保证每行一定为 20 个 要求将此字母串分成 k 份 1 k 40 且每份中包含的单词个数加起来总 数最大 每份中包含的单词可以部分重叠 当选用一个单词之后 其第一个字母不能再用 例如字符串 this 中可包含 this 和 is 选用 this 之后就不能包含 th 单词在给出的一个不超过 6 个单词的字典中 要求输出最大的个数 样例样例 输入 1 5 420输出 2 002 005 00 输入 n k 6 n 200 2 k 6 输出 一个整数 即不同的分法 输入 7 3输出 4 四种分法为 1 1 5 1 2 4 1 3 3 2 2 3 输入格式输入格式 去部输入数据放在文本文件 input3 dat 中 其格式如下 第一行为一个正整数 0 n 5 表示有 n 组测试数据 每组的第一行有二个正整数 p k p 表示字串的行数 k 表示分为 k 个部分 接下来的 p 行 每行均有 20 个字符 再接下来有一个正整数 s 表示字典中单词个数 1 s 6 接下来的 s 行 每行均有一个单词 输出格式输出格式 结果输出至屏幕 每行一个整数 分别对应每组测试数据的相应结 果 1 1 3 thisisabookyouareaoh 4 is a ok sab 7 说明 this isabookyoua reaoh 不必输出 6 题四题四 Car 的旅行路线 问题描述 的旅行路线 问题描述 又到暑假了 住在城市 A 的 Car 想和朋友一起去城市 B 旅游 她知道每个城市都有四个飞机场 分别 位于一个矩形的四个顶点上 同一个城市中两个机场之间有一条笔直的高速铁路 第 I 个城市中高速铁 路了的单位里程价格为 Ti 任意两个不同城市的机场之间均有航线 所有航线单位里程的价格均为 t 注意 图中 并没有标出 所有的铁路 和航线 飞机航线 高速公路 机场 那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢 她发现这并不是一个简单的问题 于是 她来向你请教 如何找出一条从城市 A 到 B 的旅游路线 出发和到达城市中的机场可以任意选取 要求 总的花费最少 输入格式输入格式 第一行为一个正整数 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 输入输出样例输入输出样例 题二 字串变换题二 字串变换 问题描述问题描述 已知有两个字串 A B 及一组字串变换的规则 至多 6 个规则 A1 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 输入输出样例输入输出样例 输 入输 入 键盘输入文件名 文件格式 N N 堆纸牌 1 N 100 A1 A2 An N 堆纸牌 每堆纸牌初始数 l Ai 变换规则 所有字符串长度的上限为 20 输出输出 输出至屏幕 格式如下 若在 10 步 包含 10 步 以内能将 A 变换 为 B 则输出最少的变换步数 否则输出 NO ANSWER abcd wyz abc xu ud y y yz 3 8 题三 自由落体题三 自由落体 问题描述问题描述 在高为 H 的天花板上有 n 个小球 体积不计 位置分别为 0 1 2 n 1 在地面上有一个 小车 长为 L 高为 K 距原点距离为 S1 已知小球下落距离计算公式为 d 1 2 g t 2 其 中 g 10 t 为下落时间 地面上的小车以速度 V 前进 如下图 小车与所有小球同时开始运 动 当小球距小车的距离 0 00001 时 即认为小球被小 车接受 小球落到地面后不能被 接受 请你计算出小车能接受到多 少个小球 输入输出样例输入输出样例 题四 矩形覆盖题四 矩形覆盖 问题描述问题描述 在平面上有 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 各个矩形必须完全分开 边线与顶点也都不能重合 输入输出样例输入输出样例 输入输入 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 k xl y1 x2 y2 xn yn 0 xi yi 500 输出输出 一个整数 即满足条件的最小的矩形面积之 和 4 2 1 1 2 2 3 6 0 7 4 9 NOIP 2003 题一神经网络题一神经网络 问题背景 人工神经网络 Artificial Neural Network 是一种新兴的具有自我学习能力的计算系统 在模式识别 函数逼近及贷款风险评估等诸多领域有广泛的应用 对神经网络的研究一直是当今的热门方向 兰兰同 学在自学了一本神经网络的入门书籍后 提出了一个简化模型 他希望你能帮助他用程序检验这个神经 网络模型的实用性 问题描述 在兰兰的模型中 神经网络就是一张有向图 图中的节点 称为神经元 而且两个神经元之间至多有一条边相连 下图是 一个神经元的例子 神经元 编号为 1 图中 X1 X3 是信息输入渠道 Y1 Y2 是信息输出渠 道 C1 表示神经元目前的状态 Ui 是阈值 可视为神经元的 一个内在参数 神经元按一定的顺序排列 构成整个神经网络 在兰兰的模型之中 神经网络中的神 经无分为几层 称为输入层 输出层 和若干个中间层 每层神经元只向下一层的神经元 输出信息 只从上一层神经元接受信息 下图是一个简 单的三层神经网络的例子 兰兰规定 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 5 1 Eij ijjii UCWC 10 题二侦探推理题二侦探推理 问题描述 明明同学最近迷上了侦探漫画 柯南 并沉醉于推理游戏之中 于是他召集了一群同学玩推理游戏 游戏的内容是这样的 明明的同学们先商量好由其中的一个人充当罪犯 在明明不知情的情况下 明 明的任务就是找出这个罪犯 接着 明明逐个询问每一个同学 被询问者可能会说 证词中出现的其他话 都不列入逻辑推理的内容 明明所知道的是 他的 同学中有 N 个人始终说假 话 其余的人始终说真 现在 明明需要你帮助 他从他同学的话中推断出谁是真正的凶手 请记住 凶手只有一个 输入格式 输入由若干行组成 第一行有二个整数 M 1 M 20 N 1 N M 和 P 1 P 100 M 是参加游戏的明明的同学数 N 是其中始终说谎的人数 P 是证言的总数 接下来 M 行 每行是明明的一个同学的名字 英文字母组成 没有主格 全部大写 往后有 P 行 每行开始是某个同学的名宇 紧跟着一个冒号和一个空格 后面是一句证词 符合前 表中所列格式 证词每行不会超过 250 个字符 输入中不会出现连续的两个空格 而且每行开头和结尾也没有空格 输出格式 如果你的程序能确定谁是罪犯 则输出他的名字 如果程序判断出不止一个人可能是 罪犯 则输出 Cannot Determine 如果程序判断出没有人可能成为罪犯 则输出 Impossible 题三加分二叉树题三加分二叉树 问题描述 设一个 n 个节点的二叉树 tree 的中序遍历为 l 2 3 n 其中数字 1 2 3 n 为节点编号 每个节 点都有一个分数 均为正整数 记第 j 个节点的分数为 di tree 及它的每个子树都有一个加分 任一棵 子树 subtree 也包含 tree 本身 的加分计算方法如下 subtree 的左子树的加分 subtree 的右子树的加分 subtree 的根的分数 若某个子树为主 规定其加分为 1 叶子的加分就是叶节点本身的分数 不考虑它的空子树 试求一棵符合中序遍历为 1 2 3 n 且加分最高的二叉树 tree 要求输出 1 tree 的最高加分 2 2 tree 的前序遍历 3 输入样例 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 输入格式 第 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 11 题四传染病控制题四传染病控制 问题背景 近来 一种新的传染病肆虐全球 蓬莱国也发现了零星感染者 为防止该病在蓬莱国大范围流行 该国政府决定不惜一切代价控制传染病的蔓延 不幸的是 由于人们尚未完全认识这种传染病 难以准 确判别病毒携带者 更没有研制出疫苗以保护易感人群 于是 蓬莱国的疾病控制中心决定采取切断传 播途径的方法控制疾病传播 经过 WHO 世界卫生组织 以及全球各国科研部门的努力 这种新兴传 染病的传播途径和控制方法已经研究消楚 剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控 制办法 问题描述 研究表明 这种传染病的传播具有两种很特殊的性质 第一是它的传播途径是树型的 一个人 X 只可能被某个特定的人 Y 感染 只要 Y 不得病 或者是 XY 之间的传播途径被切断 则 X 就不会得病 第二是 这种疾病的传播有周期性 在一个疾病传播周期之内 传染病将只会感染一代患者 而不 会再传播给下一代 这些性质大大减轻了蓬莱国疾病防控的压力 并且他们已经得到了国内部分易感人群的潜在传播途 径图 一棵树 但是 麻烦还没有结束 由于蓬莱国疾控中心人手不够 同时也缺乏强大的技术 以 致他们在一个疾病传播周期内 只能设法切断一条传播途径 而没有被控制的传播途径就会引起更多的 易感人群被感染 也就是与当前已经被感染的人有传播途径相连 且连接途径没有被切断的人群 当 不可能有健康人被感染时 疾病就中止传播 所以 蓬莱国疾控中心要制定出一个切断传播途径的顺序 以使尽量少的人被感染 你的程序要针对给定的树 找出合适的切断顺序 输入格式 输入格式的第一行是两个整数 n 1 n 300 和 p 接下来 p 行 每一行有两个整数 i 和 j 表示节点 i 和 j 间有边相连 意即 第 i 人和第 j 人之间有传播途径相连 其中节点 1 是已经被感染的患者 输出格式 只有一行 输出总共被感染的人数 输入样例 7 6 1 2 1 3 2 4 2 5 3 6 3 7 输出样例 3 12 NOIP 2004 一 津津的储蓄计划一 津津的储蓄计划 Save pas dpr c cpp 问题描述 津津的零花钱一直都是自己管理 每个月的月初妈妈给津津 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 300 170 330 50 90 80 200 60 样例输出 2 1580 13 二 合并果子二 合并果子 fruit pas dpr c cpp 问题描述 在一个果园里 多多已经将所有的果子打了下来 而且按果子的不同种类分成了不同的堆 多多决 定把所有的果子合成一堆 每一次合并 多多可以把两堆果子合并到一起 消耗的体力等于两堆果子的重量之和 可以看出 所有的果子经过 n 1 次合并之后 就只剩下一堆了 多多在合并果子时总共消耗的体力等于每次合并所 耗体力之和 因为还要花大力气把这些果子搬回家 所以多多在合并果子时要尽可能地节省体力 假定每个果子 重量都为 1 并且已知果子的种类数和每种果子的数目 你的任务是设计出合并的次序方案 使多多耗 费的体力最少 并输出这个最小的体力耗费值 例如有 3 种果子 数目依次为 1 2 9 可以先将 1 2 堆合并 新堆数目为 3 耗费体力为 3 接着 将新堆与原先的第三堆合并 又得到新的堆 数目为 12 耗费体力为 12 所以多多总共耗费体 力 3 12 15 可以证明 15 为最小的体力耗费值 数据规模 对于 30 的数据 保证有 n 1000 对于 50 的数据 保证有 n 5000 对于全部的数据 保证有 n 10000 三 合唱队形三 合唱队形 chorus pas dpr c cpp 问题描述 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 位同学的身高 厘米 输出文件 输出文件 chorus out 包括一行 这一行只包含一个整数 就是最少需要几位同学出列 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4 数据规模 对于 50 的数据 保证有 n 20 对于全部的数据 保证有 n 100 输入文件 输入文件 fruit in 包括两行 第一行是一 个整数 n 1 n 10000 表示果子的种类数 第二行包含 n 个整数 用空格分隔 第 i 个整数 ai 1 ai 20000 是第 i 种果子的数目 输出文件 输出文件 fruit out 包括一行 这一行只包 含一个整数 也就是最小的体力耗费值 输入数据 保证这个值小于 231 样例输入 3 1 2 9 样例输出 15 14 四 虫食算四 虫食算 alpha pas dpr c cpp 问题描述 所谓虫食算 就是原先的算式中有一部分被虫子啃掉了 需要我们根据剩下的数字来判定被啃掉的 字母 来看一个简单的例子 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 样例输出 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 16 二 过河二 过河 river pas c cpp 问题描述 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青蛙很讨厌 踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达 的点看成数轴上的一串整点 0 1 L 其中 L 是桥的长度 坐标为 0 的点表示桥的起点 坐标 为 L 的点表示桥的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳跃的距离是 S 到 T 之间 的任意正整数 包括 S T 当青蛙跳到或跳过坐标为 L 的点时 就算青蛙已经跳出了独木桥 题目给出独木桥的长度 L 青蛙跳跃的距离范围 S T 桥上石子的位置 你的任务是确定青蛙要想过河 最少需要踩到的石子数 输入文件 输入文件 river in 的第一行有一个正整数 L 1 L 109 表示独木桥的长度 第二行有三个正 整数 S T M 分别表示青蛙一次跳跃的最小距离 最大距离 及桥上石子的个数 其中 1 S T 10 1 M 100 第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置 数据 保证桥的起点和终点处没有石子 所有相邻的整数之间用一个空格隔开 输出文件 输出文件 river out 只包括一个整数 表示青蛙过河最少需要踩到的石子数 三 篝火晚会三 篝火晚会 fire pas c cpp 问题描述 佳佳刚进高中 在军训的时候 由于佳佳吃苦耐劳 很快得到了教官的赏识 成为了 小教官 在军训 结束的那天晚上 佳佳被命令组织同学们进行篝火晚会 一共有 n 个同学 编号从 1 到 n 一开始 同 学们按照 1 2 n 的顺序坐成一圈 而实际上每个人都有两个最希望相邻的同学 如何下命令调 整同学的次序 形成新的一个圈 使之符合同学们的意愿 成为摆在佳佳面前的一大难题 佳佳可向同学们下达命令 每一个命令的形式如下 b1 b2 bm 1 bm 这里m的值是由佳佳决定的 每次命令m的值都可以不同 这个命令的作用是移动编号是b1 b2 bm 1 bm的这 m 个同学的位置 要求 b1换到 b2的位置上 b2换到 b3的位置上 要求 bm换到 b1 的位置上 执行每个命令都需要一些代价 我们假定如果一个命令要移动 m 个人的位置 那么这个命令的代价就是 m 我们需要佳佳用最少的总代价实现同学们的意愿 你能帮助佳佳吗 输入文件 输入文件 fire in 的第一行是一个整数 n 3 n 50000 表示一共有 n 个同学 其后 n 行每行 包括两个不同的正整数 以一个空格隔开 分别表示编号是 1 的同学最希望相邻的两个同学的编号 编 号是 2 的同学最希望相邻的两个同学的编号 编号是 n 的同学最希望相邻的两个同学的编号 输出文件 输出文件 fire out 包括一行 这一行只包含一个整数 为最小的总代价 如果无论怎么调整都不能符合 每个同学的愿望 则输出 1 样例输入 10 2 3 5 2 3 5 6 7 样例输出 2 数据规模 对于 30 的数据 L 10000 对于全部的数据 L 109 样例输入 4 3 4 4 3 1 2 1 2 样例输出 2 数据规模 对于 30 的数据 n 1000 对于全部的数据 n 50000 17 四 等价表达式四 等价表达式 equal pas c cpp 问题描述 明明进了中学之后 学到了代数表达式 有一天 他碰到一个很麻烦的选择题 这个题目的题干中首先 给出了一个代数表达式 然后列出了若干选项 每个选项也是一个代数表达式 题目的要求是判断选项 中哪些代数表达式是和题干中的表达式等价的 这个题目手算很麻烦 因为明明对计算机编程很感兴趣 所以他想是不是可以用计算机来解决这个问题 假设你是明明 能完成这个任务吗 这个选择题中的每个表达式都满足下面的性质 1 表达式只可能包含一个变量 a 2 表达式中出现的数都是正整数 而且都小于 10000 3 表达式中可以包括四种运算 加 减 乘 乘幂 以及小括号 小括 号的优先级最高 其次是 然后是 最后是 和 和 的优先级是相同的 相同优先级的运 算从左到右进行 注意 运算符 以及小括号 都是英文字符 4 幂指数只可能是 1 到 10 之间的正整数 包括 1 和 10 5 表达式内部 头部或者尾部都可能有一些多余的空格 下面是一些合理的表达式的例子 a 1 2 3 a a a a a a 9999 a a a 1 a 1 3 1 10 9 输入文件 输入文件 equal in 的第一行给出的是题干中的表达式 第二行是一个整数 n 2 n 26 表示 选项的个数 后面 n 行 每行包括一个选项中的表达式 这 n 个选项的标号分别是 A B C D 输入中的表达式的长度都不超过 50 个字符 而且保证选项中总有表达式和题干中的表达式是等价的 输出文件 输出文件 equal out 包括一行 这一行包括一系列选项的标号 表示哪些选项是和题干中的表达式等价 的 选项的标号按照字母顺序排列 而且之间没有空格 样例输入 a 1 2 3 a 1 2 4 a a 1 a a 2 2 a 1 1 2 10 10 a a 样例输出 AC 数据规模 对于 30 的数据 表达式中只可能出现两种运算符 和 对于其它的数据 四种运算符 在表达式中都可能出现 对于全部的数据 表达式中都可能出现小括号 和 18 NOIP2006 1 能量项链 能量项链 energy pas c cpp 问题描述 在 Mars 星球上 每个 Mars 人都随身佩带着一串能量项链 在项链上有 N 颗能量珠 能量珠是一 颗有头标记与尾标记的珠子 这些标记对应着某个正整数 并且 对于相邻的两颗珠子 前一颗珠子的 尾标记一定等于后一颗珠子的头标记 因为只有这样 通过吸盘 吸盘是 Mars 人吸收能量的一种器官 的作用 这两颗珠子才能聚合成一颗珠子 同时释放出可以被吸盘吸收的能量 如果前一颗能量珠的头 标记为 m 尾标记为 r 后一颗能量珠的头标记为 r 尾标记为 n 则聚合后释放的能量为 Mars 单位 新产生的珠子的头标记为 m 尾标记为 n 需要时 Mars 人就用吸盘夹住相邻的两颗珠子 通过聚合得到能量 直到项链上只剩下一颗珠子 为止 显然 不同的聚合顺序得到的总能量是不同的 请你设计一个聚合顺序 使一串项链释放出的总 能量最大 例如 设 N 4 4 颗珠子的头标记与尾标记依次为 2 3 3 5 5 10 10 2 我们用记号 表示两颗珠子的聚合操作 j k 表示第 j k 两颗珠子聚合后所释放的能量 则第 4 1 两颗珠子 聚合后释放的能量为 4 1 10 2 3 60 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 4 1 2 3 10 2 3 10 3 5 10 5 10 710 输入文件 输入文件 energy in 的第一行是一个正整数 N 4 N 100 表示项链上珠子的个数 第二行 是 N 个用空格隔开的正整数 所有的数均不超过 1000 第i 个数为第 i 颗珠子的头标记 1 i N 当 i N时 第i 颗珠子的尾标记应该等于第 i 1 颗珠子的头标记 第 N 颗珠子的尾标记应该等 于第 1 颗珠子的头标记 至于珠子的顺序 你可以这样确定 将项链放到桌面上 不要出现交叉 随意指定第一颗珠子 然 后按顺时针方向确定其他珠子的顺序 输出文件 输出文件 energy out 只有一行 是一个正整数 E E 2 1 109 为一个最优聚合顺序所释放 的总能量 输入样例 4 23510 输出样例 710 19 2 金明的预算方案 金明的预算方案 budget pas c cpp 问题描述 金明今天很开心 家里购置的新房就要领钥匙了 新房里有一间金明自己专用的很宽敞的房间 更 让他高兴的是 妈妈昨天对他说 你的房间需要购买哪些物品 怎么布置 你说了算 只要不超过 N 元钱就行 今天一早 金明就开始做预算了 他把想买的物品分为两类 主件与附件 附件是从属于 某个主件的 下表就是一些主件与附件的例子 如果要买归类为附件的物品 必须先买该附件所属的主件 每个主件可以有 0 个 1 个或 2 个附件 附件不再有从属于自己的附件 金明想买的东西很多 肯定会超过妈妈限定的 N 元 于是 他把每件物 品规定了一个重要度 分为 5 等 用整数 1 5 表示 第 5 等最重要 他还从因特网上查到了每件物品 的价格 都是 10 元的整数倍 他希望在不超过 N 元 可以等于 N 元 的前提下 使每件物品的价格 与重要度的乘积的总和最大 设第 j 件物品的价格为 v j 重要度为 w j 共选中了 k 件物品 编号依次为 j1 j2 jk 则所求的总和为 v j1 w j1 v j2 w j2 v jk w jk 其中 为乘号 请你帮助金明设计一个满足要求的购物单 输入文件 输入文件 budget in 的第 1 行 为两个正整数 用一个空格隔开 N m 其中 N 32000 表示总钱数 m 60 为希望购买物品的个数 从第 2 行到第 m 1 行 第 j 行给出了编号为 j 1 的物品的基本数据 每行有 3 个非负整数 V p q 其中 v 表示该物品的价格 v0 表示该物品为附件 q 是所属主件的编号 输出文件 输出文件 budget out 只有一个正整数 为不超过总钱数的物品的价格与重要度乘积的总和的最大值 200000 输入样例 10005 80020 40051 30051 40030 50020 输出样例 2200 主件附件 电脑打印机 扫描仪 书柜图书 书桌台灯 文具 工作椅无 20 3 作业调度方案 作业调度方案 jsp pas c cpp 问题描述 我们现在要利用 m 台机器加工 n 个工件 每个工件都有 m 道工序 每道工序都在不同的指定的机器 上完成 每个工件的每道工序都有指定的加工时间 每个工件的每个工序称为一个操作 我们用记号 j k 表示一个操作 其中 j 为 1 到 n 中的某个数 字 为工件号 k 为 1 到 m 中的某个数字 为工序号 例如 2 4 表示第 2 个工件第 4 道工序的这个操 作 在本题中 我们还给定对于各操作的一个安排顺序 例如 当 n 3 m 2 时 1 1 1 2 2 1 3 1 3 2 2 2 就是一个给定的安排顺序 即先 安排第 1 个工件的第 1 个工序 再安排第 1 个工件的第 2 个工序 然后再安排第 2 个工件的第 1 个工 序 等等 一方面 每个操作的安排都要满足以下的两个约束条件 1 对同一个工件 每道工序必须在它前面的工序完成后才能开始 2 同一时刻每一台机器至多只能加工一个工件 另一方面 在安排后面的操作时 不能改动前面已安排的操作的工作状态 由于同一工件都是按工序的顺序安排的 因此 只按原顺序给出工件号 仍可得到同样的安排顺序 于是 在输入数据中 我们将这个安排顺序简写为 112332 还要注意 安排顺序 只要求按照给定的顺序安排每个操作 不一定是各机器上的实际操作顺序 在具体实施时 有可能排在后面 的某个操作比前面的某个操作先完成 例如 取 n 3 m 2 已知数据 如下 则对于安排顺序 1 1 2 3 3 2 下图中的两个实施方案都是正确的 但 所需要的总时间分别是 10 与 12 当一个操作插入到某台机器的