四 21
WC2010 重建计划
WC2010 能量场
WC2010 排序机
这可能是我的最后一份信息学竞赛解题报告。
三 16
问题简述
给定一个初始的排列P和M个轮换，每个轮换可以将排列P中的每个数值轮换为排列中的另一个数值，轮换后仍然是一个排列。求出从排列P到排列1,2,3,…,N至少要经过多少次轮换，输出一个方案。
问题分析
本题非常困难，好在是个提交答案题，可以看数据，然后针对每个数据设计合适的算法。不过在看数据之前，首先还是稍作一些转换，以便简化思维复杂度。本题中的“轮换”用了一种很别扭的转换方式（转换数值），与以往的习惯格格不入（轮换位置），因此要把它转化一下。用一个哈希表记录每个数值的位置，形成新的排列Ti就表示原序列中数i在第Ti位，例如样例中的4 3 1 2，转化后就是3 4 1 2，在转化后的序列上变换只用变换位置即可，这样就符合我们的习惯了（至少是我的习惯）。
接下来可以观察数据了。首先发现测试点1、2、3的N、M都很小，可以直接搜索求解。用迭代加深或者广搜即可拿到满分。
观察测试点4，N、M很大，没办法搜索了。但是发现所有轮换都是交换相邻两个元素，而且M=N-1，恰好囊括了N个元素所有相邻两对。这让我联想到冒泡排序的方法，由于冒泡排序每次交换的都是相邻两个元素，因此可以用来解决这个测试点。
测试点5的输入文件是最大的一个，主要是由于M相当大，而且一时没发现什么规律。不过突然发现M=N*(N-1)/2，令我联想到完全图顶点和边数的公式——是不是任意两个都可以交换呢？写程序判重以后发现果然是无重复的M个轮换，这意味着任意两个位置可以交换。因此我们可以从1到N逐个确定每个位置上的值。
Read the rest of this entry »
三 16
问题简述
给定一棵边上带权的树，求一个平均价值最大的简单路径。路径的平均价值定义为路径的带权长度与不带权长度的比值。
问题分析
在一棵树上直接找这样的路径是很困难的，因此我们考虑将问题分解。一个基本的想法是在树上分治，为保证对数级别的时间复杂度，必须使用基于点的剖分[1]。每次找到树的重心[2]作为根节点，然后将根节点的子树平均分为两部分，两部分共用根节点。对每一部递归求解，然后把这两部分合并。求树的重心的方法是随便找一个根，求出每个子树的大小，找到max{i.child.size,N-i.size}最小的i，i就是树的重心。重心可能有多个，找一个即可。
对于一个分治的局面，每一部分都是当前根节点的一些子树组成的森林，再加上根节点，所以每一部分仍然是一棵树。最优的路径可能在某一个分治的部分中，也可能跨过根节点在两个部分中。前者可以直接递归下去求解，重点是处理后者的情况。这时需要做的一个重要转化是二分答案，由于答案的范围是已知的，我们可以在答案的范围内二分答案的值A，然后把树上每一条边的权值都减去A。判断有解的方法也就变成了判断是否存在一条带权长度大于等于0的路径，继续转化就是，判断最长的带权路径的带权长度是否大于等于0。
Read the rest of this entry »
三 15
问题简述
能量场中有N个粒子，每个粒子都有一个质量m和结合系数c，两个粒子a,b合并时会产生mamb(ca - cb)的能量。(1)找出两个粒子相结合，使得产生的能量最大。(2)从中找出任意k个粒子排列成一个环，相邻两个粒子分别合并，使得总能量最大，产生负能量的粒子必须是环上连续的一段。
问题分析
乍一看这个问题的第一问好像很简单，枚举每对粒子即可，但是时间复杂度是O(N2)的，而且难以想到如何优化。第二问则更加困难，搜索、动态规划是肯定不行的，贪心、图论也难以找到建模方式。分析发现这个问题可以归约到一个0/1规划问题，如果没有特殊性将无法解决，而特殊性无非在于能量产生的公式，因此将目光聚焦到这个公式上，对公式进行一些变形：
- mamb(ca - cb)
- = mambca - mambcb
- = macamb – mbcbma
- 设xi=mici，yi=mi则原式
- = xa*yb – xb*ya
Recent Comments