haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

NOIP2013普及组复赛试题

发布时间:2013-11-11 08:04:17  

全国信息学奥林匹克联赛(NOIP2013)复赛 普及组

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

普及组

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

注意事项:

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页共5页

全国信息学奥林匹克联赛(NOIP2013)复赛 普及组

1.记数问题

(count.cpp/c/pas)

【问题描述】 试计算在区间1到n的所有整数中,数字x(0≤x≤9)共出现了多少次?例如,在1到11中,即在1、2、3、4、5、6、7、8、9、10、11中,数字1出现了4次。

【输入】

输入文件名为count.in。

输入共1行,包含2个整数n、x,之间用一个空格隔开。

【输出】

输出文件名为count.out。

输出共1行,包含一个整数,表示x出现的次数。

【数据说明】

对于100%的数据,1≤n≤1,000,000,0≤x≤9。

2.表达式求值

(expr.cpp/c/pas)

【问题描述】

给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。

【输入】

输入文件为expr.in。

输入仅有一行,为需要你计算的表达式,表达式中只包含数字、加法运算符“+”和乘法运算符“*”,且没有括号,所有参与运算的数字均为0到231-1之间的整数。输入数据保证这一行只有0~ 9、+、*这12种字符。

【输出】

输出文件名为expr.out。

输出只有一行,包含一个整数,表示这个表达式的值。注意:当答案长度多于4位时,请只输出最后4位,前导0不输出。

第2页共5页

全国信息学奥林匹克联赛(NOIP2013)复赛 普及组

【输入输出样例1】

【输入输出样例2】

【输入输出样例说明】

样例1计算的结果为8,直接输出8。

样例2计算的结果为1234567891,输出后4位,即7891。

样例3计算的结果为1000000004,输出后4位,即4。

【数据范围】

对于30%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100;

对于80%的数据,0≤表达式中加法运算符和乘法运算符的总数≤1000;

对于100%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100000。

3.小朋友的数字

(number.cpp/c/pas)

【问题描述】

有n个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对p取模后输出。

【输入】

输入文件为number.in。

第一行包含两个正整数n、p,之间用一个空格隔开。

第二行包含n个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。

第3页共5页

全国信息学奥林匹克联赛(NOIP2013)复赛 普及组

【输出】

输出文件名为number.out。

输出只有一行,包含一个整数,表示最大分数对p取模的结果。

小朋友的特征值分别为1、3、6、10、15,分数分别为1、2、5、11、21,最大值21对997的模是21。

小朋友的特征值分别为-1、-1、-1、-1、-1,分数分别为-1、-2、-2、-2、-2,最大值-1对7的模为-1,输出-1。

【数据范围】

对于50%的数据,1≤n≤1,000,1≤p≤1,000所有数字的绝对值不超过1000; 对于100%的数据,1≤n≤1,000,000,1≤p≤109,其他数字的绝对值均不超过109。

4.车站分级

(level.cpp/c/pas)

【问题描述】

一条单向的铁路线上,依次有编号为1, 2, …, n的n个火车站。每个火车站都有一个级别,最低为1级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站x,则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)

例如,下表是5趟车次的运行情况。其中,前4趟车次均满足要求,而第5趟车次由于停靠了3号火车站(2级)却未停靠途经的6号火车站(亦为2级)而不满足要求。

第4页共5页

全国信息学奥林匹克联赛(NOIP2013)复赛 普及组

现有m趟车次的运行情况(全部满足要求),试推算这n个火车站至少分为几个不同的级别。

【输入】

输入文件为level.in。

第一行包含2个正整数n, m,用一个空格隔开。

第i + 1行(1 ≤ i ≤ m)中,首先是一个正整数si(2 ≤ si ≤ n),表示第i趟车次有si个停靠站;接下来有si个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

【输出】

输出文件为level.out。

输出只有一行,包含一个正整数,即n个火车站最少划分的级别数。

【数据范围】

对于20%的数据,1 ≤ n, m ≤ 10; 对于50%的数据,1 ≤ n, m ≤ 100; 对于100%的数据,1 ≤ n, m ≤ 1000。

第5页共5页

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com