2021年崂山区程序设计竞赛题（初中组）
2021年崂山区程序设计竞赛题（初中组）
（比赛时间90分钟,试题满分300分）
题目名称 | 区间和 | 区间位数的个数 | 有序数组 | |
保存文件 | sum | digit | array | |
输入文件名 | sum.in | digit.in | array.in | |
输出文件名 | sum.out | digit.out | array.out | |
每个测试点时限 | 1秒 | 1秒 | 1秒 | |
测试点数目 | 20 | 20 | 20 | |
每个测试点分值 | 5 | 5 | 5 | |
附加样例文件 | 有 | 有 | 有 | |
结果比较方式 | 全文比较（过滤行末空格及文末回车） | |||
题目类型 | 传统 | 传统 | 传统 | |
运行内存限制 | 128M | 128M | 128M | |
说明：1、须以题目中规定的文件名进行保存，保存到建好的文件夹中，不需要每个题目单独建立文件夹。
2、用上机编程，C++选手，如果尚未掌握文件输入输出，请参考以下我们提供的一种方法进行文件输入输出。在主函数即main()的开始部分加入以下代码:
freopen("输入文件名","r",stdin);
freopen("输出文件名","w",stdout);
1.区间和(sum.cpp)
【描述】
输入一个整数Q，进行Q次询问,每次给定两个整数l和r，每一次输出l～r中所有平方数的和 % 1000000007
【输入】
第一行是一个整数Q
后面的Q行每行有2个数字l和r
【输出】
Q行，每行一个整数。
【样例输入输出】
light.in | light.out |
2 2 10 3 100 | 13 384 |
【数据范围】
40%的数据：Q<=1000,l<=r<=1000。
80%的数据：Q<=1000,l<=r<=1e6。
100%的数据: Q<=1e6,l<=r<=1e6
2.区间数位个数(digit.cpp)
【描述】
给定整数n和整数k,求出1～n中所有数的每一位数字中,出现数字k的次数。
【输入】
第一行是两个个整数n和k
【输出】
一个整数表示答案。
【样例输入输出】
light.in | light.out |
123456 5 | 58993 |
【数据范围】
60%的数据：n<=1e6,1<=k<=9
80%的数据：n<=1e12,1<=k<=9
3.有序数组(array.cpp)
【题目描述】
给定一个数组,其中每个元素均为1-2000之间的正整数，现在可以使用1到2000之间的整数去替换数组中的任意元素，替换完成后新数组构成的序列为不下降序列。要求替换次数尽可能少，如果替换次数相同，输出替换后的数组元素之和最小的方案。
【输入】
第一行为整数n
第二行为n个正整数ai
【输出】
n个正整数,为替换后的数组
【样例输入输出】
array.in | array.out |
3 10 8 7 | 1 1 7 |
【数据范围】
40%的数据：n <= 50
100%的数据： n <= 2000