课件案例全国赛day_第1页
课件案例全国赛day_第2页
课件案例全国赛day_第3页
课件案例全国赛day_第4页
课件案例全国赛day_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、45/ 航空【问题描述】世博期间,的航空客运量大大超过了平时,随之而来的航空也频频发生。最近,小 X 就因为航空小 X 表示很不满意。,连续两次在机场被延误超过了两小时。对此,在这次来烟台的关于航空,小 X 不幸又一次碰上了航空。于是小 X 开始思考。假设目前被延误航班共有 n 个,为 1 至 n。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。起飞序列还存在两类限制条件:第一类(最晚起飞时间限制):为 i 的航班起飞序号不得超过 ki;第二类(相对起飞顺序限制):存在一些相对起飞顺序限制(a

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

3、先于航班 b 起飞。【输出格式】输出文件 plane.out 由两行组成。第一行包含 n 个整数,表示一个可行的起飞序列,相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案,输出任意一个即可。第二行包含 n 个整数 t1, t2, , tn,其中 ti 表示航班 i 可能的最小起飞序号,相邻两个整数用空格分隔。【如何评分】如果你的输出文件格式与题目要求不符,则得 0 分。即你的输出文件必须满足:第一行恰好包含 n 个整数,且第二行也恰好包含 n 个整数。当你的输出文件格式与题目要求相符时:1.2.3.如果仅第一行正确,获得对应测试点 40%的分数;如果仅第二

4、行正确,获得对应测试点 60%的分数;如果两行均正确,获得对应测试点 100%的分数。【样例输入】25【样例输出】3 4 1 2 1【样例输入 2】5 03 3 3 5 5【样例输出 2】3 2 1 5 41 1 1 4 4【样例说明】在样例 1 中:起飞序列 33 4 5 1 22 45142 满足了所有的限制条件,所有满足条件的起飞序列有:3 5 1 2 45 3 1 4 23 55 3 4 1 2由于存在(5, 1)和(3, 1)两个限制,航班 1 只能安排在航班 5 和 3 之后,故最早起飞时间为 3,其他航班类似。在样例 2 中:虽然航班 4、5 没有相对起飞顺序限制,但是由于航班

5、1、2、3 都必须安排3 个起飞,所以 4、5 最早只能安排在第 4 个起飞。【数据范围】对于 30%数据:n10;对于 60%数据:n500;对于 100%数据:n2,000,m10,000。【运行时限】1 秒。【运行空限】512M。旅行路线【问题描述】2010 年,世博会 暑假期间小 Z 也来到了举办,吸引了数以千万计的中外游客前来参观。世, 她对世的拥挤早有所闻,对有的展馆甚至要排上好几个小时的队才能进入也做好了充分准备,但为了使得自己的世博之旅更加顺利舒畅,小 Z 决定在游玩之前先 制定一份详细的旅行路线。小 Z 搜集到了世的地图,她发现从整体上看世是一块非常狭长的区域,而每一个展馆占

6、用了其中一个几乎相同大小的方块。因此可以将整个园区看成一个 n m 的矩阵(n3),其中每一个格子为一个展馆。由于不同展馆受到的关注度会有一些差别,因此排队时间的长短也不尽相同。小 Z 根据统计信息给每一个展馆(x, y)标记了 Tx,y = 0 或 1,如果 Tx,y = 1,表示这个展馆非常热门,需要排很长时间的队;如果 Tx,y = 0,表示这个展馆相对比较普通,几乎不需要排队参观。小 Z 希望能够制定一份合理的路线,使得能交替参观热门馆和普通馆,既不会因为总是参观热门馆 而长时间在排队,也不会因为总是参观普通馆而使得游览过于平淡。同时,小 Z 办事很讲究效率,她希望在游遍所有展馆的同时

7、,又不会走冤枉路浪费体力。因此她希望旅行路线满足以下几个限制:在参观完位于(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 只想知道可行的旅行路线总数 mod 11192869 的值。【输入文件】输入文件 trip.in 第一行包含两个正整数 n, m。第

8、2 行至第 n+ 1 行,每行有 m 个 01 整数,其中第 i+ 1 行第 j 个数表示 Ti,j。第 n+ 2 行有 n*m 个 01 整数,其中第 i 个数表示 Li 的值。【输出文件】输出文件 trip.out 仅包含一个整数,表示可行的旅行路线总数 mod 11192869的值。【输入样例】2 210011010【输出样例】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%的数

9、据:n=2;对于 60%的数据:n= 3,其中 20%的数据 Ti,j 全为 0;对于 100%的数据:m50,Li,【运行时限】10 秒。【运行空限】512M。Ti,j= 0 或 1。成长【问题描述】Nemo 是一条无忧无虑的小鱼,它的初始体重为 w0。可爱的 Nemo 希望自己能够尽快地成长,因此需要吃尽量多的食物。Nemo 最喜爱的食物是海里的小虾。已知 Nemo 对食物的情况了解如下:大海里共有 n 只小虾,从 1 到 n,其中为i 的小虾的重量为 wi。将大海看作一个 X-Y 坐标系,在 0 时刻为 i 的小虾所在的位置为(xi,yi)。小虾在大海中作匀速直线运动,其中它的位置为为

10、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 希望你来帮助它制定一个成长计划,使得它【输入格式】的小虾重量总和尽量大。该题为提交型试题,所有输入

11、数据 nemo1.innemo10.in 已在试题目录下。对于每个数据,输入文件中第一行为五个实数 w0, V, T, x0, y0。分别表示 Nemo 的初始体重、最大移动速度、时间限制以及 Nemo 在 0 时刻的位置。第二行为一个整数 n,表示大海中小虾的只数。接下来 n 行,每行 5 个实数,包括 wi, xi, yi, pi, qi,分别表示 0 时刻的位置和速度向量。【输出格式】为 i 的小虾的重量、在针对给定的 10 个输入文件 nemo1.innemo10.in , 你需要分别提交你的输出文件nemo1.outnemo10.out。输出文件第一行包含一个整数 k。表示在你的成长计划中,Nemo 将吃到 k 只小虾。第二行包含一个实数 w,表示在你的成长计划中,Nemo 吃到的小虾的重量总和。接下来 k 行,每行 4 个数 t, x, y, s。表示在时刻 t,Nemo 在位置(x, y)处的小虾。其中 t, x, y 为实数,s 为整数。了为 s为保证验证程序的精度,所有实数建议至少输出到小数点后 6 位。在验证程序中,两个实数绝对误差不超过 10-4 时,即视为相等。【样例输入】5【样例输出】55 2 2 1【样例说明】在这个样例

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论