全国青少年信息学奥林匹克竞赛(NOI)2010_试题

1、 NOI 20102010.8能量采集【问题描述】栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐,一共有n列,每列有m棵,植物的横竖间距都一样,因此对于每一棵植物,栋栋可以用一个坐标(x, y来表示,其中x的范围是1至n,表示是在第x列, y的范围是1至m,表示是在第x列的第y棵。由于能量汇集机器较大,不便移动,栋栋将它放在了一个角上,坐标正好是(0, 0。能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物,则能量

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

3、】3 4【样例输出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。【运行时限】1秒。【运行空限】512M。超级钢琴【问题描述】小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z 希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美妙度为A i ,其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成,包含的音符个数不少于L且不多于

4、R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包含的音符集合是相同的。小Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。【输入格式】输入文件名为piano.in。输入文件第一行包含四个正整数n, k, L, R。其中n为音符的个数,k为乐曲所包含的超级和弦个数,L和R分别是超级和弦所包含音符个数的下限和上限。接下来n行,每行包含一个整数Ai,表示按编号从小到大每个音

5、符的美妙度。【输出格式】输出文件为piano.out。输出文件只有一个整数,表示乐曲美妙度的最大值。【样例输入】4 3 2 332-68【样例输出】11【样例说明】共有5种不同的超级和弦:1.音符1 2,美妙度为3 + 2 = 52.音符2 3,美妙度为2 + (-6 = -43.音符3 4,美妙度为(-6 + 8 = 24.音符1 3,美妙度为3 + 2 + (-6 = -15.音符2 4,美妙度为2 + (-6 + 8 = 4最优方案为:乐曲由和弦1,和弦3,和弦5组成,美妙度为5 + 2 + 4 = 11。【运行时限】2秒。【运行空限】512M。【数据规模和约定】总共10个测试点,数据范

6、围满足: 所有数据满足:-1000 A 1000,1 L R n且保证一定存在i满足要求的乐曲。海拔【问题描述】YT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×n个区域。简单起见,可以将YT市看作一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1×(n+1个交叉路口和2n×(n+1条双向道路(简称道路,每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2,城市被划分为2×2个区域,包括3×3个交叉路口和12条双向道路。 小Z作为该市的市长,他根据统计信息得到了每天上班高峰期间YT市

7、每条道路两个方向的人流量,即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值,YT市市民认为爬坡是一件非常累的事情,每向上爬h的高度,就需要消耗h 的体力。如果是下坡的话,则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数,那么一个人经过这段路所消耗的体力是max0, h(这里maxa, b表示取a, b两个值中的较大值。小Z还测量得到这个城市西北角的交叉路口海拔为0,东南角的交叉路口海拔为1(如上图所示,但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下(即你可以任意假设其他路口的海拔高度,每天上班高峰期间所有人爬坡消耗的

8、总体力和的最小值。【输入格式】输入文件altitude.in第一行包含一个整数n,含义如上文所示。接下来4n(n + 1行,每行包含一个非负整数分别表示每一条道路每一个方向的人流量信息。输入顺序:n(n + 1个数表示所有从西到东方向的人流量,然后n(n + 1个数表示所有从北到南方向的人流量,n(n + 1个数表示所有从东到西方向的人流量,最后是n(n + 1个数表示所有从南到北方向的人流量。对于每一个方向,输入顺序按照起点由北向南,若南北方向相同时由西到东的顺序给出(参见样例输入。【输出格式】输出文件altitude.out仅包含一个数,表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的

9、总体力和(即总体力和的最小值,结果四舍五入到整数。【样例输入】112345678【样例输出】3【样例说明】样例数据见下图。 最理想情况下所有点的海拔如上图所示。【数据规模】对于20%的数据:n 3;对于50%的数据:n 15;对于80%的数据:n 40;对于100%的数据:1 n 500,0 流量 1,000,000且所有流量均为整数。【提示】海拔高度不一定是整数。【运行时限】2秒。【运行空限】512M。航空管制【问题描述】世博期间,上海的航空客运量大大超过了平时,随之而来的航空管制也频频发生。最近,小X就因为航空管制,连续两次在机场被延误超过了两小时。对此,小X表示很不满意。在这次来烟台的路

10、上,小X不幸又一次碰上了航空管制。于是小X开始思考关于航空管制的问题。假设目前被延误航班共有n个,编号为1至n。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。起飞序列还存在两类限制条件:第一类(最晚起飞时间限制:编号为i的航班起飞序号不得超过k i;第二类(相对起飞顺序限制:存在一些相对起飞顺序限制(a, b,表示航班a的起飞时间必须早于航班b,即航班a的起飞序号必须小于航班b的起飞序号。小X思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。第二个问题则是,在考虑两

11、类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。【输入格式】输入文件plane.in第一行包含两个正整数n和m,n表示航班数目,m表示第二类限制条件(相对起飞顺序限制的数目。第二行包含n个正整数k1, k2, , kn。接下来m行,每行两个正整数a和b,表示一对相对起飞顺序限制(a, b,其中1a,bn, 表示航班a必须先于航班b起飞。【输出格式】输出文件plane.out由两行组成。第一行包含n个整数,表示一个可行的起飞序列,相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案,输出任意一个即可。第二行包含n个整数t1, t2, ,

12、 tn,其中ti表示航班i可能的最小起飞序号,相邻两个整数用空格分隔。【如何评分】如果你的输出文件格式与题目要求不符,则得0分。即你的输出文件必须满足:第一行恰好包含n个整数,且第二行也恰好包含n个整数。当你的输出文件格式与题目要求相符时:1.如果仅第一行正确,获得对应测试点40%的分数;2.如果仅第二行正确,获得对应测试点60%的分数;3.如果两行均正确,获得对应测试点100%的分数。【样例输入1】5 54 5 2 5 41 23 25 13 43 1【样例输出1】3 5 14 23 4 1 2 1【样例输入2】5 03 3 3 5 5【样例输出2】3 2 1 5 41 1 1 4 4【样例

13、说明】在样例1 中:起飞序列3 5 1 4 2满足了所有的限制条件,所有满足条件的起飞序列有:3 4 5 1 2 3 5 1 2 4 3 5 1 4 2 3 5 4 1 2 5 3 1 2 4 5 3 1 4 2 5 3 4 1 2由于存在(5, 1和(3, 1两个限制,航班1只能安排在航班5和3之后,故最早起飞时间为3,其他航班类似。在样例2 中:虽然航班4、5没有相对起飞顺序限制,但是由于航班1、2、3都必须安排在前3个起飞,所以4、5最早只能安排在第4个起飞。【数据范围】对于30%数据:n10;对于60%数据:n500;对于100%数据:n2,000,m10,000。【运行时限】1秒。【

14、运行空限】512M。旅行路线【问题描述】2010年,世博会在中国上海举办,吸引了数以千万计的中外游客前来参观。暑假期间小Z 也来到了上海世博园, 她对世博园的拥挤早有所闻,对有的展馆甚至要排上好几个小时的队才能进入也做好了充分准备,但为了使得自己的世博之旅更加顺利舒畅,小Z 决定在游玩之前先 制定一份详细的旅行路线。小Z 搜集到了世博园的地图,她发现从整体上看世博园是一块非常狭长的区域,而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看成一个n × m 的矩阵(n3,其中每一个格子为一个主题展馆。由于不同展馆受到的关注度会有一些差别,因此排队时间的长短也不尽相同。小Z

15、 根据统计信息给每一个展馆(x, y标记了Tx,y = 0或1,如果Tx,y = 1,表示这个展馆非常热门,需要排很长时间的队;如果Tx,y = 0,表示这个展馆相对比较普通,几乎不需要排队即可进入参观。小Z 希望能够制定一份合理的路线,使得能交替参观热门馆和普通馆,既不会因为总是参观热门馆 而长时间在排队,也不会因为总是参观普通馆而使得游览过于平淡。同时,小Z 办事很讲究效率,她希望在游遍所有展馆的同时,又不会走冤枉路浪费体力。因此她希望旅行路线满足以下几个限制:1. 在参观完位于(x, y的展馆后,下一个参观的是一个相邻的且未被参观过的展馆(x', y',即 |x-x

16、9;|+|y-y'|=1;2. 路线的起点位于整个矩阵的边界上,即x = 1或x = n 或y = 1或y = m ; 她制定了一个长度为n*m 的 01 序列L ,她希望第i 个参观的展馆(x,y满足T x,y =L i 。小Z 想知道有多少条不同的旅行路线能够满足她的要求。由于最终的结果可能很大,小Z 只想知道可行的旅行路线总数mod 11192869的值。【输入文件】输入文件trip.in 第一行包含两个正整数n, m 。第2行至第n+ 1行,每行有m 个01整数,其中第i+ 1行第j 个数表示T i,j 。 第n+ 2行有n*m 个01整数,其中第i 个数表示L i 的值。【输

17、出文件】输出文件trip.out 仅包含一个整数,表示可行的旅行路线总数mod 11192869的值。全国青少年奥林匹克竞赛（NOI）2010 试题 【输入样例】 2 2 10 01 1010 【输出样例】 4 【样例说明】 这四条可行的旅行路线分别为： (1,1(1,2(2,2(2,1 (1,1(2,1(2,2(1,2 (2,2(1,2(1,1(2,1 (2,2(2,1(1,1(1,2 【数据规模和约定】 对于 10%的数据：n=1； 对于 30%的数据：n=2； 对于 60%的数据：n= 3，其中 20%的数据 Ti,j 全为 0； 对于 100%的数据：m50，Li, Ti,j = 0

18、或 1。 【运行时限】 10 秒。 【运行空限】 512M。 Copyright © 2010 中国计算机学会, 版权所有. 全国青少年奥林匹克竞赛（NOI）2010 试题 成长快乐 【问题描述】 Nemo 是一条无忧无虑的小鱼， 它的初始体重为 w0。 可爱的 Nemo 希望自己能够尽快地 成长，因此需要吃尽量多的食物。Nemo 最喜爱的食物是海里的小虾。 已知 Nemo 对食物的情况了解如下：大海里共有 n 只小虾，从 1 到 n 编号，其中编号为 i 的小虾的重量为 wi。 将大海看作一个 X-Y 坐标系， 0 时刻编号为 i 的小虾所在的位置为(xi, 在 yi。小虾在大海中

19、作匀速直线运动，其中编号为 i 的小虾的速度向量为(pi, qi，即在时刻 t， 它的位置为 (xi+pi*t,yi+qi*t Nemo 在 0 时刻的位置为(x0, y0，它可以在海中随意移动，但速度不超过 V。Nemo 希望 通过自己的努力，在 T 个单位时间内(含 T 时刻吃到的小虾重量总和尽量大。当 Nemo 与某 只小虾同时移动到同一个位置上，且小虾的重量小于 Nemo 当时的重量，则 Nemo 可以将该 小虾吃掉。 Nemo 吃掉重量为 wi 的小虾之后， 当 它的体重将增加 wi。 注意， 小虾不会吃 Nemo， 且小虾之间也不会自相残杀。 Nemo 希望你来帮助它制定一个成长计划，使得它吃掉的小虾重量总和尽量大。 【输入格式】 该题为提交答案型试题，所有输入数据 nemo1.innemo10.in 已在试题目录下。 对于每个数据，输入文件中第一行为五个实数 w0, V, T, x0, y0。分别表示 Nemo 的初始体 重、最大移动速度、时间限制以及 Nemo 在 0 时刻的位置。 第二行为一个整数 n，表示大海中小虾的只数。 接下来 n 行，每行 5 个实数，包括 wi, xi, yi, pi, qi，分别表示编号为 i 的小虾的重量、在 0