全国青少年信息学奥林匹克竞赛(NOI)2010_试题
- 格式：pdf
- 大小：447.90 KB
- 文档页数：13
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
【样例输入 1】
55 45254 12 32 51 34 31
【样例输出 1】
35142 34121
【样例输入 2】
50 33355
【样例输出 2】
32154 11144
【样例说明】
在样例 1 中：
一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 L 且不多于 R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两 个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同 的。
小 Z 决定创作一首由 k 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 k 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包 含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大 值是多少。
输入文件 energy.in 仅包含一行，为两个整数 n 和 m。
【输出格式】
输出文件 energy.out 仅包含一个整数，表示总共产生的能量损失。
【样例输入 1】
54
【样例输出 1】
36
【样例输入 2】
34
【样例输出 2】
20
【数据规模和约定】
对于 10%的数据：1 ≤ n, m ≤ 10； 对于 50%的数据：1 ≤ n, m ≤ 100； 对于 80%的数据：1 ≤ n, m ≤ 1000； 对于 90%的数据：1 ≤ n, m ≤ 10,000； 对于 100%的数据：1 ≤ n, m ≤ 100,000。
【输出格式】
输出文件 plane.out 由两行组成。 第一行包含 n 个整数，表示一个可行的起飞序列，相邻两个整数用空格分隔。 输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案，输出任 意一个即可。 第二行包含 n 个整数 t1, t2, „, tn，其中 ti 表示航班 i 可能的最小起飞序 号，相邻两个整数用空格分隔。
小 Z 搜集到了世博园的地图，她发现从整体上看世博园是一块非常狭长的区 域，而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看 成一个 n × m 的矩阵(n≤3)，其中每一个格子为一个主题展馆。
【提示】
海拔高度不一定是整数。
【运行时限】
2 秒。
【运行空限】
512M。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
航空管制
【问题描述】
世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频 发生。最近，小 X 就因为航空管制，连续两次在机场被延误超过了两小时。对此， 小 X 表示很不满意。
起飞序列还存在两类限制条件： 第一类（最晚起飞时间限制）：编号为 i 的航班起飞序号不得超过 ki; 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示
航班 a 的起飞时间必须早于航班 b，即航班 a 的起飞序号必须小于航班 b 的起飞序号。 小 X 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个 可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每 个航班在所有可行的起飞序列中的最小起飞序号。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
海拔 【问题描述】
YT 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为 n×n 个区域。简 单起见，可以将 YT 市看作 一个正方形，每一个区域也可看作一个正方形。从而，YT 城市 中包括(n+1)×(n+1)个交叉路口和 2n×(n+1)条双向道路（简称道路），每条双向 道路连接主干 道上两个相邻的交叉路口。下图为一张 YT 市的地图(n = 2)，城市被划分为 2×2 个区域，包 括 3×3 个交叉路口和 12 条双向道路。
小 Z 作为该市的市长，他根据统计信息得到了每天上班高峰期间 YT 市每条道路两个方 向的人流量，即在高峰期间沿 着该方向通过这条道路的人数。每一个交叉路口都有不同的 海拔高度值，YT 市市民认为爬坡是一件非常累的事情，每向上爬 h 的高度，就需要消耗 h 的体力。如果 是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海 拔的值为 h(注意 h 可能是负数)，那么一个人经过这段路所消耗的体力是 max{0, h}（这里 max{a, b}表示取 a, b 两个值中的较大值）。
输出文件为 piano.out。 输出文件只有一个整数，表示乐曲美妙度的最大值。
【样例输入】
4323 3 2 -6 8
【样例输出】
11
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛 5 种不同的超级和弦： 1. 音符 1 ~ 2，美妙度为 3 + 2 = 5 2. 音符 2 ~ 3，美妙度为 2 + (-6) = -4 3. 音符 3 ~ 4，美妙度为(-6) + 8 = 2 4. 音符 1 ~ 3，美妙度为 3 + 2 + (-6) = -1 5. 音符 2 ~ 4，美妙度为 2 + (-6) + 8 = 4
【输出格式】
输出文件 altitude.out 仅包含一个数，表示在最理想情况下每天上班高峰期间所有人爬 坡所消耗的总体力和（即总体力和的最小值），结果四舍五入到整数。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
【样例输入】
1 1 2 3 4 5 6 7 8
最优方案为：乐曲由和弦 1，和弦 3，和弦 5 组成，美妙度为 5 + 2 + 4 = 11。
【运行时限】
2 秒。
【运行空限】
512M。
【数据规模和约定】
总共 10 个测试点，数据范围满足：
所有数据满足：-1000 ≤ Ai ≤ 1000，1 ≤ L ≤ R ≤ n 且保证一定存在 满足要求的乐曲。
【样例输出】
3
【样例说明】
样例数据见下图。
最理想情况下所有点的海拔如上图所示。
【数据规模】
对于 20%的数据：n ≤ 3； 对于 50%的数据：n ≤ 15； 对于 80%的数据：n ≤ 40； 对于 100%的数据：1 ≤ n ≤ 500，0 ≤ 流量 ≤ 1,000,000 且所有流量均为整数。
【输入格式】
输入文件 plane.in 第一行包含两个正整数 n 和 m，n 表示航班数目，m 表示 第二类限制条件（相对起飞顺序限制）的数目。
第二行包含 n 个正整数 k1, k2, „, kn。 接下来 m 行，每行两个正整数 a 和 b，表示一对相对起飞顺序限制(a, b)， 其中 1≤a,b≤n, 表示航班 a 必须先于航班 b 起飞。
起飞序列 3 5 1 4 2 满足了所有的限制条件，所有满足条件的起飞序列有：
34512
35124
35142
35412
53124
53142
53412
由于存在(5, 1)和(3, 1)两个限制，航班 1 只能安排在航班 5 和 3 之后，故最早
起飞时间为 3，其他航班类似。
在样例 2 中：
虽然航班 4、5 没有相对起飞顺序限制，但是由于航班 1、2、3 都必须安排在前
全国青少年奥林匹克竞赛（NOI）2010 试题
NOI 2010
2010.8
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
能量采集 【问题描述】
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。 在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一 起。 栋栋的植物种得非常整齐，一共有 n 列，每列有 m 棵，植物的横竖间距都一样，因此对于 每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中 x 的范围是 1 至 n，表示是在第 x 列， y 的范围是 1 至 m，表示是在第 x 列的第 y 棵。
【运行时限】
1 秒。
【运行空限】
512M。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
超级钢琴
【问题描述】
小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出 n 个音符，编号为 1 至 n。第 i 个音符的美妙度为 Ai，其中 Ai 可正可负。
下面给出了一个能量采集的例子，其中 n = 5，m = 4，一共有 20 棵植物，在每棵植物上 标明了能量汇集机器收集它的能量时产生的能量损失。
在这个例子中，总共产生了 36 的能量损失。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
【输入格式】
【如何评分】
如果你的输出文件格式与题目要求不符，则得 0 分。即你的输出文件必须满 足：第一行恰好包含 n 个整数，且第二行也恰好包含 n 个整数。
当你的输出文件格式与题目要求相符时： 1. 如果仅第一行正确，获得对应测试点 40%的分数； 2. 如果仅第二行正确，获得对应测试点 60%的分数； 3. 如果两行均正确，获得对应测试点 100%的分数。
在这次来烟台的路上，小 X 不幸又一次碰上了航空管制。于是小 X 开始思考 关于航空管制的问题。
假设目前被延误航班共有 n 个，编号为 1 至 n。机场只有一条起飞跑道，所 有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起 飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。
全国青少年奥林匹克竞赛（NOI）2010 试题
【样例输入 1】
55 45254 12 32 51 34 31
【样例输出 1】
35142 34121
【样例输入 2】
50 33355
【样例输出 2】
32154 11144
【样例说明】
在样例 1 中：
一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 L 且不多于 R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两 个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同 的。
小 Z 决定创作一首由 k 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 k 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包 含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大 值是多少。
输入文件 energy.in 仅包含一行，为两个整数 n 和 m。
【输出格式】
输出文件 energy.out 仅包含一个整数，表示总共产生的能量损失。
【样例输入 1】
54
【样例输出 1】
36
【样例输入 2】
34
【样例输出 2】
20
【数据规模和约定】
对于 10%的数据：1 ≤ n, m ≤ 10； 对于 50%的数据：1 ≤ n, m ≤ 100； 对于 80%的数据：1 ≤ n, m ≤ 1000； 对于 90%的数据：1 ≤ n, m ≤ 10,000； 对于 100%的数据：1 ≤ n, m ≤ 100,000。
【输出格式】
输出文件 plane.out 由两行组成。 第一行包含 n 个整数，表示一个可行的起飞序列，相邻两个整数用空格分隔。 输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案，输出任 意一个即可。 第二行包含 n 个整数 t1, t2, „, tn，其中 ti 表示航班 i 可能的最小起飞序 号，相邻两个整数用空格分隔。
小 Z 搜集到了世博园的地图，她发现从整体上看世博园是一块非常狭长的区 域，而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看 成一个 n × m 的矩阵(n≤3)，其中每一个格子为一个主题展馆。
【提示】
海拔高度不一定是整数。
【运行时限】
2 秒。
【运行空限】
512M。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
航空管制
【问题描述】
世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频 发生。最近，小 X 就因为航空管制，连续两次在机场被延误超过了两小时。对此， 小 X 表示很不满意。
起飞序列还存在两类限制条件： 第一类（最晚起飞时间限制）：编号为 i 的航班起飞序号不得超过 ki; 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示
航班 a 的起飞时间必须早于航班 b，即航班 a 的起飞序号必须小于航班 b 的起飞序号。 小 X 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个 可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每 个航班在所有可行的起飞序列中的最小起飞序号。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
海拔 【问题描述】
YT 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为 n×n 个区域。简 单起见，可以将 YT 市看作 一个正方形，每一个区域也可看作一个正方形。从而，YT 城市 中包括(n+1)×(n+1)个交叉路口和 2n×(n+1)条双向道路（简称道路），每条双向 道路连接主干 道上两个相邻的交叉路口。下图为一张 YT 市的地图(n = 2)，城市被划分为 2×2 个区域，包 括 3×3 个交叉路口和 12 条双向道路。
小 Z 作为该市的市长，他根据统计信息得到了每天上班高峰期间 YT 市每条道路两个方 向的人流量，即在高峰期间沿 着该方向通过这条道路的人数。每一个交叉路口都有不同的 海拔高度值，YT 市市民认为爬坡是一件非常累的事情，每向上爬 h 的高度，就需要消耗 h 的体力。如果 是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海 拔的值为 h(注意 h 可能是负数)，那么一个人经过这段路所消耗的体力是 max{0, h}（这里 max{a, b}表示取 a, b 两个值中的较大值）。
输出文件为 piano.out。 输出文件只有一个整数，表示乐曲美妙度的最大值。
【样例输入】
4323 3 2 -6 8
【样例输出】
11
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛 5 种不同的超级和弦： 1. 音符 1 ~ 2，美妙度为 3 + 2 = 5 2. 音符 2 ~ 3，美妙度为 2 + (-6) = -4 3. 音符 3 ~ 4，美妙度为(-6) + 8 = 2 4. 音符 1 ~ 3，美妙度为 3 + 2 + (-6) = -1 5. 音符 2 ~ 4，美妙度为 2 + (-6) + 8 = 4
【输出格式】
输出文件 altitude.out 仅包含一个数，表示在最理想情况下每天上班高峰期间所有人爬 坡所消耗的总体力和（即总体力和的最小值），结果四舍五入到整数。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
【样例输入】
1 1 2 3 4 5 6 7 8
最优方案为：乐曲由和弦 1，和弦 3，和弦 5 组成，美妙度为 5 + 2 + 4 = 11。
【运行时限】
2 秒。
【运行空限】
512M。
【数据规模和约定】
总共 10 个测试点，数据范围满足：
所有数据满足：-1000 ≤ Ai ≤ 1000，1 ≤ L ≤ R ≤ n 且保证一定存在 满足要求的乐曲。
【样例输出】
3
【样例说明】
样例数据见下图。
最理想情况下所有点的海拔如上图所示。
【数据规模】
对于 20%的数据：n ≤ 3； 对于 50%的数据：n ≤ 15； 对于 80%的数据：n ≤ 40； 对于 100%的数据：1 ≤ n ≤ 500，0 ≤ 流量 ≤ 1,000,000 且所有流量均为整数。
【输入格式】
输入文件 plane.in 第一行包含两个正整数 n 和 m，n 表示航班数目，m 表示 第二类限制条件（相对起飞顺序限制）的数目。
第二行包含 n 个正整数 k1, k2, „, kn。 接下来 m 行，每行两个正整数 a 和 b，表示一对相对起飞顺序限制(a, b)， 其中 1≤a,b≤n, 表示航班 a 必须先于航班 b 起飞。
起飞序列 3 5 1 4 2 满足了所有的限制条件，所有满足条件的起飞序列有：
34512
35124
35142
35412
53124
53142
53412
由于存在(5, 1)和(3, 1)两个限制，航班 1 只能安排在航班 5 和 3 之后，故最早
起飞时间为 3，其他航班类似。
在样例 2 中：
虽然航班 4、5 没有相对起飞顺序限制，但是由于航班 1、2、3 都必须安排在前
全国青少年奥林匹克竞赛（NOI）2010 试题
NOI 2010
2010.8
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
能量采集 【问题描述】
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。 在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一 起。 栋栋的植物种得非常整齐，一共有 n 列，每列有 m 棵，植物的横竖间距都一样，因此对于 每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中 x 的范围是 1 至 n，表示是在第 x 列， y 的范围是 1 至 m，表示是在第 x 列的第 y 棵。
【运行时限】
1 秒。
【运行空限】
512M。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
超级钢琴
【问题描述】
小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出 n 个音符，编号为 1 至 n。第 i 个音符的美妙度为 Ai，其中 Ai 可正可负。
下面给出了一个能量采集的例子，其中 n = 5，m = 4，一共有 20 棵植物，在每棵植物上 标明了能量汇集机器收集它的能量时产生的能量损失。
在这个例子中，总共产生了 36 的能量损失。
Copyright © 2010 中国计算机学会, 版权所有.
全国青少年奥林匹克竞赛（NOI）2010 试题
【输入格式】
【如何评分】
如果你的输出文件格式与题目要求不符，则得 0 分。即你的输出文件必须满 足：第一行恰好包含 n 个整数，且第二行也恰好包含 n 个整数。
当你的输出文件格式与题目要求相符时： 1. 如果仅第一行正确，获得对应测试点 40%的分数； 2. 如果仅第二行正确，获得对应测试点 60%的分数； 3. 如果两行均正确，获得对应测试点 100%的分数。
在这次来烟台的路上，小 X 不幸又一次碰上了航空管制。于是小 X 开始思考 关于航空管制的问题。
假设目前被延误航班共有 n 个，编号为 1 至 n。机场只有一条起飞跑道，所 有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起 飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。
