文档库 最新最全的文档下载
当前位置:文档库 › noip2017复赛提高组day1试题

noip2017复赛提高组day1试题

noip2017复赛提高组day1试题
noip2017复赛提高组day1试题

CCF全国信息学奥林匹克联赛(NOIP2017)复赛

提高组 day1

(请选手务必仔细阅读本页内容)

注意事项:

1、文件名(程序名和输入输出文件名)必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz,

内存4G,上述时限以此配置为准。

4、只提供Linux格式附加样例文件。

5、提交的程序代码文件的放置位置请参照各省的具体要求。

6、特别提醒:评测在当前最新公布的NOI Linux下进行,各语言的编译器版本以其为准。

1.小凯的疑惑

(math.cpp/c/pas)

【问题描述】

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。

【输入格式】

输入文件名为math.in。

输入数据仅一行,包含两个正整数a和b,它们之间用一个空格隔开,表示小凯手中金币的面值。

【输出格式】

输出文件名为math.out。

输出文件仅一行,一个正整数N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。

math/math1.in math/math1.ans

【输入输出样例1说明】

小凯手中有面值为3和7的金币无数个,在不找零的前提下无法准确支付价值为1、2、4、5、8、11的物品,其中最贵的物品价值为11,比11贵的物品都能买到,比如:

12 = 3 * 4 + 7 * 0

13 = 3 * 2 + 7 * 1

14 = 3 * 0 + 7 * 2

15 = 3 * 5 + 7 * 0

……

【输入输出样例2】

见选手目录下的math/math2.in和math/math2.ans。

【数据规模与约定】

对于30%的数据: 1 ≤ a,b ≤ 50。

对于60%的数据: 1 ≤ a,b ≤ 10,000。

对于100%的数据:1 ≤ a,b ≤ 1,000,000,000。

2.时间复杂度

(complexity.cpp/c/pas)

【问题描述】

小明正在学习一种新的编程语言A++,刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下:

其中“F i x y”表示新建变量i(变量i不可与未被销毁的变量重名)并初始化为x,然后判断i和y的大小关系,若i小于等于y则进入循环,否则不进入。每次循环结束后i都会被修改成i +1,一旦i大于y终止循环。

x和y 可以是正整数(x和y的大小关系不定)或变量n。n是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于100。

“E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。

注:本题中为了书写方便,在描述复杂度时,使用大写英文字母“O”表示通常意义下“Θ”的概念。

【输入格式】

输入文件名为complexity.in。

输入文件第一行一个正整数t,表示有t(t≤10)个程序需要计算时间复杂度。每个程序我们只需抽取其中“F i x y”和“E”即可计算时间复杂度。注意:循环结构允许嵌套。

接下来每个程序的第一行包含一个正整数L和一个字符串,L代表程序行数,字符串表示这个程序的复杂度,“O(1)”表示常数复杂度,“O(n^w)”表示复杂度为n w,其中w是一个小于100的正整数(输入中不包含引号),输入保证复杂度只有O(1)和O(n^w)两种类型。

接下来L行代表程序中循环结构中的“F i x y”或者“E”。

程序行若以“F”开头,表示进入一个循环,之后有空格分离的三个字符(串)i x y,其中i是一个小写字母(保证不为“n”),表示新建的变量名,x 和y 可能是正整数或n ,已知若为正整数则一定小于100。

程序行若以“E”开头,则表示循环体结束。

【输出格式】

输出文件名为complexity.out。

输出文件共t行,对应输入的t个程序,每行输出“Yes”或“No”或者“ERR”(输出中不包含引号),若程序实际复杂度与输入给出的复杂度一致则输出“Yes”,不一致则输出“No”,若程序有语法错误(其中语法错误只有: ① F 和E 不匹配②新建的变量与已经存在但未被销毁的变量重复两种情况),则输出“ERR”。

注意:即使在程序不会执行的循环体中出现了语法错误也会编译错误,要输出“ERR”。

complexity/complexity1.in和complexity/complexity1.ans。

【输入输出样例1说明】

第一个程序i从1到1是常数复杂度。

第二个程序x从1到n是n的一次方的复杂度。

第三个程序有一个F开启循环却没有E结束,语法错误。

第四个程序二重循环,n的平方的复杂度。

第五个程序两个一重循环,n的一次方的复杂度。

第六个程序第一重循环正常,但第二重循环开始即终止(因为n远大于100,100大于4)。第七个程序第一重循环无法进入,故为常数复杂度。

第八个程序第二重循环中的变量x与第一重循环中的变量重复,出现语法错误②,输出ERR。

【输入输出样例2】

见选手目录下的

complexity/complexity2.in和complexity/complexity2.ans。

【数据规模与约定】

对于30%的数据:不存在语法错误,数据保证小明给出的每个程序的前L/2行一定为以F开头的语句,第L/2+1行至第L行一定为以E开头的语句,L<=10,若x、y均为整数,x 一定小于y,且只有y有可能为n。

对于50%的数据:不存在语法错误,L<=100,且若x、y均为整数,x 一定小于y,且只有y有可能为n。

对于70%的数据:不存在语法错误,L<=100。

对于100%的数据:L<=100。

3. 逛公园

(park.cpp/c/pas)

【问题描述】

策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图,且没有自环和重边。其中1号点是公园的入口,N号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。

策策每天都会去逛公园,他总是从1号点进去,从N号点出来。

策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策还是一个特别热爱学习的好孩子,他不希望每天在逛公园这件事上花费太多的时间。如果1号点到N号点的最短路长为d,那么策策只会喜欢长度不超过d+K的路线。

策策同学想知道总共有多少条满足条件的路线,你能帮帮他吗?

为避免输出过大,答案对P取模。

如果有无穷多条合法的路线,请输出?1。

【输入格式】

输入文件名为park.in。

第一行包含一个整数 T,代表数据组数。

接下来T组数据,对于每组数据:

第一行包含四个整数 N,M,K,P,每两个整数之间用一个空格隔开。

接下来M行,每行三个整数a i,b i,c i,代表编号为a i,b i的点之间有一条权值为 c i的有

向边,每两个整数之间用一个空格隔开。

【输出格式】

输出文件名为park.out。

输出文件包含 T行,每行一个整数代表答案。

见选手目录下的park/park1.in和park/park1.ans。

对于第一组数据,最短路为3。

1 – 5, 1 –

2 – 4 – 5, 1 – 2 –

3 – 5 为3条合法路径。

【输入输出样例2】

见选手目录下的park/park2.in和park/park2.ans。

【数据规模与约定】

对于不同的测试点,我们约定各种参数的规模不会超过如下

对于100%的数据, 1≤P≤109,1≤a i,b i≤N ,0≤c i≤ 1000。

数据保证:至少存在一条合法的路线。

NOIP2014提高组复赛精彩试题(卷)

CCF全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势: 斯波克:《星际迷航》主角之一。 蜥蜴人:《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。 表一石头剪刀布升级版胜负关系 现在,小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定相等。例如:如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”,而如果小B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……” 已知小A和小B一共进行N次猜拳。每一次赢的人得1分,输的得0分;平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。 【输入】 输入文件名为rps.in。 第一行包含三个整数:N,NA,NB,分别表示共进行N次猜拳、小A出拳的周期长度,小B出拳的周期长度。数与数之间以一个空格分隔。 第二行包含NA个整数,表示小A出拳的规律,第三行包含NB个整数,表示小B出拳的规律。其中,0表示“剪刀”,1表示“石头”,2表示“布”,3表示“蜥蜴人”, 4表示“斯波克”。数与数之间以一个空格分隔。

NOIP2017全国青少年信息学奥林匹克联赛提高组初赛试题卷答案解析

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确选项) 1. 从( )年开始,NOIP 竞赛将不再支持 Pascal 语言。 A. 2020 B. 2021 C. 2022 D. 2023 2.在 8 位二进制补码中,10101011 表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D.-84 3.分辨率为 1600x900、16 位色的位图,存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日,1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图,必须删去 G 的( )条边,才能使得 G 变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式: T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。 A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。

A. 32 B. 35 C. 38 D. 41 9. 将7个名额分给4个不同的班级,允许有的班级没有名额,有( )种不同的分配方案。 A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2,则随着i的增大,f[i]将接近与( )。 A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。 A. n2 B. nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把 a-c三行代码补全到算法中。 a. A XUY b. A Z c. n |A| 算法Coin(A,n) 1. k n/3 2. 将A中硬币分成X,Y,Z三个集合,使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较,若不等,则它不合格;若相等,则A 中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。 A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示,第一行的数为a11;第二行的数从左到右依次为a21,a22;…第n行的数为an1,an2,…,ann。从a11开始,每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径,使得该路径上的数之和达到最大。

Noip2001年普及组复赛题目

NOI’2001第七届全国青少年信息学(计算机)奥林匹克分区联 赛复赛试题 普及组 题一数的计算(20分) 问题描述 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理: 1.不作任何处理; 2.在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3.加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例: 输入: 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136 输出: 6 题二最大公约数和最小公倍数问题(20分) 问题描述 输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数 条件: 1.P,A是正整数 2.要求P,Q以x0为最大公约数,以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 样例 输入:x0=3 yo=60 输出:4 说明(不用输出)此时的P Q 分别为: 3 60 15 12 12 15 60 3 所以:满足条件的所有可能的两个正整数的个数共4种. 题三求先序排列(30分) 问题描述 给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不

同的大写字母表示,长度<=8)。 样例 输入:BADC BDCA 输出:ABCD 题四装箱问题(30分) 问题描述 有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n <=30=,每个物品有一个体积(正整数)。 要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。 样例 输入: 24一个整数,表示箱子容量 6一个整数,表示有n个物品 8接下来n行,分别表示这n 个物品的各自体积 3 12 7 9 7 输出: 0一个整数,表示箱子剩余空间。

noip普及组复赛模拟试题18

1. 话说去年苹果们被陶陶摘下来后都很生气,于是就用最先进的克隆技术把陶陶克隆了好多份>.<然后把他们挂在树上,准备摘取。摘取的规则是,一个苹果只能摘一个陶陶,且只能在它所能摘到的高度以下(即是小于关系)的最高的陶陶,如果摘不到的话只能灰溜溜的走开了>.<给出苹果数目及每个苹果可以够到的高度和各个陶陶的高度,求苹果们都摘完后剩下多少个陶陶…… 【输入格式】第一行为两个数,分别为苹果的数量n和陶陶的数量m(n,m<=2000)以下的n行,分别为各个苹果能够到的最大高度。再接下来的m行,分别为各个陶陶的高度。高度均不高于300。 当然了,摘取的顺序按照输入的“苹果够到的最大高度”的顺序来摘。 【输出格式】输出仅有一个数,是剩下的陶陶的数量 【样例输入】5 5↙9↙10↙2↙3↙1↙6↙7↙8↙9↙10 【样例输出】3 2. 某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个学生的排序是唯一确定的。 任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前5名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是:7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和),但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:5 279 7 279则按输出错误处理,不能得分。【输入】输入文件scholar.in包含n+1行: 第1行为一个正整数n,表示该校参加评选的学生人数。 第2到n+1行,每行有3个用空格隔开的数字,每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输入数据的行号减1)。 所给的数据都是正确的,不必检验。 【输出】输出文件scholar.out共有5行,每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。 【输入输出样例1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar.in scholar.out 8 80 89 89 8 265 2 264

NOIP2001提高组初赛试题答案

第七届分区联赛提高组初赛 (提高组PASCAL语言二小时完成) 一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无分,共30分) 1、中央处理器CPU能访问的最大存储器容量取决于( ) A)地址总线B)数据总线C)控制总线 D)内存容量 2、计算机软件保护法是用来保护软件( )的。 A)编写权B)复制权C)使用权D)著作权 3、64KB的存储器用十六进制表示,它的最大的地址码是( ) A)10000 B)FFFF C)1FFFF D)EFFFF 4、在树型目录结构中,不允许两个文件名相同主要指的是( ) A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下 5、下列设备哪一项不是计算机输入设备( ) A)鼠标B)扫描仪C)数字化仪D)绘图仪 6、在计算机硬件系统中,cache是( )存储器 A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲 7、若我们说一个微机的CPU是用的PII300,此处的300确切指的是( ) A)CPU的主时钟频率B)CPU产品的系列号 C)每秒执行300百万条指令D)此种CPU允许最大内存容量 8、Email邮件本质上是一个( ) A)文件B)电报C)电话D)传真 9、2KB的内存能存储( )个汉字的机内码 A)1024 B)516 C)2048 D)218 10、以下对Windows的叙述中,正确的是( ) A)从软盘上删除的文件和文件夹,不送到回收站 B)在同一个文件夹中,可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式,将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 11、运算式(2047)10—(3FF)16+(2000)8的结果是( ) A)(2048)10B)(2049)10C)(3746)8D)(1AF7)16 12、TCP/IP协议共有( )层协议 A)3 B)4 C)5 D)6 13.若已知一个栈的入栈顺序是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1是n,则Pi是( ) A)i B)n-1 C)n-i+1 D)不确定 14.计算机病毒是( ) A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 15.下面关于算法的错误说法是( ) A)算法必须有输出B)算法必须在计算机上用某种语言实现

NOIP2002普及组(复赛)

2002年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (普及组竞赛用时:3 小时) 题一级数求和(存盘名:NOIPC1) [问题描述]: 已知:Sn= 1+1/2+1/3+…+1/n。显然对于任意一个整数K,当n足够大的时候,Sn大于K。 现给出一个整数K(1<=k<=15),要求计算出一个最小的n;使得Sn>K。 [输入] 键盘输入 k [输出] 屏幕输出 n [输入输出样例] 输人:1 输出:2 题二选数(存盘名:NOIPC2) [问题描述]: 已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。 现在,要求你计算出和为素数共有多少种。 例如上例,只有一种的和为素数:3+7+19=29)。 [输入]: 键盘输入,格式为: n , k (1<=n<=20,k<n) x1,x2,…,xn (1<=xi<=5000000) [输出]: 屏幕输出,格式为: 一个整数(满足条件的种数)。 [输入输出样例]: 输入: 4 3 3 7 12 19 输出: 1

[问题描述]: 给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。 规则: 一位数可变换成另一个一位数: 规则的右部不能为零。 例如:n=234。有规则(k=2): 2-> 5 3-> 6 上面的整数 234 经过变换后可能产生出的整数为(包括原数): 234 534 264 564 共 4 种不同的产生数 问题: 给出一个整数 n 和 k 个规则。 求出: 经过任意次的变换(0次或多次),能产生出多少个不同整数。 仅要求输出个数。 [输入]: 键盘输人,格式为: n k x1 y1 x2 y2 ... ... xn yn [输出]: 屏幕输出,格式为: 一个整数(满足条件的个数): [输入输出样例]: 输入: 234 2 2 5 3 6 输出: 4

NOIP1999普及组(复赛)

第五届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (普及组 竞赛用时:3小时) 第一题 Cantor 表(30分) 现代数学的著名证明之一是Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的: 我们以Z 字形给上表的每一项编号。第一项是1/1,然后是1/2,2/1,3/1,2/2,… 输入:整数N (1≤N ≤10000000) 输出:表中的第N 项 样例: INPUT OUTPUT N=7 1/4 第二题 回文数(30分) 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个10进制数56,将56加56(即把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 第三题 旅行家的预算(40分) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的容量C (以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P 和沿途油站数N (N 可以为零),油站i 离出发点的距离Di 、每升汽油价格Pi (i=1,2,…,N )。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution ”。 样例: INPUT … 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … 3/1 3/2 3/3 … 4/1 4/2 … 5/1 … …

NOIP2008提高组复赛试题及题解

全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 一、题目概览 二、提交源程序文件名 三、编译命令(不包含任何优化开关) 四、运行内存限制 注意事项: 1. 文件名(程序名和输入输出文件名)必须使用大写。 2. C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器配置为:CPU 1.9GHz,内存512M,上述时限以此配置为准。各省在自测时可根据具体配置调整时限。

1. 笨小猴 (word.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】 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次,出现次数最少的字母出现了1次,3-1=2,2是质数。 【输入输出样例2】 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次,出现次数最少的字母出现了1次,2-1=1,1不是质数。 基本的字符串处理,细心一点应该没问题的,不过判断素数时似乎需要考虑下0和1的情况。var a:array['a'..'z']of integer; s:string; l,i,max,min,n:integer; ch:char;flag:boolean; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(s);

NOIP2017普及组初赛试题及答案

NOIP2017普及组初赛试题及答案 一、单项选择题(共20题,每题1.5分,共计30分;每题有且仅有一个正确选项) 1.在8位二进制补码中,10101011表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D. -84 2.计算机存储数据的基本单位是( )。 A. bit B. Byte C. GB D. KB 3.下列协议中与电子邮件无关的是( )。 A. POP3 B. SMTP C. WTO D. IMAP 4.分辨率为800x600、16位色的位图,存储图像信息所需的空间为( )。 A.937.5KB B. 4218.75KB C.4320KB D. 2880KB 5.计算机应用的最早领域是( )。 A.数值计算 B.人工智能 C.机器人 D.过程控制 6.下列不属于面向对象程序设计语言的是( )。 A. C B. C++ C. Java D. C# 7.NOI的中文意思是( )。 A.中国信息学联赛

B.全国青少年信息学奥林匹克竞赛 C.中国青少年信息学奥林匹克竞赛 D.中国计算机协会 8. 2017年10月1日是星期日,1999年10月1日是( )。 A.星期三 B.星期日 C.星期五 D.星期二 9.甲、乙、丙三位同学选修课程,从4门课程中,甲选修2门,乙、丙各选修3门,则不同的选修方案共有( )种。 A. 36 B. 48 C. 96 D. 192 10.设G是有n个结点、m条边(n ≤m)的连通图,必须删去G的( )条边,才能使得G变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 11.对于给定的序列{ak},我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么 序列1, 7, 2, 3, 5, 4的逆序对数为()个。 A. 4 B. 5 C. 6 D. 7 12.表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时,应执行( )。

NOIP2015普及组复赛试题

CCF全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 (请选手务必仔细阅读本页内容) 一、题目概况 中文题目名称金币扫雷游戏求和推销员 coin mine sum salesman 英文题目与子目 录名 可执行文件名coin mine sum salesman 输入文件名coin.in mine.in sum.in salesman.in 输出文件名coin.out mine.out sum.out salesman.out 每个测试点时限1秒 测试点数目10 每个测试点分值10 附加样例文件有 结果比较方式全文比较(过滤行末空格及文末回车) 题目类型传统 运行内存上限128M 二、提交源程序文件名 对于C++语言coin.cpp mine.cpp sum.cpp salesman.cpp 对于C语言coin.c mine.c sum.c salesman.c 对于Pascal语言coin.pas mine.pas sum.pas salesman.pas 四、注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm)II x2240processor,2.8GHz,内存4G,上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒:评测在当前最新公布的NOI Linux下进行,各语言的编译器版本以其为准。

1.金币 (coin.cpp/c/pas) 【问题描述】 国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续N天每天收到N枚金币后,骑士会在之后的连续N+1天里,每天收到N+1枚金币。 请计算在前K天里,骑士一共获得了多少金币。 【输入格式】 输入文件名为coin.in。 输入文件只有1行,包含一个正整数K,表示发放金币的天数。 【输出格式】 输出文件名为coin.out。 输出文件只有1行,包含一个正整数,即骑士收到的金币数。 【输入输出样例1】 coin.in coin.out 614 见选手目录下的coin/coin1.in和coin/coin1.ans。 【输入输出样例1说明】 骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。因此一共收到1+2+2+3+3+3=14枚金币。 【输入输出样例2】 coin.in coin.out 100029820 见选手目录下的coin/coin2.in和coin/coin2.ans。 【数据说明】 对于100%的数据,1≤K≤10,000。

noip2017提高组复赛解题报告

noip2017提高组复赛解题报告 定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,融科教育信息学竞赛培训等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!以下解题思路及代码未经官方评测,仅供参考,复赛成绩以官方(CCF)评测结果为准。 Day1 1.小凯的疑惑(math.cpp/c/pas)【问题描述】小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。【输入格式】输入文件名为math.in。输入数据仅一行,包含两个正整数a 和b,它们之间用一个空格隔开,表示小凯手中金币的面值。【输出格式】输出文件名为math.out。输出文件仅一行,一个正整数N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。【输入输出样例1】math.in3 7 math.out11【数据规模与约定】对于30%的数据: 1 ≤a,b ≤50。对于60%的数据: 1 ≤a,b ≤10,000。对于100%的数据:1 ≤a,b ≤1,000,000,000。数学太差只找规律吧。

设:其中一个数为2则:2、3=>1;2、5=>3;2、7=>5;2、11=>9得:2、n=>n-2设:其中一个数为3则:3、5=>7;3、7=>11;3、11=>19;3、13=>23得:3、n=>2n-3设:其中一个数为5则:5、7=>23;5、11=>39;5、13=>47;5、17=>63得:5、n=>4n-5所以:m、n=>(m-1)n-m #includeusing namespace std;int main(){ long long a,m,n; scanf('%lld %lld',&m,&n); a=(m-1)*n-m; printf('%lld',a); return 0;} 2.时间复杂度(complexity.cpp/c/pas)【问题描述】小明正在学习一种新的编程语言A++,刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。A++语言的循环结构如下:其中“F i x y”表示新建变量(i 变量i 不可与未被销毁的变量重名)并初始化为x,然后判断i 和y 的大小关系,若i 小于等于y 则进入循环,否则不进入。每次循环结束后i都会被修改成i +1,一旦i 大于y 终止循环。x和y 可以是正整数(x 和y 的大小关系不定)或变量n。n 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于100。“E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。注:本题中为了书写方便,在描述复杂度时,使用大

NOIP2013提高组复赛Day2

CCF全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 (请选手务必仔细阅读本页内容) 注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+, 2.71GHz,内存2G,上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒:评测在NOI Linux下进行。

1.积木大赛 (block.cpp/c/pas) 【题目描述】 春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦,大厦可以看成由n块宽度为1的积木组成,第i块积木的最终高度需要是?i。 在搭建开始之前,没有任何积木(可以看成n块高度为0的积木)。接下来每次操作,小朋友们可以选择一段连续区间[L,R],然后将第L块到第R块之间(含第L块和第R块)所有积木的高度分别增加1。 小M是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。 【输入】 输入文件为block.in 输入包含两行,第一行包含一个整数n,表示大厦的宽度。 第二行包含n个整数,第i个整数为?i。 【输出】 输出文件为block.out 仅一行,即建造所需的最少操作数。 【样例解释】 其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】 对于30%的数据,有1≤n≤10; 对于70%的数据,有1≤n≤1000; 对于100%的数据,有1≤n≤100000,0≤?i≤10000。

历年noip初赛普及组试题(完整资料).doc

【最新整理,下载后即可编辑】 历年noip普及组初赛试题汇编 芜湖县实验学校NOIP初赛复习资料

第十五届全国青少年信息学奥林匹克联赛初赛试题(2009) (普及组C++语言二小时完成) ●●全部试题答案均要求写在答卷纸上,写在试卷纸 上一律无效●● 一.单项选择题(共20题,每题1.5分,共计30分。每题有且仅有一个正确答案。) 1、关于图灵机下面的说法哪个是正确的: A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作,图灵机运行速度很慢。 C)图灵机是英国人图灵发明的,在二战中为破译德军的密码 发挥了重要作用。 D)图灵机只是一个理论上的计算模型。 2、关于计算机内存下面的说法哪个是正确的: A)随机存储器(RAM)的意思是当程序运行时,每次具体分 配给程序的内存位置是随机而不确定的。 B)1MB内存通常是指1024*1024字节大小的内存。 C)计算机内存严格说来包括主存(memory)、高速缓存(cache) 和寄存器(register)三个部分。 D)一般内存中的数据即使在断电的情况下也能保留2个小时 以上。 3、关于BIOS下面说法哪个是正确的: A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输 入输出设备的驱动程序。 C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文 件管理功能。 4、关于CPU下面哪个说法是正确的: A)CPU全称为中央处理器(或中央处理单元)。 B)CPU可以直接运行汇编语言。 C)同样主频下,32位的CPU比16位的CPU运行速度快一倍。 D)CPU最早是由Intel公司发明的。 5、关于ASCII,下面哪个说法是正确的: A)ASCII码就是键盘上所有键的唯一编码。 B)一个ASCII码使用一个字节的内存空间就能够存放。 C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的 编码。 D)ASCII码是英国人主持制定并推广使用的。 6、下列软件中不是计算机操作系统的是: A) Windows B) Linux C) OS/2 D) WPS 7、关于互联网,下面的说法哪一个是正确的: A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 B)互联网的入网主机如果有了域名就不再需要IP地址。 C)互联网的基础协议为TCP/IP协议。 D)互联网上所有可下载的软件及数据资源都是可以合法免 费使用的。 8、关于HTML下面哪种说法是正确的: A)HTML实现了文本、图形、声音乃至视频信息的统一编码。 B)HTML全称为超文本标记语言。 C)网上广泛使用的Flash动画都是由HTML编写的。 D)HTML也是一种高级程序设计语言。

noip2017提高组试题

CCF 全国信息学奥林匹克联赛(NOIP2017)复赛 提高组 day1 (请选手务必仔细阅读本页内容) 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz, 内存4G,上述时限以此配置为准。 4、只提供Linux 格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。 6、特别提醒:评测在当前最新公布的NOI Linux 下进行,各语言的编译器版本以其为准。

【问题描述】1.小凯的疑惑 (math.cpp/c/pas) 小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。 【输入格式】 输入文件名为math.in。 输入数据仅一行,包含两个正整数a 和b,它们之间用一个空格隔开,表示小凯手中金币的面值。 【输出格式】 输出文件名为math.out。 输出文件仅一行,一个正整数N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。 见选手目录下的math/math1.in 和math/math1.ans。 【输入输出样例1 说明】 小凯手中有面值为3 和7 的金币无数个,在不找零的前提下无法准确支付价值为1、2、4、5、8、11 的物品,其中最贵的物品价值为11,比11 贵的物品都能买到,比如: 12 = 3 * 4 + 7 * 0 13 = 3 * 2 + 7 * 1 14 = 3 * 0 + 7 * 2 15 = 3 * 5 + 7 * 0 …… 【输入输出样例2】 见选手目录下的math/math2.in 和math/math2.ans。 【数据规模与约定】 对于30%的数据: 1 ≤ a,b ≤ 50。 对于60%的数据: 1 ≤ a,b ≤ 10,000。 对于100%的数据:1 ≤ a,b ≤ 1,000,000,000。

NOIP2002普及组初赛试题及答案

第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题 (普及组PASCAL语言二小时完成) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一.选择一个正确答案代码(A/B/C/D,填入每题的括号内(每题1.5分,多选无分,共30分) 1)微型计算机的问世是由于( ) 的出现。 A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路 2)下列说法中正确的是( ) 。 A) 计算机体积越大,其功能就越强 B) CPU的主频越高,其运行速度越快 C) 两个显示器屏幕大小相同,则它们的分辨率必定相同 D)点阵打印机的针数越多,则能打印的汉字字体越多 3)Windows98中,通过查找命令查找文件时,若输入F*.? , 则下列文件( ) 可以被查到。 A) F.BAS B) FABC.BAS C) F.C D) EF. 4)CPU处理数据的基本单位是字,一个字的字长( ) 。 A) 为8个二进制位 B) 为16个二进制位 C) 为32个二进制位 D) 与芯片的型号有关 5)资源管理器的目录前图标中增加"+"号,这个符号的意思是( ) 。 A) 该目录下的子目录已经展开 B) 该目录下还有子目录未展开 C) 该目录下没有子目录 D) 该目录为空目录, 6)下列哪一种程序设计语言是解释执行的( ) 。 A) Pascal B) GWBASIC C) C++ D) FORTRAN 7)启动WORD的不正确方法是( ) 。 A) 单击Office工具栏上的Word图标 B) 单击"开始"→"程序"→Word C) 单击"开始"→"运行",并输入Word按回车 D) 双击桌面上的"Word快捷图标" 8)多媒体计算机是指( ) 计算机。 A) 专供家庭使用的 B) 装有CDROM的 C) 连接在网络上的高级 D) 具有处理文字、图形、声音、影像等信息的 9)在树型目录结构中,不允许两个文件名相同主要是指( ) 。 A) 同一个磁盘的不同目录下 B) 不同磁盘的同一个目录下 C) 不同磁盘的不同目录下、 D) 同一个磁盘的同一个目录下 10)用画笔(Paintbrush)绘制图形并存储在文件中,该图形文件的文件名缺省的后缀为( ) 。 A) .jpg B) .bmp C) .gif D).tiff t11)E-ml地址中用户名和邮件所在服务器名之间的分隔符号是( ) 。 E A) # B) @ C) & D) $ 12)(0.5)10=( ) 16. A) 0.1 B) 0.75 C) 0.8 D) 0.25

NOIP普及组复赛试题源程序

N O I P2011普及组复赛 1.数字反转(c/pas) 【问题描述】 给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零。(参见样例2) 【输入】 输入文件名为。 输入共一行,一个整数N。 【输出】 输出文件名为。 输出共1行,一个整数,表示反转后的新数。 -1,000,000,000≤N≤1,000,000,000。 【解题】这道题非常简单,可以读字符串处理,也可以读数字来处理,只不过要注意符号问题(以及-0,但测试数据没出)。 【法一】字符串处理 Var i,l,k:integer; s:string; p:boolean; begin assign(input, ''); reset(input); assign(output, ''); rewrite(output); readln(s); l:=length(s); k:=1; if s[1]='-' then begin write('-'); k:=2; end; p:=true;; for i:=l downto k do begin if(p)and((s[i]='0')) then continue else begin write(s[i]); p:=false;; end; end; close(input); close(output); end. 【法二】数字处理 Var f:integer; n,ans:longint; begin assign(input, ''); reset(input);

NOIP2017提高组初赛试题及答案

NOIP2017提高组初赛试题及答案 一、单项选择题(共15 题,每题1.5 分,共计22.5 分;每题有且仅有一个正确选项) 1. 从( )年开始,NOIP 竞赛将不再支持Pascal 语言。C A. 2020 B. 2021 C. 2022 D. 2023 2.在8 位二进制补码中,10101011 表示的数是十进制下的( )。B A. 43 B. -85 C. -43 D.-84 3.分辨率为1600x900、16 位色的位图,存储图像信息所需的空间为( )。A A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日,1949年10月1日是( )。C A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设G 是有n 个结点、m 条边(n ≤m)的连通图,必须删去G 的( )条边,才能使得G 变成一棵树。A A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式:T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。C A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。B A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。C A. 32 B. 35 C. 38D. 41 9. 将7个名额分给4个不同的班级,允许有的班级没有名额,有( )种不同的分配方案。D A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2,则随着i的增大,f[i]将接近与( )。B A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。D A. n2 B. Nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。 2. 将A中硬币分成X,Y,Z三个集合,使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较,若不等,则它不合格;若相等,则A中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。D A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示,第一行的数为a11;第二行的数从左到右依次为a21,a22;…第n行的数为 an1,an2,…,ann。从a11开始,每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径,使得该路径上的数之和达到最大。 令C[i,j]是从a11到aij的路径上的数的最大和,并且C[i,0]=C[0,j]=0,则C[i,j]=( )。A A. max{C[i-1,j-1],C[i-1,j]}+aij B. C[i-1,j-1]+c[i-1,j] C. max{C[i-1,j-1],C[i-1,j]}+1 D. max{C[i,j-1],C[i-1,j]}+aij 14. 小明要去南美洲旅游,一共乘坐三趟航班才能到达目的地,其中第1个航班准点的概率是0.9,第2个航班准点的概率为0.8,第3个航班准点的概率为0.9。如果存在第i个(i=1,2)航班晚点,第i+1个航班准点,则小明将赶不上第i+1个航班,旅行失败;除了这种情况,其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。D

相关文档
相关文档 最新文档