2022年NOIP模拟试题 .pdf

《2022年NOIP模拟试题 .pdf》由会员分享，可在线阅读，更多相关《2022年NOIP模拟试题 .pdf（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、NOIP 第一题：搬运树苗（ move）输入文件： move.in 输出文件： move.out 【问题描述】Neyc 的绿化工程正在进行，树苗已经被工人送到园区内。设计师希望将树苗种植成一个环形的绿化带，这个绿化带有n 个树苗群， 而每个树苗群有相同数量的树苗。但是在卸放树苗时， 工人虽然按环形排列将树苗放置了n 堆，但是每一个树苗群的树苗数量却没有满足要求。于是，需要从任意一个树苗群中取任意数量的树苗搬运到相邻的树苗群，使得每个树苗群树苗的数量相等。为了节约时间，现在需要找到一种搬运方式：搬运最少的树苗使得每一个树苗群的树苗数目相同。当然，每个树苗群的树苗数量是已知的，分别是m1,m2 .

2、mn，且 S=m1+m2.mn必为 n 的倍数。例如： n=4，每个树苗群的树苗数量分别为17 9 14 16 4，我们进行如下搬运; (1) 树苗群 1 向树苗群2 搬运 1 棵树苗；(2) 树苗群 1 向树苗群5 搬运 4 棵树苗；(3) 树苗群 3 向树苗群2 搬运 2 棵树苗；(4) 树苗群 4 向树苗群5 搬运 4 棵树苗；搬运树苗的总数是1+4+2+4=11，并且可以证明这样的搬运方式是最佳的搬运方法。【输入格式】第一行正整数n（n=10000）,表示有 n 个树苗群；第二行 n 个整数（ integer 范围） ，表示 n 个树苗群的树苗数量。【输出格式】一个正整数，表示最少搬运

3、树苗的数量。【样例输入】5 17 9 14 16 4 【样例输出】11 第二题：电话网络（ phone）输入文件： phone.in 输出文件： phone.out 【题目描述】绿化工程终于完成，整个园区生机勃勃。但是，很不幸的是，在绿化过程中，工人们和进出的车辆将铺设好的电话线全部破坏了。Neyc 的领导很生气，问题很严重。为了保住面子，工程队负责人，希望尽快恢复园区的电信，他把这个任务交给了你。已知，园区周围分布N（1=n=1000 ）根按 1 n 排列的电话线杆，电话线杆之间可以拉电话线。 第 i 对电话线杆的两个端点分别为Ai ， Ri， 它们间的距离为Li（1=li=1000000

4、） 。数据中保证每对最多只出现一次。编号为 1 的电话线杆已经接入了全国的电话网络，整个园区的电话线全部连到了编号为N 的电话线杆上。也就是说，你的任务仅仅是找一条将1 号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 和 N 号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。绿化工程的负责人与电信公司协商后，电信公司决定免费为园区连接K（0=kn）对由你指定的电话线杆。对于此外的那些电话线，就必需为它们付费，总费用

5、等于其中最长的电话线长度（每根电话线仅连接一对电话线杆），其它长度不付费。如果需要连接的电话线杆不超过K 对，那么总支出为0。现在，你就要设计一个费用最少的方案。最后，计算出将电话线引到园区最少需要花多少钱？【输入格式】输入文件的第一行包含三个用空格隔开的整数：N ，P 和 K。第二行到第P+1 行：每行分别都为三个用空格隔开的整数：Ai Bi 和 Li 。【输出格式】输出文件仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出 -1。【样例输入】5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 【样例输出】4 第三题：科研先行（

6、 research ）输入文件：research.in 输出文件：research.out 【问题描述】Neyc 绿化破坏电信事件，给领导层造成了很大的麻烦。为避免类似事件发生，领导意识到，做任何事情，科研必须先行。为此，Neyc 专门成立了研究所，对Neyc 的整体建设进行研究设计。 研究所计划从全国各地邀请相关专家集中研讨。因为每个地区邀请的人数不同，出于节约经费的问题，Neyc 研究所希望集中讨论的时候能尽量花费较少的费用。于是，就出现了一个集中地点的选择问题。假设被邀请参与研究人员所在的地区都在一条直线上，并知道每个地区与Neyc 的距离和该地被邀请人员的数目（假设Neyc 在最左端）

7、。请你编程帮助他们确定在哪个地区集中研讨可以使所有被邀请的人员集中到该地区的费用总和最小。【输入文件】输入文件每一行描述一个地区的信息（地区数=5000） ；对于每一行， 首先是该地区被邀请的人员数目，紧跟着是这个地区相对于Neyc 的距离，最后是该地区的名称。 （技术人员数=100,地区的相对距离=1031,地区名称长度=20,数据保证有唯一的解） 。【输出文件】输出文件只需一行，即研究所确定的集中研讨的地区名称。【样例输入】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，

8、共 3 页 - - - - - - - - - 7 9289 shengyan 5 8523 beijing 3 5184 guilin 8 2213 chongqing 10 0 wuhan 【样例输出】chongqing 第四题：铺设道路（ road）输入文件： road.in 输出文件： road.out 【题目描述】Neyc 的新址坐落在风景优美的QP 山上。美丽的新址，令人流连忘返，但是，由于QP山地处偏远的郊区，交通很不便利。晴天开车，一层灰，雨天开车，一车泥。Neyc 很大气，决定一步到位，把周边的道路也重新铺设一番。当然，利人利己，建设新址时，路好了也方便运输材料。为加速修建新

9、址，就必需尽快将材料运达。因此，建设人员希望修好后的路面高度单调上升或单调下降（据说，车辆通过这样的道路，速度将是无穷大的），以便建设材料在最短的时间内运到Neyc 新址。整条路现在的情况是被分成了N 段，每一路段的高度依次为A1， .,An（1=n=2000 ，0=Ai=1000000000 ） 。重新铺设后，希望各个路段高度为B1, ,Bn，恰好形成了一个含N 个元素的不上升或不下降的序列。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为：|A1-B1|+|A2-B2|+ .+|An-Bn| 请你计算一下，要修好这段道路，在这项工程上的最小支出是多少（总支出不会超过231-1） 。【输入格式】输入文件的第一行仅有一正整数，以下的N 行每行一个整数Ai ，表示路面的高度。【输出格式】输出文件仅有一个正整数，表示如果把路修成高度不上升或不下降的路面，所需的最小花费。【样例输入】7 1 3 2 4 5 3 9 【样例输出】3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -