WC 2010 试题

第 27 届全国信息学奥林匹克冬令营 NOI Winter Camp 2010 竞赛时间：2010 年 2 月 6 日上午 8:00-13:00 题目名称 重建 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 能量场 排序机 目录 工贸企业有限空间作业目录特种设备作业人员作业种类与目录特种设备作业人员目录1类医疗器械目录高值医用耗材参考目录 rebuild efield sort 可执行文件名 rebuild efield 无 输入文件名 rebuild.in efield.in sort1.in~sort10.in 输出文件名 rebuild.out efield.out sort1.out~sort10.out 每个测试点时限 4 秒 1 秒 / 内存限制 128 M 128 M / 测试点数目 10 10 10 每个测试点分值 10 10 10 是否有部分分 否 是 是 题目类型 传统 传统 提交 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 附加文件 无 无 checker 提交源程序须加后缀 对于 Pascal 语言 rebuild.pas efield.pas 无 对于 C 语言 rebuild.c efield.c 无 对于 C++ 语言 rebuild.cpp efield.cpp 无 注意：最终测试时，所有编译命令均不打开任何优化开关。 第 27 届全国信息学奥林匹克冬令营 山东烟台 2010. 2. 6 重建计划 第 2 页 共 7 页 重建计划 【问题描述】 X 国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉 睫。X 国由 N 个城市组成, 重建小组提出，仅需建立 N-1 条道路即可使得任意两 个城市互相可达。于是，重建小组很快提出了一个包含 N-1 条道路的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，并满 足城市之间两两可达，他们还计算评估了每条道路 e 建设之后可以带来的价值 v(e)。 由于重建计划复杂而艰难，经费也有一定限制。因此，政府要求第一期重建 工程修建的道路数目为 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 作为新的方案，使得新方案中的道路平均价值 || )( S ev AvgValue Se   最大。这里 v(e)表示道路 e 的价值，|S|表示新方案中道路的条数。请你帮助 重建小组寻找一个最优方案。 注: 在本题中 L 和 U 的设置将保证有解。 【输入格式】 输入文件 rebuild.in 第一行包含一个正整数 N，表示 X 国的城市个数。 第二行包含两个正整数 L、U，表示政府要求的第一期重建方案中修建道路 数的上下限。 接下来的 N-1 行描述重建小组的原有方案，每行三个正整数 ai, bi, vi，分别 表示道路(ai, bi)，其价值为 vi。其中城市由 1…N 标号。 【输出格式】 输出文件 rebuild.out 仅包含一行，为一个实数 AvgValue，即最大平均价值。 小数点后保留三位。 【样例输入】 4 2 3 1 2 1 1 3 2 1 4 3 第 27 届全国信息学奥林匹克冬令营 山东烟台 2010. 2. 6 重建计划 第 3 页 共 7 页 【样例输出】 2.500 【样例说明】 输入的原方案如下图所示，新方案中选择路径(3, 1), (1, 4)可以得到的平均价 值为 2.5，为最大平均价值。 【数据规模】 对于 20%的数据，N ≤ 5 000; 另有 30%的数据，N ≤ 100 000, 原有方案恰好为一条路径(链); 对于 100%的数据，N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, vi ≤ 10 6。 1 2 3 4 1 2 3 第 27 届全国信息学奥林匹克冬令营 山东烟台 2010. 2. 6 能量场 第 4 页 共 7 页 能量场 【问题描述】 物理学家栋栋最近在研究一个能量场。在这个能量场中有 n 个粒子，每个粒 子都有两个属性：质量 m 和结合系数 c。 栋栋发现，在这个能量场中，每个粒子都有两极，N 极和 S 极。两个粒子相 遇时，符合“同极相斥，异极相吸”的原则，只能是一个粒子的 N 极和另一个 粒子的 S 极连接到一起。当质量为 ma，结合系数为 ca 的粒子 a 的 N 极与另一个 质量为 mb，结合系数为 cb 的粒子 b 的 S 极直接连接时，可以产生大小为 ma mb (ca – cb) 的结合能量。 请解决以下两个问题： 1. 在能量场的 n 个粒子中哪两个粒子直接连接的能量最大。 2. 栋栋发明了一种 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，能选择其中的任意 k 个粒子 p1, p2, …, pk，将 pi 的 N 极与 pi+1 的 S 极连接(1 ≤ i < k)， pk 的 N 极与 p1 的 S 极连接， 其中 p1, p2, …, pk 两两不同。k 可以在 1 至 n 中任意取值，如使用栋栋的这种方法 连接，选择哪些粒子可以得到最大的能量。 【输入格式】 输入文件 efield.in 的第一行包含一个整数 n，表示粒子的个数。 接下来 n 行，每行两个实数，第 i+1 行的两个实数表示第 i 个粒子的质量 mi 和结合系数 ci。(0< mi, ci <10 5 ) 【输出格式】 输出文件 efield.out 第一行包含两个整数 a, b，表示将粒子 a 的 N 极与粒子 b 的 S 极连接可以得到最大的能量。 第二行包含一个整数 k，表示第二问中要得到最大的能量需要多少个粒子。 第三行包含 k 个整数，表示 p1, p2, …, pk，即第二问中的最优方案。 【样例输入】 4 1.0 2.0 3.0 1.0 5.0 4.0 2.0 2.0 第 27 届全国信息学奥林匹克冬令营 山东烟台 2010. 2. 6 能量场 第 5 页 共 7 页 【样例输出】 3 2 3 1 3 2 【样例说明】 对于第一问，第三个粒子的 N 极与第二个粒子的 S 极连接，能得到的能量 为 5*3*(4–1) = 45。 对于第二问，顺次连接 1, 3, 2 号粒子，能量为 1*5*(2–4) + 5*3*(4–1) + 3*1*(1–2) = 32。 【数据规模】 10%的数据，n ≤ 8； 20%的数据，n ≤ 15； 40%的数据，n ≤ 1 000； 50%的数据，n ≤ 5 000； 100%的数据，n ≤ 50 000。 【评分标准】 此题可能有多解，如果用你的解产生的能量与参考答案的绝对误差或相对误 差小于 10–5，则得满分。否则不得分。 对于本题，每问的分数各占 50%。如果你的输出任何一问的格式或结果不正 确，则不得分；否则如果其中的一问正确，则得到该测试点 50%的分数；如果两 问都正确，得到该测试点 100%的分数。 第 27 届全国信息学奥林匹克冬令营 山东烟台 2010. 2. 6 排序机 第 6 页 共 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, …, pn)上的结果为： 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行，每行一个轮换，每一行的第一个数为 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 < c ≤ 1 000 000，得 1 分； 若 c > 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。 第 27 届全国信息学奥林匹克冬令营 山东烟台 2010. 2. 6 排序机 第 7 页 共 7 页 【如何测试你的输出】 在你的目录下有一个程序 checker 可以用来测试你的输出结果，你可以在终 端中使用以下命令来检查你的输出结果： ./checker N 其中 N 为测试点的编号，例如，要测试第 3 个测试点可以使用 ./checker 3 该程序会检测你的输出是否合法。对于合法的输出，checker 会输出“Right.” 否则会输出错误信息。 【样例输入】 4 2 4 3 1 2 2 4 2 3 1 3 4 【样例输出】 2 2 1