国家集训队2004论文集胡伟栋

IOI2004国家集训小组论文胡伟栋第1页共10页，在冗馀度和算法优化冗馀度和算法优化长沙市长郡中学胡伟栋【摘要】【摘要】信息学比赛中，我们经常遇到冗馀度，但冗馀度是算法，程序效率不是信息学比赛， 我们经常遇到冗馀，冗馀导致算法、程序效率的不同程度降低：有些小，有些算法的复杂性大大提高。 本文同等程度的下降：有些是微不足道的，有些大大提高了算法的复杂性。 本文针对后者，举例说明了冗馀性对算法效率的影响及减少冗馀性的方法。 本文通过举例说明冗馀如何影响算法的效率以及如何减少冗馀。 【关键词】【关键词】【冗馀度】、算法优化冗馀度、算法优化【本文】【本文】在引言信息竞赛中，我们追求的目标之一是以最少的时间解决程序问题，即实现最高效率。 在实际生活中也需要同样的事情，高效率的人在竞争中往往占优势。 冗馀是指冗馀操作或重复操作。 冗馀是指冗馀操作或重复操作。 许多算法(如搜索、递归和动态规划)都具有冗馀性。 定义冗馀时，必须移除该算法的冗馀以使该算法最有效。 但是，要完全消除冗长性是困难的，使程序在绝对最小限度的时间内解决问题也是困难的，通常要退一步，把使程序在尽可能少的时间内解决问题变成目标。 从冗馀的定义来看，为了提高算法的效率，必须减少算法的冗馀处理来提高算法的效率。 要减少冗馀，在解决大量问题的过程中，必须不断探索和积累经验。 下面通过两个具体示例来研究冗馀如何影响算法的效率以及减少冗馀。 二二二整数分割整数分割2.1问题记述将正整数n分割为几个整数之和，使分割数成为二的非负整数幂形式。 询问有多少分割方案。 如果两个方案数量不同，则将其视为相同的方案。 例如，如果N=5，则5=1111115=11125=1主题源：由于可以分割成金凯原创IOI2004国家集训团队论文胡伟栋2页共计10页，所以有5个分割方案。 2.2粗略分析这个问题可以递归解决(为什么？ 让读者自己考虑_):，F i j把I分割成几个，其中最大的数量不超过2 j以下的分割总数。 则：1 0，1=Fj 2 ，01=F i，即将I分割为几个，其中最大数量不超过0 21=的分割方案只有一个：将I分割为I个1。 对于3I0和j0，F i j表示第一类：划分的最大数目恰好为2 j，其总数为2，ij； 第二类：分割的最大数小于2 j，其总数为，1F i j。 所以，2，1JFFJFJIJ=。 最后计算的目标是FN，M。 因为2Ji必须等于或大于0，所以2logji，并且1 iN 。 总时间复杂度为2 (log)O NN ，空间复杂度也为2 (log)O NN。 这种复杂性似乎已经很低了。 但是为了简化研究复杂性是更低还是2.3减少冗馀，首先处理n应当是2的整数的特殊情况，然后当n不应当是2的整数时，处理n应当是2的整数。 2.3.1当丹宁为2的整数乘以时的整数乘以时，设定为2MN=(M为非负整数)。 首先，为了更直观地进行讨论，所有，F i j对应于具有轴I、j作为纵轴的正交坐标系的各点，横轴为I的点被称为第I列的点，纵轴为j的点被称为第j行的点。(fij是第I列，第j行的点)如果点c是点a与点b之和，则边缘ac与bc接续(图a所示)。 这里所说的时空复杂性忽略了高精度的要素。 因为回答n达到10000000只有60位，所以这个数字比较小。 c为，F i j时，根据递归方程式，a、b分别为2，jjj，1fij。 IOI2004国家集训队论文胡伟栋第3页共10页，可以递归关系连接所有边，得到图b。 观察要计算的目标，fmm。 其中，2，=nmfmm与，1nmm的和，1 NMM为1 2，1 NMM与，2nmm的和，2 fnm为2 2，2 Mn mm与，3 fnm的和即使在图中可能需要很多点(图b中的d，e )的值可以看出，除去这些冗馀的点和边，最后仅保留可能影响目标点的点和边，图b为图c，图c为比图b简洁，计算的点数也变少了。 那么，究竟计算几个点呢？从图c可知，当j为最大，即jM=时，第j行仅计算一个3 ，F N M值即可.在1 JM=的情况下，第j行计算两个值3354 ，1fnm和，12nmm的I J A(2， jji ) 1F i j) C(，fij)12345678230图A (M=3，n=8)ijd1234568230图B (M=3 n=8)enij1234567820图C (M=3，N=8) IOI2004国家合宿队论文胡伟栋4页，共计10页，第2jM=时j行为4个值24nmm，22nmm，3 24nmm和，2 fnm由此可以推测，当jMk=时，需要第j行，并且仅计算2k个值。 这些这些计算的值分别为 2，(12)jkfj这2k个。 的双曲馀弦值。 这两个预测是否正确答案是肯定的，下面用归纳法证明： jM=时，第j行很明显只计算，F N M。 预计、在此时成立。 假定1jMk=成立，则第j行计算1 2，(12)jkfj此1k个。 当1 jjmk=0=时，因为第j行计算0 2， j Fj，所以根据递归方程，第j行计算00 2，2*2， j Fj，并使用0 (21)*2， j Fj来计算0 2*2， j Fj。 当计算jfj时，继续使用0 (22)*2，jj，直到最后计算所有0 *2，(12)xjxJX。 如果取所有0 ，则得出第j行计算哪个值。 *2， (12 )JK f xjx这2k个数，该公式与相同。 因此，我认为此时、还成立。 综合1和2，我认为、都是正确的。 由可知，图中实际有用的地方是23112222211mmn=个，但最初计算*NM个时，可知计算中的冗馀数远多于必须计算的数。 删除此冗馀计算可能会降低算法的时间复杂性() O N。 现在的问题是计算哪个点。用找出计算点是一种方法，但这里有两个巧妙的结论：在图中，计算点必定是最下面的几点。 的双曲馀弦值。 因为要计算，F i j，需要从递归方程式计算，1F i，计算，2F i j 之前计算，1F i，最后知道，0F i。因此，计算，F i j时，必须计算，F i j正下方的所有点，所以按图列计算的IOI2004国家集训队论文胡伟栋的第5页总共10页点必须是最下面的几点。 当Ti=X时，在第I列计算的点的个数Ti=X的二进制表现中，最后的二进制表现中最后的0的个数。 数数儿。 证明：假设I的二进制表示最后有Ti个0。 在j=Ti 1的情况下，2 | j i /，即，因为不存在整数，所以不需要从2 j i=、2、，F i j进行计算。 因而，第I列仅计算Ti个值即可。 综合一、二、命题成立。 这样，时间的复杂性降低到() O N也没有问题。 让我们来看看空间的复杂性。 不需要计算的数据都可以不分配内存，之前浪费了很多空间。 怎样才能不浪费呢？假设程序的实现时从外层循环小的一方向大的一方列举的I值、从内层循环小的一方向大的一方列举的j值的顺序，则对于，F i j使用的值为，F i j和2，jji， 2，JII是第j行求出点中最右侧的点，即当前已知的，F x j (x为非负整数)中x为最大的点(图中x为非负整数) 对于某个j，如果在求出的，F x j中x保存最大的要素，则认为有减少无用，如滚动排列那样减少空间的效果。 可以将空间复杂度设置为2 (log)ON。 2.3.2如果但不是2的整数乘方，那么对于2MNr=，其中122mmNinaaa，一个() noaaa，总时间复杂度为()