信息学竞赛冬令营集

减少冗余与算法优长沙郡中学【对后者，举例说明冗余对算法效率的影响和如何减少冗余。冗余、算法优—引言下面就让我们通过两个具体的例子来研究冗余是如何影响算法效率的以及二整数拆分问题描述N2的非负整数幂的形N=5所以，54粗略分此题可用递推解决(为什么？请读者自己思考F[i,ji拆分成若干个数，其中最大的数不超过2j1°F[0,j]2F[i01i拆分成若干个数，其中最大的数不超过201的拆分方案ii1。3i>0,j>0F[i,j第一类：拆分成的最大数正好是2jF[i2j,j]；第二类：拆分成的最大数小于2jF[i,j1。F[i,jF[i2j,jF[i,j1]。F[N,M]。22 杂度是O(NlogN①，空间复杂度也是O(NlogN 减少冗N2N不2N2的整数幂的情况处理。N2的整数次幂N2M(M为非负整数)F[ij对应I为横轴，Ji的点称ijj行的点。F[i,jij行的点)若点C是点AB的和②，则连有向边AC和BC(A所示)①此处所讲的时空复杂度都忽略了高精度的因素。因为当N达到 时答案也只有60位，这个数字②当CF[i,j时，由递推方程，A、BF[i2j,j]F[i,j1J3 21

图 根据递推关系将所有的边都连出来，可以得到图BJ 1 图 F[NMF[N2MMF[0MF[NM1而F[NM1]

F[N2M1M1]

F[N,M

F[NM2]F[N2M2M2F[NM3的和……可以看出，图中有很多的点(如图BB简洁多了，要计算的点数也少多了。J321 图 CjjMj1F[NM

jM1j2F[NM1FNM12jM2J4FNM2]、FNM2]、F[3NM F[NM2]①当jMk时第j行要且只要计算2k个值②这些要计算的值是F[2j,j](12k这2k个1jMjF[NM]，这是显然的。猜想①、②此时都2jMk1jF[2j,j](12k1这jj1Mk，当

jF[2j,j0jF[2j,jF[2*2j',jF[2*2j',j0

F[(21)*2j',j

F[(21)*2j',j

00F[(22)*2j',j']F[x*2j',j'](1x200 取遍所有的0时，就可以得到第j行要计算哪些值，它们是F[x*2j',j'](1x2k这2k122M由①，图中实际有用的点是122223 2M1N2MN*M个，可见计算过程中的冗余数目远远大于必须计算的数目。如果去掉这此冗余的计算，算法的时间复杂度可能降到O(N)。③图中每一列要计算的点必然是最下面的若干个F[ijF[ij1，然后又必定要计算F[i,j2]……，直到要计算F[i,1]，最后F[i,0]已知。所以，如果要计F[i,jF[i,j④当i=X时，第i列要计算的点的个数TiX的二进制表示中最末的0的个iTi01j<=Ti2j|ii2j。因1iN1i2 2

2Mj，由②，F[i,jij=TiiTi2j>=Ti+1时，2j|i，即不存在整数，使i2j，由②，F[i,j不必计iTi个值。1°,2这样，时间复杂度降至O(N)jF[i,jF[i,j1F[i2j,jF[i,jj-1F[x,j1(x是非负整数)中xF[i2j,j是第jF[x,j(x是非负整数)x最大的点(D)jF[x,jx最大的那个元素即可，这样可以减少浪费，而且能起到类似滚动数组减少空间的效果。空间复杂度可以降到O(log2N)。J32F[i-1

图 N不是2的整数次幂N2Mr，其中2M1N2M，这时，计算的目标是F[NM1F[NMF[NM1F[N2MMF[N2MM0或者说不存在F[NM]F[NM1F[NM]仍然将F[i,j]对应到坐标系中连边去除其中的冗余得到图E(其中N=5)。添加F[r],F[r1],F[r2], ,F[1]共r列，令它们的值全为0(图F)。然后将所有的点向右平移r个单位，得到的就是类似N'2M的情况了，但从第0列J21012345J21012345IJ3J321-- - 12345J3J321012345678小探索中...三最大奖品价值问题描N+20N+11N级每级上都放着一个奖0M步(M≤N+1)N+1N+20级(即原地不动)K级(i级走到第i+Kii-K级)。数学模

,aN,aN

a0aN10 aN0对于一个M(MN)和K，从序列中找出一个子序列,Mai,ai,,M

0i0,iMNKi1i0K,Ki2i1K, ,KiMiM1K

ai 最M M粗略分

ip1ipip1ip因0ipip1K,Kip1ip0，所以Kip1ip1K，若将ip1ipip1为ip1ip1ip，即变换ip和ip1种方法调整，可以使i0i1因为除a0aN100走过的楼梯，所以进一步可以使i0i1F[i,j表示所选的第iaj所能得到子序列的和最大是多少。则F[i,j]

maxF[i1x]}ajjKxjN*MK，所以时间复杂度为O(NMK。这个减少冗当计算F[i,j1]jKx

F[i,

jK1x jK1x jKxjKx jKx

max{F[i1x]}jKx第一类方法：设计算F[ij1XF[i,jF[i1,jK1X

max{F[i1x]}，jKxF[i,j]时的最大值为max{XF[i1,j1O(1)即可转移；但当XF[i1,jK1时，就不得不计算max{F[i1x]}。复杂度为O(K)jKx对于这一类方法，当数据比较特殊时，如a1a2a3 aN，总时间杂度是O(NMK)第二类方法：用堆、线段树之类的数据结构优化。时间复杂度可降到O(NMlog2KF[i1F[i移的这一步。注意到，若abjF[i1bF[i1aF[ijF[i1b在，最大F[i1a](F[i1aF[i1bF[i1b而不F[i1a])F[i,jF[i1a——F[i1a

F[i1中所有要枚举的状态，且按标号(大值将是线性表中的第一个元素的值。但怎么实现呢？把线性表改造一下①jF[i1x](xjK都要删除(j1为增量的，最多将线性表的第一个元素删除)F[i1,j1插入F[i1,x]F[i1,j1]，要将F[i1,x]删除，这些元素都是性表的末尾，可F[i1x](1xn)O(1)O(NM)F[i-1]=(6352j16623635，533从线性表最后删除，564625