搜索
全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第1页共7页CCF全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1（请选手务必仔细阅读本页内容）一．题目概况中文题目名称铺设道路货币系统赛道修建英文题目与子目录名roadmoneytrack可执行文件名roadmoneytrack输入文件名road.inmoney.intrack.in输出文件名road.outmoney.outtrack.out每个测试点时限1s1s1s测试点数目102020每个测试点分值1055附加样例文件有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统运行内存上限512M512M512M二．提交源程序文件名对于C++语言road.cppmoney.cpptrack.cpp对于C语言road.cmoney.ctrack.c对于pascal语言road.pasmoney.pastrack.pas三．编译命令（不包含任何优化开关）对于C++语言g++-oroadroad.cpp-lmg++-omoneymoney.cpp-lmg++-otracktrack.cpp-lm对于C语言gcc-oroadroad.c-lmgcc-omoneymoney.c-lmgcc-otracktrack.c-lm对于pascal语言fpcroad.pasfpcmoney.pasfpctrack.pas注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、全国统一评测时采用的机器配置为：Intel(R)Core(TM)i7-8700KCPU@3.70GHz，内存32GB。上述时限以此配置为准。4、只提供Linux格式附加样例文件。5、特别提醒：评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第2页共7页1.铺设道路(road.cpp/c/pas)【问题描述】春春是一名道路工程师，负责铺设一条长度为n的道路。铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n块首尾相连的区域，一开始，第i块区域下陷的深度为di。春春每天可以选择一段连续区间[L,R]，填充这段区间中的每块区域，让其下陷深度减少1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为0。春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为0。【输入格式】输入文件名为road.in。输入文件包含两行，第一行包含一个整数n，表示道路的长度。第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为di。【输出格式】输出文件名为road.out。输出文件仅包含一个整数，即最少需要多少天才能完成任务。【输入输出样例1】road.inroad.out64325359见选手目录下的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。全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第3页共7页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.inmoney.out243191065112913191725见选手目录下的money/money1.in和money/money1.ans。【输入输出样例1说明】在第一组数据中，货币系统(2,[3,10])和给出的货币系统(n,a)等价，并可以验证不存在m2的等价的货币系统，因此答案为2。在第二组数据中，可以验证不存在mn的等价的货币系统，因此答案为5。全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第4页共7页【输入输出样例2】见选手目录下的money/money2.in和money/money2.ans。【数据规模与约定】测试点𝑛𝑎𝑖测试点𝑛𝑎𝑖1=2≤100011≤13≤162123134=314≤25≤405156167=417≤100≤250008189=5191020对于100%的数据，满足1≤T≤20,n,a[i]≥1。全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第5页共7页3.赛道修建（track.cpp/c/pas)【问题描述】C城将要举办一系列的赛车比赛。在比赛前，需要在城内修建𝑚条赛道。C城一共有𝑛个路口，这些路口编号为1,2,…,𝑛，有𝑛−1条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第𝑖条道路连接的两个路口编号为𝑎𝑖和𝑏𝑖，该道路的长度为𝑙𝑖。借助这𝑛−1条道路，从任何一个路口出发都能到达其他所有的路口。一条赛道是一组互不相同的道路𝑒1,𝑒2,…,𝑒𝑘，满足可以从某个路口出发，依次经过道路𝑒1,𝑒2,…,𝑒𝑘（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的𝑚条赛道中长度最小的赛道长度最大（即𝑚条赛道中最短赛道的长度尽可能大）。【输入格式】输入文件名为track.in。输入文件第一行包含两个由空格分隔的正整数𝑛,𝑚，分别表示路口数及需要修建的赛道数。接下来𝑛−1行，第𝑖行包含三个正整数𝑎𝑖,𝑏𝑖,𝑙𝑖，表示第𝑖条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这𝑛−1条道路相互到达。每行中相邻两数之间均由一个空格分隔。【输出格式】输出文件名为track.out。输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。【输入输出样例1】track.intrack.out71121013524925836637731见选手目录下的track/track1.in与track/track1.ans。【输入输出样例1说明】所有路口及适合于修建赛道的道路如下图所示：全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第6页共7页道路旁括号内的数字表示道路的编号，非括号内的数字表示道路长度。需要修建1条赛道。可以修建经过第3,1,2,6条道路的赛道（从路口4到路口7），则该赛道的长度为9+10+5+7=31，为所有方案中的最大值。【输入输出样例2】track.intrack.out93126233345451062472984794415见选手目录下的track/track2.in与track/track2.ans。【输入输出样例2说明】所有路口及适合于修建赛道的道路如下图所示：需要修建3条赛道。可以修建如下3条赛道：1.经过第1,6条道路的赛道（从路口1到路口7），长度为6+9=15；2.经过第5,2,3,8条道路的赛道（从路口6到路口9），长度为4+3+5+4=16；3.经过第7,4条道路的赛道（从路口8到路口5），长度为7+10=17。长度最小的赛道长度为15，为所有方案中的最大值。【输入输出样例3】见选手目录下的track/track3.in与track/track3.ans。全国信息学奥林匹克联赛（NOIP2018）复赛提高组day1第7页共7页【数据规模与约定】所有测试数据的范围和特点如下表所示测试点编号𝑛𝑚𝑎𝑖=1𝑏𝑖=𝑎𝑖+1分支不超过31≤5=1否否是2≤10≤𝑛−1是3≤15是否否4≤1,000=1否是5≤30,000是否6否7≤𝑛−1是8≤50,0009≤1,000否是是10≤30,00011≤50,00012≤50否1314≤2001516≤1,00017否18≤30,0001920≤50,000其中，“分支不超过3”的含义为：每个路口至多有3条道路与其相连。对于所有的数据，2≤𝑛≤50,000，1≤𝑚≤𝑛−1，1≤𝑎𝑖,𝑏𝑖≤𝑛，1≤𝑙𝑖≤10,000。