全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day1
CCF全国信息学奥林匹克联赛（NOIP2018）复赛
提高组 day1
（请选手务必仔细阅读本页内容）
一．题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限
铺设道路 货币系统 赛道修建 money road track road money track road.in money.in track.in road.out money.out track.out 1s 1s 1s 10 20 20 10 5 5 有 有 有 全文比较（过滤行末空格及文末回车） 传统 传统 传统 512M 512M 512M 二．提交源程序文件名 对于C++语言 对于C语言 对于pascal语言
road.cpp road.c road.pas money.cpp money.c money.pas track.cpp track.c track.pas 三．编译命令（不包含任何优化开关） 对于C++语言 对于C语言 对于pascal语言 g++ -o road road.cpp -lm gcc -o road road.c -lm fpc road.pas g++ -o money money.cpp -lm gcc -o money money.c -lm fpc money.pas g++ -o track track.cpp -lm gcc -o track track.c -lm fpc track.pas 注意事项：
1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存32GB。上述时限以此配置为准。 4、只提供Linux格式附加样例文件。
5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。
第1页共7页
全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day1
1．铺设道路
(road.cpp/c/pas)
【问题描述】
春春是一名道路工程师，负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域，一开始，第 i 块区域下陷的深度为 di 。
春春每天可以选择一段连续区间 [L,R] ，填充这段区间中的每块区域，让其下陷深度减少1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0 。 春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。
【输入格式】
输入文件名为road.in。
输入文件包含两行，第一行包含一个整数 n，表示道路的长度。
第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数为 di 。
【输出格式】
输出文件名为road.out。
输出文件仅包含一个整数，即最少需要多少天才能完成任务。
【输入输出样例1】 road.in road.out 6 9 4 3 2 5 3 5 见选手目录下的road/road1.in和road/road1.ans。
【样例解释】
一种可行的最佳方案是，依次选择：
[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。 【输入输出样例2】
见选手目录下的road/road2.in和road/road2.ans。
【数据规模与约定】
对于 30% 的数据，1≤??≤10 ； 对于 70% 的数据，1≤??≤1000 ；
对于 100% 的数据，1≤??≤100000 ，0≤di≤10000 。
第2页共7页
全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day1
2．货币系统
(money.cpp/c/pas)
【问题描述】
在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。
在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 m。
【输入格式】
输入文件名为money.in。
输入文件的第一行包含一个整数 T，表示数据的组数。接下来按照如下格式分别给出T组数据。
每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数 a[i]。
【输出格式】
输出文件名为money.out。
输出文件共有T行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。
【输入输出样例1】 money.in money.out 2 2 4 5 3 19 10 6 5 11 29 13 19 17 见选手目录下的money/money1.in和money/money1.ans。 【输入输出样例1说明】
在第一组数据中，货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价，并可以验证不存在 m < 2 的等价的货币系统，因此答案为 2。
在第二组数据中，可以验证不存在 m < n 的等价的货币系统，因此答案为 5。
第3页共7页
全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day1
【输入输出样例2】
见选手目录下的money/money2.in和money/money2.ans。 【数据规模与约定】 测试点 测试点 ?? ???? ?? ???? 1 11 2 12 =2 ≤13 ≤16 3 13 4 14 5 15 =3 ≤25 ≤40 ≤1000 6 16 7 17 =4 8 18 ≤100 ≤25000 9 19 =5 10 20 对于 100% 的数据，满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。
第4页共7页
全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day1
3. 赛道修建
（track.cpp/c/pas)
【问题描述】
C城将要举办一系列的赛车比赛。在比赛前，需要在城内修建 ?? 条赛道。
C城一共有 ?? 个路口，这些路口编号为 1,2,…,??，有 ???1 条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 ?? 条道路连接的两个路口编号为 ???? 和 ????，该道路的长度为 ????。借助这 ???1 条道路，从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 ??1,??2,…,????，满足可以从某个路口出发，依次经过道路 ??1,??2,…,????（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的??条赛道中长度最小的赛道长度最大（即??条赛道中最短赛道的长度尽可能大）。 【输入格式】
输入文件名为track.in。
输入文件第一行包含两个由空格分隔的正整数 ??,??，分别表示路口数及需要修建的赛道数。
接下来 ???1 行，第 ?? 行包含三个正整数 ????,????,????，表示第 ?? 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 ???1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。 【输出格式】
输出文件名为track.out。
输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。
【输入输出样例1】 track.in track.out 7 1 31 1 2 10 1 3 5 2 4 9 2 5 8 3 6 6 3 7 7 见选手目录下的track/track1.in与track/track1.ans。 【输入输出样例1说明】
所有路口及适合于修建赛道的道路如下图所示：
第5页共7页
NOIP 复赛提高组Day 试题
