信息学集训队作业problems

1、第 27 届信息学冬令营NOI Wer C2010竞赛时间：2010 年 2 月 6 日上午 8:00-13:00提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关。对于 Pascal 语言rebuild.pasefield.pas无对于 C语言rebuild.cefield.c无对于 C+语言rebuild.cppefield.cpp无题目名称重建计划能量场排序机目录rebuildefieldsort可执行文件名rebuildefield无输入文件名rebuild.inefield.insort1.insort10.in输出文件名rebuild.outefield.outs

2、ort1.outsort10.out每个测试点时限4 秒1 秒/内存限制128 M128 M/测试点数目101010每个测试点分值101010是否有部分分否是是题目类型传统传统提交附加文件无无checker重建计划重建计划【问题描述】X 国的重创, 导致了的交通近乎瘫痪，重建家园的计划迫在眉睫。X 国由 N 个城市组成, 重建小组提出，仅需建立 N-1 条道路即可使得任意两个城市互相可达。于是，重建小组很快提出了一个包含 N-1 条道路的方案，并满足城市之间两两可达，他们还计算评估了每条道路 e 建设之后可以带来的价值 v(e)。由于重建计划复杂而艰难，经费也有一定限制。因此，要求第一期重建工

3、程修建的道路数目为 k 条，但需满足 L k U, 即不应少于 L 条，但不超过 U条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径，即所建设的 k 条路径可以 一个排列 e1 = (p1, q1), e2 = (p2, q2), , ek = (pk, qk), 对于 1 i k, 有(qi = pi+1)。重建小组打算修改他们的原有方案以满足要求，即在原有的 N-1 条道路中寻找一条路径 S 作为新的方案，使得新方案中的道路平均价值v(e)AvgValue eS| S |最大。这里 v(e)表示道路 e 的价值，|S|表示新方案中道路的条数。请你帮助重建小组寻找一个最优方

4、案。注: 在本题中 L 和 U 的设置将保证有解。【输入格式】输入文件 rebuild.in 第一行包含一个正整数 N，表示 X 国的城市个数。第二行包含两个正整数 L、U，表示数的上下限。要求的第一期重建方案中修建道路接下来的 N-1 行描述重建小组的原有方案，每行三个正整数 ai, bi, vi，分别表示道路(ai, bi)，其价值为 vi。其中城市由 1N 标号。【输出格式】输出文件 rebuild.out 仅包含一行，为一个实数 AvgValue，即最大平均价值。小数点后保留三位。【样例输入】421113234123第 2 页 共 7 页重建计划【样例输出】2.500【样例说明】输入的

5、原方案如下图所示，新方案中选择路径(3, 1), (1, 4)可以得到的平均价值为 2.5，为最大平均价值。1132243【数据规模】对于 20%的数据，N 5 000;另有 30%的数据，N 100 000,原有方案恰好为一条路径(链);对于 100%的数据，N 100 000, 1 L U N-1, vi 106。第 3 页 共 7 页能量场能量场【问题描述】物理学家栋栋最近在研究一个能量场。在这个能量场中有 n 个粒子，每个粒子都有两个属性：质量 m 和结合系数 c。栋栋发现，在这个能量场中，每个粒子都有两极，N 极和 S 极。两个粒子相遇时，符合“同极相斥，异极相吸”的原则，只能是一个

6、粒子的 N 极和另一个粒子的 S 极连接到一起。当质量为 ma，结合系数为 ca 的粒子 a 的 N 极与另一个质量为 mb，结合系数为 cb 的粒子 b 的 S 极直接连接时，可以产生大小为ma mb (ca cb)的结合能量。请解决以下两个问题：1. 在能量场的 n 个粒子中哪两个粒子直接连接的能量最大。2. 栋栋发明了法，能选择其中的任意 k 个粒子 p1, p2, , pk，将 pi 的N 极与 pi+1 的 S 极连接(1 i k)， pk 的 N 极与 p1 的 S 极连接， 其中 p1, p2, , pk 两两不同。k 可以在 1 至 n 中任意取值，如使用栋栋的这种方法连接，选

7、择哪些粒子可以得到最大的能量。【输入格式】输入文件 efield.in 的第一行包含一个整数 n，表示粒子的个数。接下来 n 行，每行两个实数，第 i+1 行的两个实数表示第 i 个粒子的质量 mi和结合系数 ci。(0 mi, ci 105)【输出格式】输出文件 efield.out 第一行包含两个整数 a, b，表示将粒子 a 的 N 极与粒子 b的 S 极连接可以得到最大的能量。第二行包含一个整数 k，表示第二问中要得到最大的能量需要多少个粒子。第三行包含 k 个整数，表示 p1, p2, , pk，即第二问中的最优方案。【样例输入】41.03.05.02.02.01.04.02.0第

8、4 页 共 7 页能量场【样例输出】3 231 3 2【样例说明】对于第一问，第三个粒子的 N 极与第二个粒子的 S 极连接，能得到的能量为 5*3*(41) = 45。对于第二问，顺次连接 1, 3, 2 号粒子，能量为1*5*(24) + 5*3*(41) + 3*1*(12) = 32。【数据规模】10%的数据，n 8；20%的数据，n 15；40%的数据，n 1 000；50%的数据，n 5 000；100%的数据，n 50 000。【评分标准】此题可能有多解，如果用你的解产生的能量与参考差小于 105，则得满分。否则不得分。的绝对误差或相对误对于本题，每问的分数各占 50%。如果你的

9、输出任何一问的格式或结果不正确，则不得分；否则如果其中的一问正确，则得到该测试点 50%的分数；如果两问都正确，得到该测试点 100%的分数。第 5 页 共 7 页排序机排序机【问题描述】轮换 g : (q1 q2 q3 qk)是一个从1, 2, , n到1, 2, , n的一一，它将q1数为 q2，q2为 q3，qk为 q1，而在 q1, q2, qk 中没有出现的整到自身。即：g(q1) = q2, g(q2) = q3, , g(qk) = q1，而对于在 q1, q2, qk 中没有出现的 x，g(x) = x。定义将轮换 g 应用到一个1, 2, , n的排列(p1, p2, , p

10、n)上的结果为： g(p1, p2, , pn) = (g(p1), g(p2), , g(pn)例如，对排列(3,1,5,4,2)应用轮换(1 3 4)进行变换后到排列(4,3,5,1,2)。给定1, 2, , n的一个排列(p1, p2, , pn)和一些轮换，请给出一种使用尽量少的轮换次数将该排列变换为(1, 2, , n)的方法。每个轮换可以使用多次。【输入格式】这是一道提交的试题，在你的目录下有 10 个输入文件 sort*.in。输入文件的第一行为两个整数 n 和 m，分别表示序列的长度和可使用的轮换个数。第二行有 n 个整数，是给定的初始排列(p1, p2, , pn)。接下来m

11、 行，每行一个轮换，每一行的第一个数为k，接下来k 个数为q1, q2, ,qk，表示轮换(q1 q2 q3 qk)。【输出格式】对于每一个输入文件，在目录下给出对应的输出文件 sort*.out。输出的第一行包含一个整数 c，表示所需的轮换次数。接下来 c 行，每行一个 1 至 m 的整数，表示使用的轮换。【评分标准】对于每个测试点，如果你没有输出、输出不合法或不能将排列变为指定的序列，则得 0 分。对于每个数据，设有三个评分参数 m1、m2 和 m3。若 c m1，得 10 分；若 m1 c m2，得 5 分。若 m2 c m3，得 3 分。若 m3 1 000 000，得 0 分；其中，对第 8 个点，m1 = 2 300，m2 = 2 400，m3 = 3 000；对第 9 个点，m1 = 69 000，m2 = 75 000，m3 = 100 000；对第 10 个点，m1 = m2 = m3 = 1 000 000。第 6 页 共 7 页排序机【如何测试你的输出】在你的目录下有一个程序 chec