当前位置:首页 >> 学科竞赛 >>

NOIP提高组复赛题目


第一题题库

NOIP2007
1.统计数字
(count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数,每个数均不超过 1500000000(1.5*109) 。已知不相 同的数不超过 10000 个, 现在需要统计这些自然数各自出现的次数, 并按照自然数从小到大 的顺序输出统计结果。 【输入】 输入文件 co

unt.in 包含 n+1 行: 第 1 行是整数 n,表示自然数的个数。 第 2~n+1 行每行一个自然数。 【输出】 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数) ,按照自然数从 小到大的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格 隔开。

【输入输出样例】 count.in 8 2 4 2 4 5 100 2 100

count.out 2 3 4 2 5 1 100 2

【限制】 40%的数据满足:1<=n<=1000 80%的数据满足:1<=n<=50000 100%的数据满足:1<=n<=200000,每个数均不超过 1 500 000 000(1.5*109) NOIP2008

1. 笨小猴
(wird.pas/c/cpp)
【问题描述】 笨小猴的词汇量很小, 所以每次做英语选择题的时候都很头疼。 但是他找到了一种方法, 经试验证明,用这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn 是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认 为这是个 Lucky Word,这样的单词很可能就是正确的答案。 【输入】 输入文件 word.in 只有一行, 是一个单词, 其中只可能出现小写字母, 并且长度小于 100。 【输出】 输出文件 word.out 共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word, 那么输出“Lucky Word” ,否则输出“No Answer” ; 第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。

【输入输出样例 1】
word.in error word.out Lucky Word 2

【输入输出样例 1 解释】 单词 error 中出现最多的字母 r 出现了 3 次,出现次数最少的字母出现了 1 次,3-1=2,2 是 质数。

【输入输出样例 2】
word.in Olympic word.out No Answer 0

【输入输出样例 2 解释】 单词 olympic 中出现最多的字母 i 出现了 2 次,出现次数最少的字母出现了 1 次,2-1=1,1 不是质数。

NOIP2009

1.潜伏者 (spy.pas/c/cpp)
【问题描述】 R 国和S 国正陷入战火之中,双方都互派间谍,潜入对方内部,伺机行动。 历经艰险后,潜伏于S 国的R 国间谍小C 终于摸清了S 国军用密码的编码规则: (1)S 国军方内部欲发送的原信息经过加密后在网络上发送,原信息的内容与加密后所的内 容均由大 写字母‘A’—‘Z’构成(无空格等其他字母)。 (2)S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换 为其对应的 “密字”。 (3)每个字母只对应一个唯一的“密字”,不同的字母对应不同的“密字”。“密字”可以 和原字母相 同。 例如,若规定‘A’的密字为‘A’,‘B’的密字为‘C’(其他字母及密字略),则原信 息“ABA” 被加密为“ACA”。 现在,小C 通过内线掌握了S 国网络上发送的一条加密信息及其对应的原信息。小C 希望 能通过这 条信息,破译S 国的军用密码。小C 的破译过程是这样的:扫描原信息,对于原信息中的 字母x(代表 任一大写字母),找到其在加密信息中的对应大写字母y,并认为在密码里y 是x 的密字。 如此进行下去 直到停止于如下的某个状态: 1、所有信息扫描完毕,‘A’—‘Z’所有26 个字母在原信息中均出现过并获得了相应的 “密字”。 2、所有信息扫描完毕,但发现存在某个(或某些)字母在原信息中没有出现。 3、扫描中发现掌握的信息里有明显的自相矛盾或错误(违反S 过密码的编码规则)。例如 某条信 息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。 在小C 忙得头昏脑胀之际,R 国司令部又发来电报,要求他翻译另外一条从S 国刚刚截取 到的加密

信息。现在请你帮助小C:通过内线掌握的信息,尝试破译密码。然后利用破译的密码,翻 译电报中的 加密信息。 【输入】输入文件名为spy.in,共3 行,每行为一个长度在1 到100 之间的字符串。 第1 行为小C 掌握的一条加密信息。 第2 行为第1 行的加密信息所对应的原信息。 第3 行为R 国司令部要求小C 翻译的加密信息。 输入数据保证所有字符串仅由大写字母‘A’—‘Z’构成,且第1 行长度与第2 行相等。 【输出】若破译密码停止时出现2,3 两种情况,请你输出“Failed”(不含引号,注意首字 母大写,其它小写)。否则请输出利用密码翻译电报中加密信息后得到的原信息。

提高 问题描述

NOIP2000

题二

乘积最大

(22 分)

今年是国际数学联盟确定的“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 设计一个程序,求得正确的答案。 输 入

程序的输入共有两行: 第一行共有 2 个自然数 N,K(6≤N≤40,1≤K≤6) 第二行是一个长度为 N 的数字串。





结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数) 。 样 输入 4 2 1231 输出 62 例

NOIP2003 题二

侦探推理

【问题描述】 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学 玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明 明不知情的情况下) ,明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被 询问者可能会说:

证词中出现的其他话,都不列入逻辑推理的内容。 明明所知道的是,他的同学中有 N 个人始终说假话,其余的人始终说真。 现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一 个! 【输入格式】 输入由若干行组成,第一行有二个整数,M(1≤M≤20) 、N(1≤N≤M)和 P(1≤P≤100) ; M 是参加游戏的明明的同学数,N 是其中始终说谎的人数,P 是证言的总数。接下来 M 行, 每行是明明的一个同学的名字(英文字母组成,没有主格,全部大写) 。 往后有 P 行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是一句 证词,符合前表中所列格式。证词每行不会超过 250 个字符。 输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。 【输出格式】 如果你的程序能确定谁是罪犯,则输出他的名字;如果程序判断出不止一个人可能是 罪犯, 则输出 Cannot Determine; 如果程序判断出没有人可能成为罪犯, 则输出 Impossible。 【输入样例】 315 MIKE CHARLES KATE MIKE:I am guilty. MIKE:Today is Sunday. CHARLES:MIKE is guilty. KATE:I am guilty. KATE:How are you?? 【输出样例】 MIKE

NOIP2004 二、合并果子 (fruit.pas/dpr/c/cpp) 【问题描述】 在一个果园里, 多多已经将所有的果子打了下来,而且按果子的不同种类分成了 不同的堆。多多决定把所有的果子合成一堆。 每一次合并, 多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量 之和。可以看出,所有的果子经过 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。

NOIP2008 2. 火柴棒等式
(matches.pas/c/cpp)
【问题描述】 给你 n 根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是用 火柴棍拼出的整数(若该数非零,则最高位不能是 0) 。用火柴棍拼数字 0-9 的拼法如图所 示:

注意: 1. 加号与等号各自需要两根火柴棍 2. 如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0) 3. n 根火柴棍必须全部用上 【输入】 输入文件 matches.in 共一行,又一个整数 n(n<=24) 。 【输出】 输出文件 matches.out 共一行,表示能拼成的不同等式的数目。

【输入输出样例 1】
matches.in 14 【输入输出样例 1 解释】 2 个等式为 0+1=1 和 1+0=1。 matches.out 2

【输入输出样例 2】
matches.in 18 【输入输出样例 2 解释】 9 个等式为: 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11 matches.out 9

NOIP2009

Hankson 的趣味题

Hanks 博士是 BT (Bio-Tech,生物技术) 领域的知名专家,他的儿子名叫 Hankson。现在,刚刚放学回家的 Hankson 正在思考一个有趣的问题。 今天在课堂上,老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小 公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识,他开始思考一个 “求公约数”和“求公倍数”之类问题的“逆问题” ,这个问题是这样的:已 知正整数 a0,a1,b0,b1,设某未知正整数 x 满足: 1. x 和 a0 的最大公约数是 a1; 2. x 和 b0 的最小公倍数是 b1。 Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后,他发 现这样的 x 并不唯一,甚至可能不存在。因此他转而开始考虑如何求解满足条 件的 x 的个数。请你帮助他编程求解这个问题。 Input 第一行为一个正整数 n,表示有 n 组输入数据。接下来的 n 行每行一 组输入数据,为四个正整数 a0,a1,b0,b1,每两个整数之间用一个空格隔开。 输入数据保证 a0 能被 a1 整除,b1 能被 b0 整除。 Output 共 n 行。每组输入 数据的输出结果占一行,为一个整数。 对于每组数据:若不存在这样的 x,请输出 0; 若存在这样的 x,请输出满足 条件的 x 的个数; Sample Input 241 1 96 28895 1 37 1776 Sample Output 62 Hint 第一组输入数据,x 可以是 9、18、36、72、144、288,共有 6 个。 第二组输入数据,x 可以是 48、1776,共有 2 个。

对于 50%的数据,保证有 1≤a0,a1,b0,b1≤10000 且 n≤100。 对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000 且 n≤2000。

NOIP 2003 题三

加分二叉树

【问题描述】 设一个 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)tree 的前序遍历

【输入格式】 第 1 行:一个整数 n(n<30) ,为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数<100) 。 【输出格式】 第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000) 。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 31245

NOIP2007 3. 矩阵取数游戏
(game.pas/c/cpp) 【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元 素 aij 均为非负整数。游戏规则如下: 1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素; 2. 每次取走的各个元素只能是该元素所在行的行首或行尾; 3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素 值*2i,其中 i 表示第 i 次取数(从 1 开始编号) ; 4. 游戏结束总得分为 m 次取数得分之和。 帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。 【输入】 输入文件 game.in 包括 n+1 行: 第 1 行为两个用空格隔开的整数 n 和 m。 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。 【输出】 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。 【输入输出样例 1】 game.in 2 3 1 2 3 3 4 2

game.out 82

【输入输出样例 1 解释】 第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1*21+2*21=6 第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20

第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=82 【输入输出样例 2】 game.in 1 4 4 5 0 5 【输入输出样例 3】 game.in 2 10 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67

game.out 122

game.out 316994

【限制】 60%的数据满足:1<=n, m<=30, 答案不超过 1016 100%的数据满足:1<=n, m<=80, 0<=aij<=1000

NOIP2004 四、虫食算 (alpha.pas/dpr/c/cpp) 【问题描述】 所谓虫食算, 就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数 字来判定被啃掉的字母。来看一个简单的例子:

其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数 字分别是 5 和 3,第二行的数字是 5。 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算。这里的加法是 N 进制加法,算式中三个数都有 N 位,允许有前导的 0。 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同的 数字用相同的字母表示, 不同的数字用不同的字母表示。如果这个算式是 N 进制 的,我们就取英文字母表午的前 N 个大写字母来表示这个算式中的 0 到 N-1 这 N 个不同的数字: 但是这 N 个字母并不一定顺序地代表 0 到 N-1)。输入数据保证 N 个字母分别至少出现一次。

上面的算式是一个 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; 对于全部的数据,保证有 N<=26。

NOIP 2008 4. 双栈排序
(twostack.pas/c/cpp)
【问题描述】 Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 S1 和 S2,Tom 希望借助 以下 4 种操作实现将输入序列升序排序。 操作 a 如果输入序列不为空,将第一个元素压入栈 S1 操作 b 如果栈 S1 不为空,将 S1 栈顶元素弹出至输出 序列 操作 c 如果输入序列不为空,将第一个元素压入栈 S2 操作 d 如果栈 S2 不为空,将 S2 栈顶元素弹出至输出 序列 如果一个 1~n 的排列 P 可以通过一系列操作使 得输出序列为 1,2,?,(n-1),n,Tom 就称 P 是一个“可双栈排序排列” 。例如(1,3,2,4) 就是一个“可双栈排序序列” ,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列: <a,c,c,b,a,d,d,b>

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个 可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。 【输入】 输入文件 twostack.in 的第一行是一个整数 n。 第二行有 n 个用空格隔开的正整数,构成一个 1~n 的排列。 【输出】 输出文件 twostack.out 共一行,如果输入的排列不是“可双栈排序排列” ,输出数字 0; 否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

【输入输出样例 1】
twostack.in 4 1324 twostack.out abaabbab

【输入输出样例 2】
twostack.in 4 2341 twostack.out 0

【输入输出样例 3】
twostack.in 3 231 【限制】 30%的数据满足: n<=10 50%的数据满足: n<=50 100%的数据满足: n<=1000 twostack.out acabbd


相关文章:
NOIP2014提高组复赛试题day1+day2
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2015提高组复赛试题Day1
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2015提高组解题报告
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2015提高组复赛试题... 6页 免费 NOIP2015提高组 6页 1下载券 NOIP2015...
NOIP历年复赛提高组试题(2004-2013)
2004~2013 年 NOIP 复赛试题集(提高组) 第十届全国信息学奥林匹克分区联赛(NOIP2004)复赛试题(提高组 竞赛用时:3 小时) 1、津津的储蓄计划(Save.pas/dpr/c...
NOIP2015提高组复赛试题Day2
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day2 (请选手务必仔细阅读本页内容)一.题目概况中文题目...
NOIP2014提高组复赛试题(C语言版)
NOIP2014提高组复赛试题(C语言版)_其它课程_高中教育_教育专区。NOIP2014提高组复赛试题 C语言CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务...
NOIP2013提高组复赛试题
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...
noip2015提高组复赛试题答案
noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。noip2015 提高组复赛试题答案一. 单项选择题 (共 20 题,每题 1.5 分,共计 30 分;每题有且仅...
更多相关标签:
noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2012提高组复赛 | noip2013提高组复赛 | noip提高组复赛 | noip2011提高组复赛 |