第二十六届全国信息学奥林匹克竞赛.doc

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

NOI 2009
第一试

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

题目名称
变换序列
诗人小G
二叉查找树
目录
transform
poet
treapmod
可执行文件名
transform
poet
treapmod
输入文件名
transform.in
poet.in
treapmod.in
输出文件名
transform.out
poet.out
treapmod.out
每个测试点时限
1秒
30 秒
1 秒
测试点数目
10
10
10
每个测试点分值
10
10
10
是否有部分分
无
有
无
题目类型
传统
传统
传统

提交源程序须加后缀
对于Pascal语言
transform.pas
poet.pas
treapmod.pas
对于C 语言
transform.c
poet.c
treapmod.c
对于C++ 语言
transform.cpp
poet.cpp
treapmod.cpp

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

第26届全国信息学奥林匹克竞赛 第一试 变换序列 transform
变换序列
【问题描述】
对于N个整数0, 1, ……, N-1，一个变换序列T可以将i变成Ti，其中且。，定义x和y之间的距离。给定每个i和Ti之间的距离D(i,Ti)，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。
说明：对于两个变换序列S和T，如果存在p变换序列T，则输出文件中包含一行N个整数，表示你计算得到的字典序最小的T；否则输出”No Answer”（不含引号）。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。
【输入样例】
5
1 1 2 2 1
【输出样例】
1 2 4 0 3
【数据规模和约定】
20%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。

第2页　共7页
第26届全国信息学奥林匹克竞赛 第一试 诗人小G poet
诗人小G
【问题描述】
小G是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中, 注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。
小G最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。
【输入文件】
输入文件poet.in包含多组数据。
第一行包含一个整数T，表示诗的数量，接下来是T首诗，这里一首诗即为一组数据。每组数据的第一行包含三个由空格分隔的正整数N、L、P，其中N表示这首诗句子的数目，L表示这首诗的行标准长度，P的含义见问题描述。从第2行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成(ASCII码33~127, 但不包含 ‘-’)。
【输出文件】
输出文件为poet.out。
对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度，接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过1018，则输出"Too hard to arrange"(不包含引号)。每组数据结束后输出"--------------------"(不包括引号)，共20个"-"，"-"的ASCII码为45，请勿输出多余的空行或者空格。
【输入样例】
4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet
【输出样例】
108
brysj,
hhrhl
yqqlm,
gsycl.
--------------------
32
brysj, hhrhl.
yqqlm, gsycl.
--------------------
Too hard to arrange
--------------------
1000000000000000000
poet
--------------------
【样例说明】
前两组输入数据中每行的实际长度均为6，后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。
【评分方法】
本题设有部分分，当你的程序对于该测试点内每组数据计算得出的不协调度最小值都正确时，能得到本测试点70%的分数。在此情况下，若每组数据的排版方案都合法并且得出的不协调度都与输出的相等，则能得到本测试点剩下30%的分数。注意，输出格式错误可能会导致本测试点不得分。

【数据规模和约定】
总共10个测试点，数据范围满足：

测试点
T
N
L
P
1
≤10
≤18
≤100
≤5
2
≤10
≤2000
≤60000
≤10
3
≤10
≤2000
≤60000
≤10
4
≤5
≤100000
≤200
≤10
5
≤5
≤100000
≤200
≤10
6
≤5
≤100000
≤3000000
2
7
≤5
≤100000
≤3000000
2
8
≤5
≤100000
≤3000000
≤10
9
≤5
≤100000
≤3000000
≤10
10
≤5
≤100000
≤3000000
≤10
所有测试点中均满足句子长度不超过30。

第5页　共7页
第26届全国信息学奥林匹克竞赛 第一试 二叉查找树 treapmod
二叉查找树
【问题描述】
已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值都比它左子树结点的数据值大，而比它右子树结点的数据值小。
另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的儿子结点的权值要小。
已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。
一个结点在树中的深度定义为它到树根的距离加1。因此树的根结点的深度为1。
每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。
现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些结点的权值，但每次修改你会付出K的额外修改代价。你可以把结点的权值改为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是，整棵树的访问代价与额外修改代价的和最小是多少？
【输入文件】
输入文件名为treapmod.in。
输入文件第一行包含两个正整数N和K。N为结点的个数，K为每次修改所需的额外修改代价。
接下来一行包含N个非负整数，是每个结点的数据值。
再接下来一行包含N个非负整数，是每个结点的权值。
再接下来一行包含N个非负整数，是每个结点的访问频度。
所有的数据值、权值、访问频度均不超过400000。每两个数之间都有一个空格分隔，且行尾没有空格。
【输出文件】
输出文件名为treapmod.out。输出文件只有一个数字，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。
【输入样例】
4 10
1 2 3 4
1 2 3 4
1 2 3 4
【输出样例】
29
【样例说明】
输入的原图是左图，它的访问代价是1×1+2×2+3×3+4×4=30。最佳的修改方案是把输入中的第3个结点的权值改成0，得到右图，访问代价是1×2+2×3+3×1+4×2=19，加上额外修改代价10，一共是29。
数据值：1

权值：1

数据值：2

权值：2

数据值：3

权值：3

数据值：4

权值：4

数据值：1

权值：1

数据值：2

权值：2

数据值：3

权值：0

数据值：4

权值：4

【数据规模】
40%的数据满足N ≤ 30;
70%的数据满足N ≤ 50;
100%的数据满足N ≤ 70, 1 ≤ K ≤ 30000000。

第7页　共7页