文档介绍：该【全国青少年信息学奥林匹克竞赛NOI 】是由【春天资料屋】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【全国青少年信息学奥林匹克竞赛NOI 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
NOI2010
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
能量收集
【问题描述】
栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以收集太阳光的能量。
在这些植物收集能量后,栋栋再使用一个能量齐集机器把这些植物收集到的能量齐集到一
起。
栋栋的植物种得特别整齐,一共有
n列,每列有
m棵,植物的横竖间距都相同,因此关于
每一棵植物,栋栋可以用一个坐标
(x,y)来表示,其中x的范围是1至n,表示是在第x列,
y的范围是1至m,表示是在第x列的第y棵。
由于能量齐集机器较大,不便搬动,栋栋将它放在了一个角上,坐标正好是
(0,0)。
能量齐集机器在齐集的过程中有必然的能量损失。
若是一棵植物与能量齐集机器连接而成的
线段上有k棵植物,则能量的损失为2k+1。比方,当能量齐集机器收集坐标为
(2,4)的植
物时,由于连接线段上存在一棵植物
(1,
2),会产生3的能量损失。注意,若是一棵植物与
能量齐集机器连接的线段上没有植物,则能量损失为
1。现在要计算总的能量损失。
下面给出了一个能量收集的例子,其中
n=5,m=4,一共有20棵植物,在每棵植物上
标了然能量齐集机器收集它的能量时产生的能量损失。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
在这个例子中,总合产生了36的能量损失。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
【输入格式】
,为两个整数n和m。
【输出格式】
,表示总合产生的能量损失。
【样例输入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。
【运行时限】
秒。
【运行空限】
512M。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
超级钢琴
【问题描述】
Z是一个小有名气的钢琴家,近来C博士送给了小Z一架超级钢琴,小Z希望可以用这架钢琴创作出生界上最美好的音乐。
这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美好度为Ai,其中Ai可正可负。
一个“超级和弦”由若干个编号连续的音符组成,包括的音符个数很多于L且不多于R。我们定义超级和弦的美好度为其包括的所有音符的美好度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包括的音符会集是相同的。
Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小
Z要求该乐曲由k个不相同的超级和弦组成。我们定义一首乐曲的美好度为其所包括的所有超级和弦的美好度之和。小Z想知道他可以创作出来的乐曲美好度最大值是多少。
【输入格式】
。
输入文件第一行包括四个正整数n,k,L,R。其中n为音符的个数,k为乐
曲所包括的超级和弦个数,L和R分别是超级和弦所包括音符个数的下限和上限。
接下来n行,每行包括一个整数Ai,表示按编号从小到大每个音符的美好度。
【输出格式】
。
输出文件只有一个整数,表示乐曲美好度的最大值。
【样例输入】
4323
3
2
-6
8
【样例输出】
11
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
【样例说明】
共有5种不相同的超级和弦:
音符1~2,美好度为3+2=5
音符2~3,美好度为2+(-6)=-4
音符3~4,美好度为(-6)+8=2
音符1~3,美好度为3+2+(-6)=-1
音符2~4,美好度为2+(-6)+8=4
最优方案为:乐曲由和弦1,和弦3,和弦5组成,美好度为5+2+4=11。
【运行时限】
秒。
【运行空限】
512M。
【数据规模和约定】
总合10个测试点,数据范围满足:
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
所有数据满足:-1000≤Ai≤1000,1≤L≤R≤n且保证必然存在满足要求的乐曲。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
海拔
【问题描述】
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两个值中的较大值)。
小Z还测量获得这个城市西北角的交织路口海拔为0,东南角的交织路口海拔为1(如上
图所示),但其他交织路口的海拔高度都无法得知。小Z想知道在最理想的情况下(即你可
以随意假设其他路口的海拔高度),每天上班巅峰时期所有人爬坡耗费的整体力和的最小值。
【输入格式】
,含义如上文所示。
接下来4n(n+1)行,每行包括一个非负整数分别表示每一条道路每一个方向的人流量信
息。输入序次:n(n+1)个数表示所有从西到东方向的人流量,尔后n(n+1)个数表示所有从
北到南方向的人流量,n(n+1)个数表示所有从东到西方向的人流量,最后是n(n+1)个数表
示所有从南到北方向的人流量。关于每一个方向,输入序次依照起点由北向南,若南北方向相同时由西到东的序次给出(拜会样例输入)。
【输出格式】
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
,表示在最理想情况下每天上班巅峰时期所有人爬
坡所耗费的整体力和(即整体力和的最小值),结果四舍五入到整数。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
【样例输入】
1
1
2
3
4
5
6
7
8
【样例输出】
3
【样例说明】
样例数据见以下图。
最理想情况下所有点的海拔如上图所示。
【数据规模】
关于20%的数据:n≤;3
关于50%的数据:n≤15;
关于80%的数据:n≤40;
关于100%的数据:1≤n≤,500≤流量≤1,000,000且所有流量均为整数。
【提示】
海拔高度不用然是整数。
【运行时限】
秒。
【运行空限】
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
512M。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
航空管制
【问题描述】
世博时期,上海的航空客运量大大高出了平时,随之而来的航空管制也频频
发生。近来,小X就由于航空管制,连续两次在机场被延缓高出了两小时。对此,小X表示很不满意。
在此次来烟台的路上,小X不幸又一次碰上了航空管制。于是小X开始思虑关于航空管制的问题。
假设目前被延缓航班共有n个,编号为1至n。机场只有一条腾跃跑道,所有的航班需按某个序次依次腾跃(称这个序次为腾跃序列)。定义一个航班的腾跃序号为该航班在腾跃序列中的地址,即是第几个腾跃的航班。
腾跃序列还存在两类限制条件:
第一类(最晚腾跃时间限制):编号为i的航班腾跃序号不得高出ki;
第二类(相对腾跃序次限制):存在一些相对腾跃序次限制(a,b),表示航班a的腾跃时间必定早于航班b,即航班a的腾跃序号必定小于航班b
的腾跃序号。
X思虑的第一个问题是,若给定以上两类限制条件,可否可以计算出一个
可行的腾跃序列。第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的腾跃序列中的最小腾跃序号。
【输入格式】
,n表示航班数目,m表示
第二类限制条件(相对腾跃序次限制)的数目。
第二行包括n个正整数k1,k2,,kn。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
接下来m行,每行两个正整数a和b,表示一对相对腾跃序次限制
(a,b)
,
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
其中1≤a,b≤n,表示航班a必定先于航班b腾跃。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
【输出格式】
。
第一行包括n个整数,表示一个可行的腾跃序列,相邻两个整数用空格分开。输入数据保证最少存在一个可行的腾跃序列。若是存在多个可行的方案,输出随意一个即可。
第二行包括n个整数t1,t2,,tn,其中ti表示航班i可能的最小腾跃序号,相邻两个整数用空格分开。
【如何评分】
若是你的输出文件格式与题目要求不符,则得0分。即你的输出文件必定满足:第一行恰好包括n个整数,且第二行也恰好包括n个整数。
当你的输出文件格式与题目要求切合时:
若是仅第一行正确,获得对应测试点40%的分数;
若是仅第二行正确,获得对应测试点60%的分数;
若是两行均正确,获得对应测试点100%的分数。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
【样例输入1】
55
45254
2
2
1
4
1
【样例输出1】
35142
34121
【样例输入2】
50
33355
【样例输出2】
32154
11144
【样例说明】
在样例1中:
腾跃序列35142
满足了所有的限制条件,所有满足条件的
腾跃序列有:
34512
35124
35142
35412
53124
53142
53412
由于存在(5,1)和(3,1)两个限制,航班1只能安排在航班5和3此后,故最早
腾跃时间为3,其他航班近似。
在样例2中:
诚然航班4、5没有相对腾跃序次限制,但是由于航班1、2、3都必定安排在前3个腾跃,因此4、5最早只能安排在第4个腾跃。
【数据范围】
关于30%数据:n≤10;
关于60%数据:n≤500;
关于100%数据:n≤2,000,m≤10,000。
【运行时限】
秒。
【运行空限】
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
512M。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
旅行路线
【问题描述】
2010年,世博会在中国上海举办,吸引了数以千万计的中外游客前来参观。暑期时期小Z也到达了上海世博园,她对世博园的拥挤早有所闻,对有的展馆甚至要排上好几个小时的队才能进入也做好了充分准备,但为了使得自己的世博之旅更加顺利快乐,小Z决定在游玩从前先拟定一份详细的旅行路线。
Z收集到了世博园的地图,她发现从整体上看世博园是一块特别狭长的区
域,而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看作一个n×m的矩阵(n≤3),其中每一个格子为一个主题展馆。
由于不相同展馆碰到的关注度会有一些差别,因此排队时间的长短也不尽相同。
小Z依照统计信息给每一个展馆(x,y)标记了Tx,y=0或1,若是Tx,y=1,表示这个展馆特别热门,需要排很长时间的队;若是Tx,y=0,表示这个展馆相比较较一般,几乎不需要排队即可进入参观。小Z希望可以拟定一份合理的路线,使得能交替参观热门馆和一般馆,既不会由于总是参观热门馆而长时间在
排队,也不会由于总是参观一般馆而使得旅行过于平凡。同时,小Z做事很讲究效率,她希望在游遍所有展馆的同时,又不会走冤枉路浪费体力。因此她希望旅行路线满足以下几个限制:
在参观完位于(x,y)的展馆后,下一个参观的是一个相邻的且未被参观过
的展馆(x',y'),即|x-x'|+|y-y'|=1;
,即x=1或x=n或y=1或y=m;
她拟定了一个长度为n*m的01序列L,她希望第i个参观的展馆(x,y)满足
Tx,y=Li。
小Z想知道有多少条不相同的旅行路线可以满足她的要求。由于最后的结果可能很大,小Z只想知道可行的旅行路线总数mod11192869的值。
【输入文件】
,m。
2行至第n+1行,每行有m个01整数,其中第i+1行第j个数表示Ti,j。
n+2行有n*m个01整数,其中第i个数表示Li的值。
【输出文件】
,表示可行的旅行路线总数mod11192869的值。
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI
全国青少年信息学奥林匹克比赛NOI