noip2006提高组解题报告及源程序.docVIP

NOIP2006 Solutions 2006届中国信息学奥林匹克联赛提高组解题报告 by FaLLeNs 问题一 能量项链/Energy 核心算法 动态规划 (原型 石子合并问题) 时间复杂度 O(n3) 空间复杂度 O(n2) 编码复杂度 50行 实测时间 0.1s 分析 记head[i]为第i颗能量珠的首标记，也同时是它前面那颗能量珠的尾标记。记录Energy[i,j]为从以Head[i]为首标记的能量珠开始顺时针数到以Head[j]为尾标记的能量珠为止所有能量珠组成的串合并后放出的最大能量。那么对于Energy[i,j]，若先合并从以Head[i]为首标记的能量珠开始顺时针数到以Head[k]为尾标记的能量珠为止的串，在合并以Head[k]为首标记的能量珠开始顺时针数到以Head[j]为尾标记的能量珠为止的串，然后将这两颗合并后的能量珠合并，放出的能量为Energy[i,k]+Energy[k,j]+Head[i]*Head[k]*Head[j]。也就是说，状态转移方程为Energy[i,j]=Max{Energy[i,k]+Energy[k,j]+Head[i]*Head[k]*Head[j]} (i=k=j (ij), ki or kj (i=j))。 计算Energy[i,j]时，只会用到含有能量珠数目比它少的串在数组中的值，所以可以以串的能量珠数目为顺序规划，即按照k|(k+i) mod n=j的顺序进行规划。 评论 如果枚举将能量项链变为串的开链位置，需要约n/2倍计算量，得到一个O(n4)的时间复杂度。这是不需要的。 一个较优的贪心近似算法是每次找首标记最小的能量珠与它前面的能量珠合并。对于NOIP中30%数据是正确的。一个典型的反例是n=4,Head={10,3,2,3}，贪心算法得到3*2*3+10*3*3+10*10*3=408，而最优解为10*3*2+10*2*3+10*10*3=420。 问题二 金明的预算方案/Budget 核心算法 动态规划 (原型 0-1背包问题) 时间复杂度 O(2knm), k=最大附件数 空间复杂度 O(n) 编码复杂度 50行 实测时间 0.1s 分析 使用邻接表记录每个主件的附件，将每个主件拆为四个物品：只买主件，买附件1，买附件2，买附件1和2，将问题转化为0-1背包问题。在动态规划中，忽略附件，对于每一个主件考虑上述四种情况，选取最优。当i是主件时状态转移方程为Priority[i,j]=Max{Priority[i-1][j],Priority[i-1,j-V[i,k]]+VP[i,k]} (0=k=3, 表示四种情况, VP为权值即价格与重要度的乘积)，当i时附件时Priority[i,j]=Priority[i-1,j]。 计算Priority[i,j]时，只与Priority[i-1,k] (k=j)有关。所以可以忽略数组的第一维，但是计算时(i确定)必须按j从大到小计算。由于V[i]都是10的整数倍，可以将n和V[i]都除以10，将时间复杂度和空间复杂度降低10倍，最后输出结果要乘以10。 问题三 作业调度方案/JSP 核心算法 模拟 时间复杂度 O(n2mt), t为工序时间上界 空间复杂度 O(nm2t) 编码复杂度 50行 实测时间 0.1s 分析 事件数共有nm个，而每个事件时间不超过t，所以整个作业过程时间不超过nmt。建立时间表Schedule[i,j]表示第i台机器第j时间是否空间。然后记录每个工件的已完成工序数Completed[i]和最后完成时间FinishTime[i]。每次读入一个工件查Complete得到需要进行的工序，然后在Schedule[Device[Complete[i]+1],*]中从FinishTime[i]+1起找第一段长度为Time[Complete[i]+1]的值为0的下标插入(所有下标赋值1，Complete[i]++,FinishTime[i]置为值为0的下标的最后一个。 由于每个工件的每个工序都是从上个工序的完成时间开始找，所以每个工件的所有工序加起来查找了不超过nmt个下标。所以时间复杂度为O(n2 mt)。 评论 不要看错题目。 问题四 2k进制数/Digital 核心算法 数学方法 (原型 计算组合数 数据结构 高精度整数) 时间复杂度 O(22kl) , l为最大数据长度 空间复杂度 O(2kl) 编码复杂度 100行 实测时间 0.8s 分析 考虑一个首位为r、位数为n且除最后一位每一位严格小于右边的2k进制数。它的种数等于从2k-(r+1)个自然数中选出n-1个升序排列。即Amount[