2024年3月7日发(作者：)
NOIP2013复赛普及组试题
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
CCF全国信息学奥林匹克联赛（NOIP2013）复赛
普及组
（请选手务必仔细阅读本页内容）
一．题目概况
中文计数问题 表达式小朋友的 车站分题目名称
英文题目与子目录名
可执行文件名
count
expr number
level
count
expr number
level
求值 数字 级
第 2 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
第 3 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
第 4 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
对于
C 语言
count.c expr.c number.c level.c
对于
pascal
语言
三．编译命令（不包含任何优化开关）
g++ -o g++ -o g++ -o g++ -o
count expr number level
C++
语言
-lm
–lm
-lm -lm
gcc -o
对于
gcc -o gcc -o gcc-o
count expr number level
C 语count.c expr.c number.c level.c
-lm -lm -lm
-lm
言
对于
对于
pascal
语言
fpc fpc fpc fpc
第 5 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
注意事项：
1、
文件名（程序名和输入输出文件名）必须使用英文小写。
2、
C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、
全国统一评测时采用的机器配置为：CPU AMD
Athlon(tm) 64x2 Dual Core CPU 5200+，
2.71GHz，内存 2G，上述时限以此配置为准。
4、
只提供 Linux 格式附加样例文件。
特别提醒：评测在 NOI Linux 下进行。
5、
1． 记数问题
(/c/pas)
【问题描述】
试计算在区间 1 到 n 的所有整数中，数字 x（0 ≤ x ≤ 9）共出现了多少次？例如，在 1 到 11
中，即在 1、2、3、4、5、6、7、8、9、10、11
中，数字 1 出现了 4 次。
第 6 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
【输入】
输入文件名为 。
输入共 1 行，包含 2 个整数 n、x，之间用一个空格隔开。
【输出】
输出文件名为 。
输出共 1 行，包含一个整数，表示 x 出现的次数。
【输入输出样例】
11 1
【数据说明】
对于 100%的数据，1≤ n ≤ 1,000,000，0 ≤ x ≤
9。
第 7 页共 18 页
4
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
2． 表达式求值
(/c/pas)
【问题描述】
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
【输入】
输入文件为 。
输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为 0
到 231-1 之间的整数。输入数据保证这一行只有
0~ 9、+、*这 12 种字符。
第 8 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
【输出】
输出文件名为 。
输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于 4 位时，请只输出最后 4 位，前导 0 不输出。
【输入输出样例 1】
1+1*3+4
【输入输出样例 2】
1+1234567890*1
7891
8
第 9 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
【输入输出样例 3】
1+1000000003*1
4
【输入输出样例说明】
样例 1 计算的结果为 8，直接输出 8。
样例 2 计算的结果为 1234567891，输出后 4
位，即 7891。
样例 3 计算的结果为 1000000004，输出后 4
位，即 4。
【数据范围】对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
第 10 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。
3． 小朋友的数字
(/c/pas)
【问题描述】
有 n 个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面（包括他本人）的小朋友中连续若干个（最少有一个）小朋友手上的数字之和的最大值。
作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。
第 11 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
请计算所有小朋友分数的最大值，输出时保持最大值的符号，将其绝对值对 p 取模后输出。
【输入】
输入文件为 。
第一行包含两个正整数 n、p，之间用一个空格隔开。
第二行包含 n 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。【输出】
输出文件名为 。
输出只有一行，包含一个整数，表示最大分数对 p 取模的结果。
【输入输出样例 1】
5 997
1 2 3 4 5
21
【输入输出样例说明】
第 12 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
小朋友的特征值分别为 1、3、6、10、15，分数分别为 1、2、5、11、21，最大值 21 对997的模是21。
【输入输出样例 2】
5 7
-1 -1 -1 -1 -1
-1
【输入输出样例说明】
小朋友的特征值分别为-1、-1、-1、-1、-1，分数分别为-1、-2、-2、-2、-2，最大值
-1对7的模为-1，输出-1。
【数据范围】对于 50%的数据，1 ≤ n ≤
1,000，1 ≤ p ≤ 1,000所有数字的绝对值不超过 1000；
第 13 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
对于 100%的数据，1 ≤ n ≤ 1,000,000，1 ≤ p ≤
109，其他数字的绝对值均不超过 109。
4． 车站分级
(/c/pas)
【问题描述】
一条单向的铁路线上，依次有编号为 1, 2, …,
n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大第 14 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是 5 趟车次的运行情况。其中，前
4 趟车次均满足要求，而第 5 趟车次由于停靠了
3 号火车站（2 级）却未停靠途经的 6 号火车站（亦为 2 级）而不满足要求。
车1
2
3
4
5
6
7
8
9
站编号
车站级3
1
2
1
3
2
1
1
3
别车第 15 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
次
1
始→→→停→→→停→终
2
始→→→停→终
3
始→→→→→→→停→→→→→→→终
4
始→停→停→停→停→终
5
始→→→停→→→→→→→终
现有 m 趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的级别。
【输入】
第 16 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
输入文件为 。
第一行包含 2 个正整数 n, m，用一个空格隔开。
第 i + 1 行（1 ≤ i ≤ m）中，首先是一个正整数
si（2 ≤ si ≤ n），表示第 i 趟车次有 si
个停靠站；接下来有 si
个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
【输出】
输出文件为 。
输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。
【输入输出样例】
第 17 页共 18 页
全国信息学奥林匹克联赛（NOIP2013）复赛 普及组
9 2
4 1 3 5 6
3 3 5 6
9 3
4 1 3 5 6
3 3 5 6
3 1 5 9
【数据范围】
对于 20%的数据，1
≤ n, m ≤ 10；对于
50%的数据，1 ≤ n,
m ≤ 100；
2
3
对于 100%的数据，1 ≤ n, m ≤ 1000。
第 18 页共 18 页
发布评论