资源描述：
《NOIP2018复赛提高组Day1试题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1CCF全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1（请选手务必仔细阅读本页内容）一．题目概况中文题目名称铺设道路货币系统赛道修建英文题目与子目录名roadmoneytrack可执行文件名roadmoneytrack输入文件名road.inmoney.intrack.in输出文件名road.outmoney.outtrack.out每个测试点时限1s1s1s测试点数目102020每个测试点分值1055附加样例文件有有有结果
2、比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统运行内存上限512M512M512M二．提交源程序文件名对于C++语言road.cppmoney.cpptrack.cpp对于C语言road.cmoney.ctrack.c对于pascal语言road.pasmoney.pastrack.pas三．编译命令（不包含任何优化开关）对于C++语言g++-oroadg++-omoneyg++-otrackroad.cpp-lmmoney.cpp-lmtrack.cpp-lm对于C语言gcc-
3、oroadroad.cgcc-omoneygcc-otracktrack.c-lmmoney.c-lm-lm对于pascal语言fpcroad.pasfpcmoney.pasfpctrack.pas注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、全国统一评测时采用的机器配置为：Intel(R)Core(TM)i7-8700KCPU@3.70GHz，内存32GB。上述时限以此配置为准。4、
4、只提供Linux格式附加样例文件。5、特别提醒：评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。第1页共7页全国信息学奥林匹克联赛（NOIP2018）复赛提高组day11．铺设道路(road.cpp/c/pas)【问题描述】春春是一名道路工程师，负责铺设一条长度为n的道路。铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n块首尾相连的区域，一开始，第i块区域下陷的深度为di。春春每天可以选择一段连续区间[L,R]，填充这段区间中的每块区域，让其下陷深度减少1。在选择
5、区间时，需要保证，区间内的每块区域在填充前下陷深度均不为0。春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为0。【输入格式】输入文件名为road.in。输入文件包含两行，第一行包含一个整数n，表示道路的长度。第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为di。【输出格式】输出文件名为road.out。输出文件仅包含一个整数，即最少需要多少天才能完成任务。【输入输出样例1】road.inroad.out69432535见选手目录下的road/road1.in和
6、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）复赛提高组day12．货
7、币系统(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,
8、9]中，金额1,3就无法被表示出来。两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b)与原来的货币系统(n,a)等价，且m尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。【输入格式】输入文件名为money.in。输入文件的第一行包含一个整数T，表示数据的组数。接下来按照如下格式分别给出T组数据。每组数据的第一行包含一个正
