课件案例全国赛day

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【样例说明】在这个样例