noi2试

noi2

1、 航空管制

【问题描述】

世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小X就因为航空管制，连续两次在机场被延误超过了两小时。对此，小X表示很不满意。 在这次来烟台的路上，小X不幸又一次碰上了航空管制。于是小X开始思考关于航空管制的问题。假设目前被延误航班共有n个，编号为1至n。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。起飞序列还存在两类限制条件：

第一类（最晚起飞时间限制）：编号为i的航班起飞序号不得超过ki; 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示航班a的起飞时间必须早于航班b，即航班a的起飞序号必须小于航班b的起飞序号。

小X思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

【输入格式】

输入文件plane.in第一行包含两个正整数n和m，n表示航班数目，m表示第二类限制条件（相对起飞顺序限制）的数目。

第二行包含n个正整数k1, k2, …, kn。

接下来m行，每行两个正整数a和b，表示一对相对起飞顺序限制(a, b)，其中1≤a,b≤n, 表示航班a必须先于航班b起飞。

【输出格式】

输出文件plane.out由两行组成。

第一行包含n个整数，表示一个可行的起飞序列，相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案，输出任意一个即可。

第二行包含n个整数t1, t2, …, tn，其中ti表示航班i可能的最小起飞序号，相邻两个整数用空格分隔。

【如何评分】

如果你的输出文件格式与题目要求不符，则得0分。即你的输出文件必须满足：第一行恰好包含n个整数，且第二行也恰好包含n个整数。

当你的输出文件格式与题目要求相符时： 如果仅第一行正确，获得对应测试点40%的分数； 如果仅第二行正确，获得对应测试点60%的分数； 如果两行均正确，获得对应测试点100%的分数。

【样例输入1】

5 5

4 5 2 5 4

1 2

3 2

5 1

3 4

3 1

【样例输出1】

3 5 1 4 2

3 4 1 2 1

【样例输入2】

noi2

5 0

3 3 3 5 5

【样例输出2】

3 2 1 5 4

1 1 1 4 4

【样例说明】

在样例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%数据：n≤10；

对于60%数据：n≤500；

对于100%数据：n≤2,000，m≤10,000。

【运行时限】

1秒。

【运行空限】

512M。

6

2、旅行路线【问题描述】

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只想知道可行的旅行路线总数mod 11192869的值。

noi2

【输入文件】

输入文件trip.in第一行包含两个正整数n, m。

第2行至第n+ 1行，每行有m个01整数，其中第i+ 1行第j个数表示Ti,j。

第n+ 2行有n*m个01整数，其中第i个数表示Li的值。

【输出文件】

输出文件trip.out仅包含一个整数，表示可行的旅行路线总数mod 11192869的值。

【输入样例】

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%的数据：m≤50，Li, Ti,j = 0或1。

【运行时限】

10秒。

【运行空限】

512M

2、 成长快乐

【问题描述】

Nemo是一条无忧无虑的小鱼，它的初始体重为w0。可爱的Nemo希望自己能够尽快地成长，因此需要吃尽量多的食物。Nemo最喜爱的食物是海里的小虾。

已知Nemo对食物的情况了解如下：大海里共有n只小虾，从1到n编号，其中编号为i的小虾的重量为wi。将大海看作一个X-Y坐标系，在0时刻编号为i的小虾所在的位置为(xi, yi)。小虾在大海中作匀速直线运动，其中编号为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希望你来帮助它制定一个成长计划，使得它吃掉的小虾重量总和尽量大。

【输入格式】

noi2

该题为提交答案型试题，所有输入数据nemo1.in~nemo10.in已在试题目录下。

对于每个数据，输入文件中第一行为五个实数w0, V, T, x0, y0。分别表示Nemo的初始体重、最大移动速度、时间限制以及Nemo在0时刻的位置。

第二行为一个整数n，表示大海中小虾的只数。

接下来n行，每行5个实数，包括wi, xi, yi, pi, qi，分别表示编号为i的小虾的重量、在0时刻的位置和速度向量。

【输出格式】

针对给定的10 个输入文件nemo1.in~nemo10.in，你需要分别提交你的输出文件nemo1.out~nemo10.out。

输出文件第一行包含一个整数k。表示在你的成长计划中，Nemo将吃到k只小虾。 第二行包含一个实数w，表示在你的成长计划中，Nemo吃到的小虾的重量总和。

接下来k行，每行4个数t, x, y, s。表示在时刻t，Nemo在位置(x, y)处吃掉了编号为s的小虾。其中t, x, y为实数，s为整数。

为保证验证程序的精度，所有实数建议至少输出到小数点后6位。在验证程序中，两个实数绝对误差不超过10-4时，即视为相等。

【样例输入】

5 1 6 0 0

1

5 2 2 0 0

【样例输出】

1

5

5 2 2 1

【样例说明】

在这个样例中，Nemo在时刻5在位置(2, 2)吃掉了1号小虾。其实Nemo到达(2, 2)的时间可以更早，但题中仅要求速度不超过V即可。

【特别提示】

由于测试程序将涉及浮点运算，可能存在精度误差，请确保每一个提交的答案文件都通过了nemo_check的检查。

请妥善保存输入文件nemo*.in 和你的输出nemo*.out，及时备份，以免误删。

本文来源：https://www.bwwdw.com/article/7zqi.html