2023年全国青少年信息学奥林匹克竞赛(NOI)课案

《2023年全国青少年信息学奥林匹克竞赛(NOI)课案》由会员分享，可在线阅读，更多相关《2023年全国青少年信息学奥林匹克竞赛(NOI)课案（14页珍藏版）》请在装配图网上搜索。

1、MT全国青少年信息学奥林匹克題NOI 20232023.能量采集【问题描述】栋栋有一块长方形的地，他在地上种了一种能量植物， 这种植物可以采集太阳光的能量。在这些植物采集能量后， 栋栋再使用一个能量集合机器把这些植物采集到的能量集合到一 起。栋栋的植物种得格外整齐，一共有每一棵植物，栋栋可以用一个坐标n 列，每列有 m 棵，植物的横竖间距都一样，因此对于x, y来表示，其中 x 的范围是 1 至 n,表示是在第 x 列，y 的范围是 1 至 m，表示是在第 x 列的第 y 棵。由于能量集合机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是0, 0。能量集合机器在集合的过程中有肯定的能量损失

2、。假设一棵植物与能量集合机器连接而成的线段上有k 棵植物，则能 量的损失为 2k + 1。例如，当能量集合机器收集坐标为 2, 4的植 物时，由于连接线段上存在一棵植物1, 2，会产生 3 的能量损失。留意，假设一棵植物与能量集合机器连接的线段上没有植物，则能量损失为1。现在要计算总的能量损失。下面给出了一个能量采集的例子，其中n = 5，m = 4，一共有 20 棵植物，在每棵植物上标明白能量集合机器收集它的能量时产生的能量损失。在这个例子中，总共产生了 36 的能量损失。【输入格式】输入文件 energy.in 仅包含一行，为两个整数 n 和 m 。【输出格式】输出文件 energy.ou

3、t 仅包含一个整数，表示总共产生的能量损失。【样例输入 1】5 4【样例输出 1】36【样例输入 2】3 4【样例输出 2】20对于 10%的数据：对【数据规模和商定】于 50%的数据： 对1 w n, m 秀 10 于 80%的数据： 对1 w n, m w 100 于 90%的数据： 对1 w n, m w 1000于 100%的数据：1 w n, m w 10,0001 w n, m w 100,。000【运行时限】1 秒。【运行空限】512M 。在这个例子中，总共产生了 36 的能量损失。超级钢琴【问题描述】小 Z 是一个小知名气的钢琴家，最近C 博士送给了小 Z 一架超级钢琴，小Z

4、期望能够用这架钢琴创作出世界上最奇特的音乐。这架超级钢琴可以弹奏出 n 个音符，编号为 1 至 n。第 i 个音符的奇特度为 A，其中 A 可正可负。一个“超级和弦”由假设干个编号连续的音符组成，包含的音符个数不少于 L 且不多于 R。我们定义超级和弦的奇特度为其包含的全部音符的奇特度之和。两 个超级和弦被认为是一样的，当且仅当这两个超级和弦所包含的音符集合是一样 的。小 Z 打算创作一首由k 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 k 个不同的超级和弦组成。我们定义一首乐曲的奇特度为其所包 含的全部超级和弦的奇特度之和。小 Z 想知道他能够创作出来的乐曲奇特度最大

5、值是多少。【输入格式】输入文件名为 piano.in。输入文件第一行包含四个正整数 n, k, L, R 。其中 n 为音符的个数，k 为乐 曲所包含的超级和弦个数，L 和 R 分别是超级和弦所包含音符个数的下限和上限。 接下来n 行，每行包含一个整数 A，表示按编号从小到大每个音符的奇特度。【输出格式】输出文件为 piano.out 。输出文件只有一个整数，表示乐曲奇特度的最大值。【样例输入】4 3 2 332-68【样例输出】11【样例说明】共有 5 种不同的超级和弦：1.音符 1 2，奇特度为 3 + 2 = 52.音符 23，奇特度为 2 + (-6) = -43.音符 34，奇特度为

6、(-6) + 8 = 24.音符 13，奇特度为 3 + 2 + (-6) = -15.音符 24，奇特度为 2 + (-6) + 8 = 4最优方案为：乐曲由和弦 1,和弦 3,和弦 5 组成，奇特度为 5 + 2 + 4 = 11【运行时限】2 秒。【运行空限】512M【数据规模和商定】测试点Nk1 10 1.000 100 500,0003 100,000=14 10.000 10,0005 500,000 10.0006 80,000 80,0007 100.000 100.0008 100.000 500,0009 500,000 500.00010 500.000 500,000总

7、共 10 个测试点，数据范围满足：i全部数据满足：-1000 A 1000，1 L R n 且保证肯定存在 满足要求的乐曲。海拔【问题描述】YT 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为nXn个区域。简单起见，可以将 YT 市看作 一个正方形，每一个区域也可看作一个正方形。从而，YT 城市中包括(n+1) x (n+个穿插路口和 2nx(n +1 条双向道路(简称道路)，每条双向 道路连接主干 道上两个相邻的穿插路口。以下图为一张 YT 市的地图(n = 2)，城市被划分为 2X2 个区域，包 括 3X3 个穿插路口和 12 条双向道路。H；= 1小 Z 作为该市的市长，他依

8、据统计信息得到了每天上班顶峰期间YT 市每条道路两个方向的人流量，即在顶峰期间沿着该方向通过这条道路的人数。每一个穿插路口都有不同的海拔高度值，YT 市市民认为爬坡是一件格外累的事情，每向上爬h 的高度，就需要消耗 h的体力。假设 是下坡的话，则不需要消耗体力。因此假设一段道路的终点海拔减去起点海 拔的值为h(留意 h 可能是负数)，那么一个人经过这段路所消耗的体力是maxa, b表示取 a, b 两个值中的较大值)。max0, h(这里小 Z 还测量得到这个城市西北角的穿插路口海拔为图所示)，但其它穿插路口的海拔高度都无法得知。小0,东南角的穿插路口海拔为 1(如上Z 想知道在最抱负的状况下

9、(即你可以任意假设其他路口的海拔高度)，每天上班顶峰期间全部人爬坡消耗的总体力和的最小值。【输入格式】输入文件 altitude.in 第一行包含一个整数 n ,含义如上文所示。接下来 4n(n + 1)行，每行包含一个非负整数分别表示每一条道路每一个方向的人流量信 息。输入挨次：n(n + 1)个数表示全部从西到东方向的人流量，然后n(n + 1)个数表示全部从北到南方向的人流量，n(n + 1)个数表示全部从东到西方向的人流量，最终是 n(n + 1)个数表 示全部从南到北方向的人流量。对于每一个方向，输入挨次依据起点由北向南，假设南北方向一样时由西到东的挨次给出 (参见样例输入)。【输出

10、格式】输出文件 altitude.out 仅包含一个数，表示在最抱负状况下每天上班顶峰期间全部人爬 坡所消耗的总体力和(即总体力和的最小值)，结果四舍五入到整数。112345678【样例输出】【样例说明】样例数据见以下图。H = 0H = 1H = 0【样例输入】最抱负状况下全部点的海拔如上图所示。【数据规模】对于 20%的数据：nW 3对于 50%的数据：nW 15对于 80%的数据：nW 40对于 100%的数据：1 W n W 500 W 流量 W 1,000,000 且全部流量均为整数。【提示】海拔高度不肯定是整数。【运行时限】2 秒。【运行空限】512M。航空管制【问题描述】世博期间

11、，上海的航空客运量大大超过了寻常，随之而来的航空管制也频频 发生。最近，小 X 就由于航空管制，连续两次在机场被延误超过了两小时。 对此， 小 X 表示很不满足。在这次来烟台的路上，小 X 不幸又一次碰上了航空管制。于是小 X 开头思考 关于航空管制的问题。假设目前被延误航班共有 n 个，编号为 1 至 n。机场只有一条起飞跑道，所 有的航班需按某个挨次依次起飞称这个挨次为 起飞序列。定义一个航班的起 飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。起飞序列还存在两类限制条件：第一类最晚起飞时间限制：编号为 i 的航班起飞序号不得超过 k；i其次类相对起飞挨次限制：存在一些相对起飞挨次

12、限制 a, b，表示 航班a 的起飞时间必需早于航班b,即航班a 的起飞序号必需小于航班b 的起飞序号。小 X 思考的第一个问题是，假设给定以上两类限制条件，是否可以计算出一个 可行的起飞序列。其次个问题则是,在考虑两类限制条件的状况下，如何求出每个航班在所有可行的 起飞序列中的最小起飞序号。【输入格式】输入文件 plane.in 第一行包含两个正整数 n 和 m n 表示航班数目，m 表示 其次类限制条件相对起飞挨次限制的数目。其次行包含 n 个正整数 k1, k2,kn。接下来 m 行，每行两个正整数 a 和 b,表示一对相对起飞挨次限制a, b， 其中Ka,b n,表示航班 a 必需先于

13、航班 b 起飞。【输出格式】输出文件 plane.out 由两行组成。第一行包含 n 个整数，表示一个可行的起飞序列， 相邻两个整数用空格分隔。 输入数据保证至少存在一个可行的 起飞序列。假设存在多个可行的方案，输出任 意一个即可。其次行包含 n 个整数 tl, t 2,t n，其中t i 表示航班i 可能的最小起飞序 号，相邻两个整数用空格分隔。【如何评分】假设你的输出文件格式与题目要求不符，则得 0 分。即你的输出文件必需满 足： 第一行恰好包含 n 个整数，且其次行也恰好包含 n 个整数。当你的输出文件格式与题目要求相符时：1. 假设仅第一行正确，获得对应测试点 40%勺分数；2. 假设

14、仅其次行正确，获得对应测试点 60%勺分数；3. 假设两行均正确，获得对应测试点 100%勺分数。【样例输入 1】5 54 5 2 5 41 23 25 13 43 1【样例输出 1】3 5 1 4 23 4 1 2 1【样例输入 2】5 03 3 3 5 5【样例输出 2】3 2 1 5 41 1 1 4 4【样例说明】在样例 1 中：起飞序列 3 5 1 4 2 满足了全部的限制条件，全部满足条件的起飞序列有:3 4 5 1 23 5 1 2 43 5 1 4 23 5 4 1 25 3 1 2 45 3 1 4 25 3 4 1 2由于存在(5, 1)和(3, 1)两个限制，航班 1 只

15、能安排在航班 5 和 3 之后，故最早 起飞时间为 3,其他航班类似。在样例 2 中：虽然航班 4、5 没有相对起飞挨次限制，但是由于航班 1、2、3 都必需安排在前 3 个起飞，所以 4、5 最早只能安排在第 4 个起飞。【数据范围】对于 30%据：nW 10;对于 60 徹据：nW 500;对于 100%据：nW 2,000，mW 10,000。【运行时限】1 秒。【运行空限】512M旅行路线【问题描述】2023 年，世博会在中国上海举办，吸引了数以千万计的中外游客前来参观。 暑假期间小 Z 也来到了上海世博园， 她对世博园的拥挤早有所闻，对有的展馆 甚至要排上好几个小时的队才能进入也做好了充分预备， 但为了使得自己的世博 之旅更加顺当舒服，小 Z 打算在游玩之前先 制定一份具体的旅行路线。小 Z 搜集到了世博园的地图， 她觉察从整体上看世博园是一块格外狭长的区 域，而每一个展馆占用了其中一个几乎一样大小的方块。 因此可以将整个园区看 成一个 nx m 的矩阵(n U“iserA0对于每组数据，我们设置了9 个评分参数 务 0 月 9,呂假设选手的输出不合法，则得零分。否则，设在你的方案中，Nemo 体重的增加量为 Wuser,你的分数将会由下表给出：假设有多项满足，则取满足条件中的最高得分。