NOI2008

今年的NOI试题

“AMD”杯


第二十五届全国信息学奥林匹克竞赛



NOI 2008


第一试


浙江绍兴
第 25届全国信息学奥林匹克竞赛第一试假面舞会 party

假面舞会


【问题描述】

一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。

今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择
一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具
的人。

为了使舞会更有神秘感，主办方把面具分为 k (k≥3)类，并使用特殊的技术将
每个面具的编号标在了面具上，只有戴第 i类面具的人才能看到戴第 i+1类面具
的人的编号，戴第 k类面具的人能看到戴第 1类面具的人的编号。

参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己
算出有多少类面具，于是他开始在人群中收集信息。

栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第 2
号面具的人看到了第 5号面具的编号。栋栋自己也会看到一些编号，他也会根据
自己的面具编号把信息补充进去。

由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信息
不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多
少类面具。由于主办方已经声明了 k≥3，所以你必须将这条信息也考虑进去。

【输入格式】

输入文件 party.in第一行包含两个整数 n, m，用一个空格分隔，n表示主办
方总共准备了多少个面具，m表示栋栋收集了多少条信息。

接下来 m行，每行为两个用空格分开的整数 a, b，表示戴第 a号面具的人看
到了第 b号面具的编号。相同的数对 a, b在输入文件中可能出现多次。

【输出格式】

输出文件 party.out包含两个数，第一个数为最大可能的面具类数，第二个数
为最小可能的面具类数。如果无法将所有的面具分为至少 3类，使得这些信息都
满足，则认为栋栋收集的信息有错误，输出两个-1。

【输入样例一】


6 5
1 2
2 3
3 4
4 1
3 5


【输出样例一】


4 4

【输入样例二】


3 3
1 2
2 1
2 3


【输出样例二】


-1 -1

【数据规模和约定】


50%的数据，满足 n ≤ 300, m ≤ 1000；
100%的数据，满足 n ≤ 100000, m ≤ 1000000。


“AMD”杯


浙江绍兴
第 25届全国信息学奥林匹克竞赛第一试设计路线 design

设计路线


【问题描述】

Z国坐落于遥远而又神奇的东方半岛上，在小 Z的统治时代公路成为这里主
要的交通手段。Z国共有 n座城市，一些城市之间由双向的公路所连接。非常神
奇的是 Z国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的
城市直接通过公路相连。Z国的首都是 Z国政治经济文化旅游的中心，每天都有
成千上万的人从 Z国的其他城市涌向首都。

为了使 Z国的交通更加便利顺畅，小 Z决定在 Z国的公路系统中确定若干条
规划路线，将其中的公路全部改建为铁路。

我们定义每条规划路线为一个长度大于 1的城市序列，每个城市在该序列中
最多出现一次，序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且，
每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有
公共部分。

当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出
发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的
城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首
都。

我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的
次数，而 Z国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明
显首都的“不便利值”为 0。小 Z想知道如何确定规划路线修建铁路使得 Z国的
交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不
便利值”达到最小。当然方案总数可能非常大，小 Z只关心这个天文数字 mod Q
后的值。

注意：规划路线 1-2-3和规划路线 3-2-1是等价的，即将一条规划路线翻转
依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不
属于另一个方案。

【输入格式】

输入文件 design.in第一行包含三个正整数 N、M、Q，其中 N表示城市个数，
M表示公路总数，N个城市从 1~N编号，其中编号为 1的是首都。Q表示上文
提到的设计路线的方法总数的模数。接下来 M行，每行两个不同的正数 ai、bi (1≤
ai , bi ≤
N)表示有一条公路连接城市 ai和城市 bi。输入数据保证一条公路只出现
一次。

【输出格式】

输出文件 design.out应包含两行。第一行为一个整数，表示最小的“不便利
值”。第二行为一个整数，表示使“不便利值”达到最小时不同的设计路线的方
法总数 mod Q的值。
如果某个城市无法到达首都，则输出两行-1。

【输入样例】


5 4 100
1 2
4 5
1 3
4 1

【输出样例】


1
10

【样例说明】

以下样例中是 10种设计路线的方法：

(1) 4-5
(2) 1-4-5
(3) 4-5, 1-2
(4) 4-5, 1-3
(5) 4-5, 2-1-3
(6) 2-1-4-5
(7) 3-1-4-5
(8) 1-4
(9) 2-1-4
(10) 3-1-4

【数据规模和约定】

对于 20%的数据，满足 N,M ≤ 10。
对于 50%的数据，满足 N,M ≤ 200。
对于 60%的数据，满足 N,M ≤ 5000。
对于 100%的数据，满足 1 ≤
N,M ≤ 100000，1 ≤
Q ≤ 120000000。

【评分方式】

每个测试点单独评分。对于每个测试点，第一行错则该测试点得零分，否则
若第二行错则该测试点得到 40%的分数。如果两问都答对，该测试点得到 100%
的分数。


“AMD”杯


浙江绍兴
第 25届全国信息学奥林匹克竞赛第一试志愿者招募 employee

志愿者招募


【问题描述】

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的
主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志
愿者。经过估算，这个项目需要 N天才能完成，其中第 i天至少需要 Ai个人。
布布通过了解得知，一共有 M类志愿者可以招募。其中第 i类可以从第 Si天工
作到第 Ti天，招募费用是每人 Ci元。新官上任三把火，为了出色地完成自己的
工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是
布布找到了你，希望你帮他设计一种最优的招募方案。

【输入格式】

输入文件 employee.in的第一行包含两个整数 N, M，表示完成项目的天数和

可以招募的志愿者的种类。
接下来的一行中包含 N个非负整数，表示每天至少需要的志愿者人数。
接下来的 M行中每行包含三个整数 Si, Ti, Ci，含义如上文所述。为了方便起

见，我们可以认为每类志愿者的数量都是无限多的。

【输出格式】

输入文件 employee.out中仅包含一个整数，表示你所设计的最优方案的总费
用。

【输入样例】

3 3
2 3 4
1 2 2
2 3 5
3 3 2


【输出样例】

14


【样例说明】

招募 3名第一类志愿者和 4名第三类志愿者。

【数据规模和约定】

30%的数据中，1 ≤
N, M ≤ 10，1 ≤
Ai ≤ 10；

100%的数据中，1 ≤
N ≤ 1000，1 ≤
M ≤ 10000，题目中其他所涉及的数据均
不超过 231-1。


NOI 2008


第二试


竞赛时间：2008年7月31日上午 8:00-13:00

题目名称奥运物流糖果雨赛程安排
目录 trans candy match
可执行文件名 trans candy match
输入文件名 trans.in candy.in match1.in~match10.in
输出文件名 trans.out candy.out match1.out~match10.out
每个测试点时限
1s 2s N/A
内存限制
128M 128M N/A
测试点数目
10 10 10
每个测试点分值
10 10 10
是否有部分分无无有
题目类型传统传统提交答案

提交源程序须加后缀

对于
Pascal语言 trans.pas candy.pas N/A
对于
C 语言 trans.c candy.c N/A
对于
C++ 语言 trans.cpp candy.cpp N/A

注意：最终测试时，所有编译命令均不打开任何优化开关


“AMD”杯


浙江绍兴
第 25届全国信息学奥林匹克竞赛第二试奥运物流 trans

奥运物流


【问题描述】

2008北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效率、
成功地举办奥运会，对物流系统进行规划是必不可少的。

物流系统由若干物流基站组成，以 1…N进行编号。每个物流基站 i都有且
仅有一个后继基站 Si，而可以有多个前驱基站。基站 i中需要继续运输的物资都
将被运往后继基站 Si，显然一个物流基站的后继基站不能是其本身。编号为 1的
物流基站称为控制基站，从任何物流基站都可将物资运往控制基站。注意控制基
站也有后继基站，以便在需要时进行物资的流通。在物流系统中，高可靠性与低

成本是主要设计目。对于基站 i，我们定义其“可靠性”R()i如下：

设物流基站 i有 w个前驱基站PP1,,..P，

2w 即这些基站以 i为后继基站，则基

站 i的可靠性 R(i)满足下式：

R()i=
Ck (

i+Σ(w) RP j)

j=1

其中 Ci和 k都是常实数且恒为正，且有 k小于 1。

整个系统的可靠性与控制基站的可靠性正相关，我们的目标是通过修改物流
系统，即更改某些基站的后继基站，使得控制基站的可靠性 R(1)尽量大。但由于
经费限制，最多只能修改 m个基站的后继基站，并且，控制基站的后继基站不
可被修改。因而我们所面临的问题就是，如何修改不超过 m个基站的后继，使
得控制基站的可靠性 R(1)最大化。

【输入格式】

输入文件 trans.in第一行包含两个整数与一个实数，N, m, k。其中 N表示基
站数目，m表示最多可修改的后继基站数目，k分别为可靠性定义中的常数。

第二行包含 N个整数，分别是 S1, S2…SN，即每一个基站的后继基站编号。

第三行包含 N个正实数，分别是 C1, C2…CN，为可靠性定义中的常数。

【输出格式】

输出文件 trans.out仅包含一个实数，为可得到的最大 R(1)。精确到小数点两
位。

【输入样例】


4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0
【输出样例】


30.00

【样例说明】

原有物流系统如左图所示，4个物流基站的可靠性依次为 22.8571，21.4286，

25.7143，10。
最优方案为将 2号基站的后继基站改为 1号，如右图所示。此时 4个基站
的可靠性依次为 30，25，15，10。

【数据规模和约定】

本题的数据，具有如下分布：

测试数据编号 N M
1 ≤ 6 ≤ 6
2 ≤ 12 ≤ 12
3 ≤ 60 0
4 ≤ 60 1
5 ≤ 60 N-2
6~10 ≤ 60 ≤ 60

对于所有的数据，满足 m ≤
N ≤ 60，Ci ≤ 106，0.3 ≤
k < k =" 1，2，3）分别表示事件的类型，分别对应三种事件：插入事件，" di =" -1)或向右(Di" di =" -1或" pi =" Ri" n =" 2k)个同学报名参加，因此第一轮后就会有" n="8时比赛的赛程表" a="1)。于是小" 2k =" n。" i =" 0.00。" p1="1-0.8="0.2," p2="0.8-0.528="0.272," p3="0.528。" 3 =" 2.328。"> our_ans，得 12分。

如果 your_ans < our_ans*d，得 1分。

否则得分为：

.
your _ ans .
our _ ans *d .

*8 +
2

..

.
our _ ans .
our _ ans *d .

【提示】

“数学期望”

数学期望是随机变量最基本的数字特征之一。它反映随机变量平均取值的大
小，又称期望或均值。它是简单算术平均的一种推广。例如某城市有 10万个家
庭，没有孩子的家庭有 1000 个，有一个孩子的家庭有 9万个，有两个孩子的家
庭有 6000个，有 3个孩子的家庭有 3000个，则该城市中任一个家庭中孩子的数
目是一个随机变量，它可取值 0，1，2，3，其中取 0的概率为 0.01，取 1的概
率为 0.9，取 2的概率为 0.06，取 3的概率为 0.03，它的数学期望为 0×0.01＋1×0.9

＋2×0.06＋3×0.03等于 1.11，即此城市一个家庭平均有小孩 1.11个。
本题中期望值的计算：假设小 Z在第一轮被打败的概率为 P1，第一轮胜利且
在第二轮被打败的概率为 P2, 前两轮胜利且在第三轮被打败的概率为 P3……，
那么小 Z的期望奖金为：

P1 * a1 + P2 * a2 + …+ Pk+1 * ak+1

【特别提示】

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