规模化问题的解题策略

1、规模化问题的解题策略【关键字】 规模化 策略 算法【摘要】 问问题规模模化是近近来信息息学竞赛赛的一个个新趋势势，它意意在通过过扩大数数据量来来增加算算法设计计和编程程实现的的难度，这就向向信息学学竞赛的的选手提提出了更更高层次次的要求求，本文文试图探探索一些些解决此此类问题题的普遍遍性的策策略。开开始，本本文给出出了“规模化化”一词的的定义，并据此此将其分分为横向向扩展和和纵向扩扩展两种种类型，分别进进行论述述。在探探讨横向向扩展问问题的解解决时本本文是以以谋划策策略的“降维”思想为为主要对对象的；而重点点讨论的的是纵向向扩展问问题的解解决，先先提出了了两种策策略分解法法和精简简法，然然后结

2、合合一个具具体例子子研究“剪枝”在规模模化问题题中的应应用。问问题规模模化是信信息学竞竞赛向实实际运用用靠拢的的一个体体现，因因此具有有不可忽忽视的意意义。【正文】一 引引 论论（一）背背景分析析分析近年年来国际际、国内内中学生生信息学学竞赛试试题，可可以看出出信息学学竞赛对对于选手手的要求求已经不不再仅仅仅局限于于“算法设设计”，它同同时在编编程实现现方面加加强了考考察力度度，由侧侧重于考考察理论论知识转转向理论论考察与与实践考考察并重重。这一一命题宗宗旨的转转变，给给信息学学竞赛注注入了新新的机能能，为命命题者开开拓了另另一个领领域。其其一体现现有：试试题由精精巧型(这类试试题的难难度主要

3、要体现在在精妙算算法的构构造，属属于一点点即通的的类型)向规模模型发展展，从而而使得问问题的实实现复杂杂化。（二）对对“规模化化”的理解解规模一词词在字典典中的含含义是：事物所所具有的的格式、形式或或范围。在信息息学竞赛赛中，问问题的规规模具体体是指待待处理数数据量的的大小，通常可可以通过过一组规规模参数数(S1,S2, Skk)来表示示。例如如下列问问题1的的规模就就是(1000)，而问问题2的的规模是是(1000,1000)。问题1：求数列列的前1100项项之和。问题2：求1000*1100的的矩阵中中的各项项之和。问题3：求数列列的前110000项之和和。“规模化化”即扩展展问题的的规模

4、，它具体体是指增增加规模模参数的的个数或或扩大规规模参数数的数值值范围。我们知知道，如如果撇开开计算机机的硬件件、软件件等环境境因素，可以认认为一个个特定算算法的“运行工工作量”的大小小，只依依赖于问问题的规规模，或或者说，它是问问题规模模的函数数，程序序的执行行时间与与存储量量需求直直接受到到问题规规模的影影响。由由于种种种现行条条件的制制约，随随着规模模扩展，问题的的实际解解法集便便会缩小小，甚至至变为空空集，这这有时会会使问题题规模扩扩展后无无法用原原来小规规模时的的理想模模型解决决。如NNOI99生日蛋蛋糕一一题，理理论上可可以用动动态规划划的方法法求解，但因其其空间耗耗费过大大，多数

5、数人是用用搜索来来实现的的。从“规模模化”一词的的定义不不难看出出，它包包括横向向扩展和和纵向扩扩展。横横向扩展展是指增增加规模模参数的的个数，如由问问题1扩扩展至问问题2，即我们们通常说说的多维维化；纵纵向扩展展是指扩扩大规模模参数的的数值范范围，如如由问题题1扩展展至问题题3。下下文将分分别探讨讨这两类类问题的的一般性性解题策策略。二 横向扩扩展问题题的解题题策略（一）构构造策略略的思想想横向扩展展问题一一般具有有维数高高、难于于构想的的特点，所以谋谋划解决决这一类类问题的的策略，通常采采用“降维”1的思想想：分析析低维问问题，找找到解法法，推广广至高维维的情况况。下面我们们就来看看一个具

6、具体例子子。 问题一一：对于于一个nn维体PP(SS1,TT1),(S22,T22)，(Snn,Tnn), Sii、Ti (i=1.n)均均为整数数，我们们定义其其阶积=(T11-S11) *(T22-S22)*(TTn-SSn)，并称(Ti-Si)是P的的一个要要素i。如果存在在另一个个n维体QQ(SS1,T1),(S2,T22)，(Snn,TTn),使使得SiiSi(i=11.nn),且且TiTi(ii=1.n), SSi、Ti (ii=1.n)也是整整数，则则称Q是是P的子子n维体。现给定一一个n维体(0,AA1),(0,A2)，(0,An),求它它所有子子n维体的的阶积和和。问题分分析

7、：如果泛泛泛地从nn维体入入手，会会觉得无无所适从从，根据据要求“所有子子n维体的的阶积和和”，我们们可以枚枚举所有有的子nn维体，其时间间复杂度度高达OO(m22n)（其中中m表示AAi(ii=1.n)的一般般规模），效率率不高的的主要原原因是数数学模型型不够抽抽象，而而好的数数学模型型是建立立在问题题本质基基础上的的。所以以说，如如果我们们对问题题缺乏认认识或认认识不深深，就不不可能高高效地解解决它。这就是是笼统的的考虑横横向扩展展问题的的弊病。下面我们们根据上上文提到到的“降维”思想来来解决此此题。第一步：降低问问题的规规模。我们先从从简单模模型入手手，来看看一看nn=1时时的情况况，我

8、们们把一维维体（0，AA1）体现在在在下图图所示的的一根数数轴上，这里不不妨把一一维体看看成一条条线段,其阶积积就是线线段的长长度。0 1 2 33 4 AA1-11 AA1第二步：在低维维问题中中求找规规律。试想把长长度相同同的子线线段归类类统计，那么对对于长度度为L的的线段(s,ss+L)：s+LLA1 sA1-L 又又s0，0ssA1-L ，这这样的子子线段共共有A11+1-L条。所以，一一维体（(0,A1)）的的所有子子一维体体的阶积积和为i*(A1+1-ii)i=11.AA1，设为FFg(AA1)。第三步：将规律律推广至至高维问问题。我们将模模型稍加加推广，看看nn=2时时的情况况。

9、这时时我们可可将二维维体看成成一个矩矩形，其其阶积就就是矩形形的面积积。 yy (AA1,AA2)单位矩形形(A2-1)个个宽为22的单位位矩形带带 xx (0,00) 在上上图中，我们把把一个矩矩形嵌入入平面直直角坐标标系。这这里我们们按照子子矩形不不同的长长(x轴上上的距离离)、宽(y轴上上的距离离)来统计计。我们先提提取矩形形中一个个宽为11的单位位矩形带带(如上图图的阴影影部分)，然后后讨论矩矩形的长长。根据据解决一一维体时时的规律律，我们们知道在在这个单单位矩形形带中长长为L的的矩形共共有A11+1-L个，所以在在单位矩矩形带中中，所有有子矩形形的面积积和为FFg(AA1)。由由于宽

10、为为1的单单位矩形形带在原原矩形中中共有AA2个，所有宽宽为1的的子矩形形的面积积之和为为1*AA2* Fg(A1)。同理，所所有宽为为2的子子矩形的的面积之之和为22*(A2-1)*Fg(A1)，因此此所有宽宽为W的子矩矩形的面面积之和和为W *(A2+1-W)* Fgg(A11)。由由此可知知二维体体所有子子二维体体的阶积积之和是是Fg(A2)* Fgg(A11)。逐步推广广，可以以得知求求n维体体（(00,A1),(0,A2)，(0,An)）所所有子nn维体的的阶积和和为Fgg(A11)* Fgg(A22)* Fg(An)。其中中， Fg(a) =(1+22+a)+(1+2+a-1)+(

11、1) = eq o(sdo-8(),sddo 00(),sddo 88() (a+1)aa+a(a-11)+(a-11)(aa-2)+2= eq o(sdo-8(),ssdoo 0(),sddo 88() (a+2)(a+11)a-(a+1)aa(a-1)+(a+1)aa(a-1)-a(aa-1)(a-2)+66-0 = eq o(sdo-8(),ssdoo 0(),sddo 88()a(a+1)(a+22) 至此，问问题得到到圆满解解决，时时间复杂杂度已经经降到OO(n)，足够够满足维维数高的的情况。（二）小小 结结当然了，大多数数横向扩扩展问题题最终并并不能如如此轻松松地解决决，实际际竞赛

12、中中的问题题是非常常复杂的的，上面面列举的的例子没没有涉及及其他方方面的知知识点，是为了了集中说说明具体体如何运运用“降维”思想来来分析问问题。横横向扩展展问题的的难度主主要体现现在思维维上，所所以我们们应当从从低维的的简单情情况入手手，通过过挖掘低低维问题题与高维维问题的的相通之之处来寻寻找规律律，找到到规律后后不能机机械地推推广到高高维模型型，要注注意灵活活、变通通，真正正使它发发挥作用用。三 纵向扩扩展问题题的解题题策略（一）分分解法问题二：求正整整数N和M之间具具有最多多真因子子的数。本题中中的真因因子是这这样定义义的：如如果RP而且且R能整整除P，我们就就称R是是P的真真因子，对于特

13、特殊整数数1，我我们认为为1是11的真因因子。参数范围围：1NM999999999999；M-N99999999；时限：110s。我们很容容易得到到下列两两个方法法：顺序查查找法：依次统统计规定定范围内内的各整整数的真真因子个个数，记记录最优优解。由于，分分解质因因数的算算法时间间复杂度度为平方方根级的的，因此此这个算算法的时时间复杂杂度为OO(mm-n)*m00.5)。标号法法：枚举举不同的的因数，标记它它们的倍倍数。如果不仔仔细分析析，会认认为两种种方法的的算法时时间复杂杂度一样样，实际际上后者者的时间间复杂度度是0(m-n)*(1+1/22+1/3+1/m0.5)，还还不到OO(mm-n

14、)*logg2m0.5)x表示示x,x+11)间的的整数。证明明如下：先用数学学归纳法法证明11+1/2+11/3+1/44+1/5+1/(2n-1)n。当n=11时，左左边=11，右边边=n=1；111，不不等式成成立。假设当nn=k时时，不等等式成立立，则有有 11+1/2+11/3+1/44+1/5+1/22k-1k 现证证明n=k+11时，不不等式依依然成立立，1/22k+1/(2k+1)+1/(2k+2)+1/(2k+1-1)1/22k+1/22k+1/22k=(2kk+1-1-2k+1)/2kk=11+11/2+1/33+1/22k-1+1/22k+1/(2k+1)+1/(2k+1

15、-1)k+1 即即 1+1/22+1/3+11/4+1/55+1/22k+1-11k+1故命题成成立。所以，11+1/2+11/3+1/44+1/5+1/nlogg2n方法二之之所以在在时间复复杂度上上大有降降低，是是因为它它采用了了“空间换换时间”的模式式，由于于在标号号的全过过程中必必须保存存当前各各整数的的真因子子个数，因此空空间复杂杂度是00(m-n)，从参数数范围可可知，实实际情况况下无法法满足这这一需求求。它仅仅仅停留留在理论论基础上上，无法法用程序序实现。方法一一虽然空空间耗费费小，具具有可行行性，但但时间耗耗费却难难以满足足要求。于是我我们得到到：分段统统计法：将给定定区间分分

16、成不重重复且不不遗漏的的若干个个子区间间，然后后按方法法二统计计。 由于于方法一一每次处处理单一一元素，因此时时间耗费费高，方方法二将将所有元元素统一一处理，因此空空间需求求大，而而方法三三则综合合前两种种方法的的优点，在充分分利用空空间的情情况下，得到较较高的时时间效率率。方法三实实质就是是分解法法的应用用，由此此我们将将“分解法法”定义如如下：以一定的的算法为为原型，将大规规模的问问题分解解成若干干个不遗遗漏且尽尽量不重重复的相相对独立立的子问问题，使使得所有有子问题题解集的的全集就就是原问问题的解解集。分解法的的原理和和适用范范围：解决某些些纵向扩扩展问题题的时候候，常常常会出现现理论需

17、需求与实实际承受受能力之之间的“矛盾”，它主主要体现现在时空空需求互互相制约约的关系系上。如如本题中中的时空空关系可可以用下下图所示示的曲线线（双曲曲线的某某一支的的一部分分）来表表示，其其中曲线线的两个个端点分分别代表表方法一一与方法法二的时时空需求求。这时时若把问问题分解解成若干干规模较较小的子子问题，套用原原有的算算法解决决，就能能有效地地中和时时空需求求的矛盾盾。通常常，我们们以实际际空间承承受能力力作为划划分子问问题的规规模标准准，这样样才能令令时间效效率得到到最大提提高。下下图中，虚线位位置表示示实际空空间承受受能力的的上限，它与曲曲线的交交点就是是时空需需求分配配的最优优方案。时

18、间 （方法一一，空间间耗费趋趋近于零零） （方方法二，时间耗耗费最小小） 实实际可承承受空间间 空间间（二）精精简法我们对“精简法法”定义如如下：忽略问题题的表面面因素，只提取取具有实实质性联联系的特特殊信息息，以节节省空间间适应问问题的规规模。下面我们们结合一一个具体体例子说说明这一一解题方方法： 问题三三：最长长词链问问题。给定一个个仅包含含小写字字母的英英文单词词表，其其中的每每个单词词包含至至少1个个字母，至多775个字字母，且且按字典典顺序由由小到大大排列（不会重重复）。所有单单词所含含的字母母个数总总和不超超过2,0000,0000个。如果在一一张由一一个词或或多个词词组成的的表中

19、，每个单单词（除除最后一一个）都都被其后后一个单单词所包包含（是是其前缀缀），则则称此表表为一个个链。现要求从从单词表表中找到到一个包包含单词词数最多多的最长长词链。问题分分析问题的的实质是是在一定定的序列列中，求求找相邻邻元素（字串）间存在在特定关关系（包包含）的的最长子子序列。解决这这类问题题，通常常会用到到动态规规划的办办法。这这在求“数列的的最长非非降子序序列”和IOII999隐藏藏的码字字一题题中都有有所运用用。我们令nnum(i)表表示以第第i个单词词为链尾尾的最长长词链，则num(i)=maxxnumm(j)+1ji，且单单词j是单词词i的前缀缀所以，空空间复杂杂度为OO(n)n

20、为所包包含的单单词个数数，本本题的数数据量过过大，显显然无法法满足这这一存储储量需求求。仔细考虑虑“字典顺顺序”和“前缀”的关系系可以得得出这样样的结论论：两个个单词ww1、w2，如如果w22包含w1，且且有一个个单词ww3满足足，w11w33，w3w2，那么ww3必定定包含ww1。简简证如下下：令w2=L1L2L3.LLLW2，w3=L1L2L3.LLWW3，则w1=L1L2L3.LLLW1( LLi或Li为字母母)。假设w33不包含含w1，由由于w11w2，这与ww3ww2矛盾盾，因此此假设不不成立。所以某个个单词的的(单词表表中存在在的)前缀，必定被被其前驱驱单词所所包含或或者就是是其前

21、驱驱单词。于是我我们可将将单词的的所有前前缀(每个单单词也可可视为自自身的前前缀)标记出出来，来来为后面面的单词词传递信信息。如如下表：i；innt；inttegeer；intternn；intternnet；integerinterninternet首先，ii和intt被标记记为后继继单词iinteegerr的前缀缀，待读读入单词词intternn后，我我们只需需将单词词inttegeer与intternn比较，就得出出了它的的前缀词词链i和intt，最后后处理iinteerneet，得得出上表表中的最最长词链链为i；intt；intternn；intternnet。这样问题题的空间间复杂度

22、度就由OO(n)降低至至常量阶阶O(1)。下面面我们再再来分析析两种方方法的时时间复杂杂度，如如果以对对两两单单词间的的比较作作为基本本运算的的原操作作，则动动态规划划方法的的时间复复杂度为为O(nn2)，后者者的时间间复杂度度仅为OO(n)。我们们发现，两种方方法不存存在时空空需求上上的制约约关系，因此分分解法便便无“用武之之地”了。动动态规划划的方法法尽管在在求“数列的的最长非非降子序序列”中得到到了很好好的效果果，但却却不适应应本题，主要基基于这几几个原因因：字串的的存储比比数列元元素复杂杂，使得得空间耗耗费大；字串的的包含关关系比数数列元素素的大小小关系复复杂，使使得时间间耗费大大；单

23、词表表的元素素存在有有序性，使得我我们能够够根据问问题良好好的特性性设计最最为适用用的算法法。方法法二巧妙妙抓住了了两两元元素（单单词）间间的内在在联系，提炼出出了问题题的关键键，使得得处理对对象明确确化。精简法的的适用范范围：处理对象象的存储储空间大大，操作作比较复复杂(例如对对字符串串的操作作)，这样样的元素素间往往往存在一一定的特特殊关系系，于是是我们可可以仅仅仅提取问问题的脉脉络，而而实际的的元素能能够附着着于其上上，这就就将看似似凌乱孤孤立的元元素转化化成了具具有一定定逻辑关关系的结结构。其实，多多数人对对“精简法法”并不陌陌生，大大家在处处理011串时，常常会会把它转转化为对对应的

24、十十进制数数，使得得离散的的元素构构成了线线性结构构，这同同样也是是精简法法的一大大应用。精简法的的特点：精简法在在于抓住住问题的的本质，升华元元素的内内在联系系，淡化化元素的的孤立性性，将大大规模的的数据抽抽象成简简单、明明了的关关系，使使得问题题更易于于描述，实际操操作更加加简化。因此，精简法法针对性性强，设设计算法法时没有有固定模模式可套套，需要要具体问问题具体体对待。（三）巧巧用剪枝枝统计问题题是纵向向扩展问问题的一一大组成成部分，由于这这类问题题大多可可以采用用时间复复杂度为为多项式式阶O（nk）的算算法解决决，难度度不大，所以长长久以来来难以在在大赛中中显露头头角。近近来，命命题者

25、通通过扩大大统计问问题的规规模来增增加其难难度，于于是，统统计问题题便开始始活跃于于重大的的信息学学竞赛中中，如NNOI97的的卫星星覆盖，IOOI98的的图形形周长。剪枝就是是通过某某种判断断，筛减减掉一些些不必要要的计算算过程。它源于于搜索算算法，好好的剪枝枝条件，往往能能够极大大提高搜搜索的时时间效率率。然而而，由于于多项式式阶的算算法通常常被视为为有效算算法，因因而很少少有人问问津剪枝枝条件，甚至认认为那起起不了多多大作用用。那么么到底剪剪枝的应应用对于于统计问问题有多多大的作作用呢？还是让让我们先先来看一一个具体体例子吧吧。问题四：IOII999机场场跑道。试题简述述：在一一个数字字

26、矩阵中中求解一一个最大大数与最最小数差差不超过过阈值CC的面积积最大的的子矩阵阵。记录下下每行中中包括首首元素在在内的下下限一定定的最大大线性区区域长度度，然后后查找下下限一定定的面积积最大区区域。(为方便便讨论，在示意意图中行行、列的的排列按按从上至至下，从从左至右右的顺序序) 38 38 33 39 39 40 39 39 39 40 41 38 36 39 39 39以左图的的一个44*4的的矩形为为例（CC=4）： 从（11,1）格开始始，下限限为366（上限限为366+C）的线性性区域可可延伸至至（1,2）格格；同理，从从（2,1），（3,1），（4,1）格格开始，下限为为36的的线

27、性区区域分别别可延伸伸至（22,4），（33,2），（44,4）格。 所以下下限为336的面面积最大大区域为为（1,1,44,2）。我们注意意到，统统计每行行的最大大线性区区域时，由于必必须包括括首元素素，因此此下限值值与首位位元素值值不会超超过C。由于CC的取值值范围是是0,10，空间间需求可可以满足足，该算算法具有有可行性性，其算算法复杂杂度为OO(uvv2C)。由于于u、v的上限限是7000，尽尽管试题题规定的的最大时时限长达达一分钟钟，仍然然无法满满足这一一时间耗耗费。将矩阵阵进行横横向压缩缩，得到到一系列列单位区区域，然然后求最最长的连连续单位位区域。我们可以以得到如如下算法法：1

28、确定定西界限限；2 确定东东界限（西界限限+1000）； 3 对对从西界界限至东东界限的的每个单单位区域域进行统统计；4 确确定北界界限5 找到到最小的的南界限限；可以看出出，上述述算法的的时间复复杂度是是O(1000uv2)。如果从时时间复杂杂度来看看两种方方法，前前者肯定定比后者者好。但但如果对对于后者者加上好好的剪枝枝条件，结果就就不一样样了。38383339394039393940413836393939由于我们们求找面面积最大大的矩形形区域会会不断更更新当前前的最优优值，所所以，如如果某次次计算所所能得到到的最大大面积不不超过当当前的最最优值，则这样样的计算算毫无意意义，可可以省略略

29、。3838333939403939394041383639393938383339394039393940413836393939我们仍然然以原来来4*44的矩形形为例，以上三三个矩形形中分别别用粗线线条框出出了西界界限为11，东界界限为22、3、4时的的面积最最大区域域。我们们可以发发现南北北界限的的差别呈呈递减趋趋势，事事实上，这并不不是偶然然的，可可以用反反证法证证明，西西界限一一定，而而东界限限逐步扩扩展，也也即矩形形的宽度度增加时时，最大大面积矩矩形区域域的长度度是（非非严格）递减的的。我们令MMax_widdewwno,enoo表示示东西界界限为eeno和和wnoo时的最最大区域域

30、长度，那么Maax_wwideewnno,eenoMax_widdewwno,enoo-1。所以以我们可可以得到到下列两两个剪枝枝条件：If 最大宽宽度（MMin1000,u）* Maxx_wiidewnoo,enno-11当当前最大大面积 Thenn 扩扩展西界界限； If (eeno- wnno+11)* Maxx_wiidewnoo,enno-11当当前最大大面积 Thenn 扩扩展东界界限；下面我们们就将方方法一（lannd_11.paas）、方法二二（laand_2.paas）及及结合剪剪枝条件件后的方方法二（lannd_33.paas）进进行测试试时间的的对照： 输入数数据 数据规

31、规模 (UU,V,C)运 行 时 间间Landd_1.passLandd_2.passLandd_3.pass120，220，000.055s0.055s0.005s230，441，50.055s0.499s0.005s3100，1000，20.222s0.944s0.111s4100，5000，71.266s2.200s0.900s5300，3000，1009.233s10.333s2.477s6500，4000，10020.999s98.552s7.255s7600，5000，51.544s25.773s4.899s8700，7000，999.889s56.887s9.788s9700，7

32、000，100168.85ss16955.933s34.112s（运行环环境：ppenttiumm 1666MHHz/166MB）注：数据据是按规规模从大大到小进进行排列列的。测试结果果分析：除数据据7的运运行时间间与数据据规模不不相称外外，程序序一的运运行时间间与数据据规模相相对稳定定，那主主要是由由于数据据7中相相邻正方方形的高高度差大大多大于于阈值CC。所以以O(uvv2C)是本算算法的平平均时间间复杂度度，它能能够较为为准确地地反映其其时间耗耗费。对于规规模递增增的数据据，程序序二的运运行时间间波动很很大，尤尤其是数数据8与与数据99，两数数据规模模相差无无几，而而运行结结果却大大相径

33、庭庭。这说说明了OO(1000uv2)仅仅是是算法最最坏情况况下的时时间复杂杂度。由由于程序序二的实实际时间间耗费对对于数据据规模的的依赖性性大，因因此难以以用时间间复杂度度较准确确地反映映。剪枝效果果分析：一旦确定定剪枝条条件，每每次统计计都会执执行一次次判断操操作，所所以不精精准的剪剪枝会带带来很大大的负面面影响，再则剪剪枝条件件的效果果常常被被认为存存在很大大的偶然然性。所所以它常常常被人人们冷落落。在上表中中，相对对于程序序二，程程序三的的运行速速度大大大提高，且普遍遍优于程程序一，对比说说明剪枝枝条件还还是起到到了很好好的筛减减作用。从其运运行时间间中，我我们还能能够大致致看出数数据

34、规模模，尽管管我们并并不能精精准地估估计出剪剪枝条件件的效用用到底有有多大，但这一一相对稳稳定性足足以说明明，使用用优秀的的剪枝条条件或者者综合使使用多方方面的剪剪枝条件件，收益益良好也也就是“偶然”中的必必然了。尽管剪剪枝不能能降低算算法的时时间复杂杂度，但但却对降降低实际际时间耗耗费有着着非同小小可的作作用。尤尤其是规规模化问问题，时时间耗费费大，如如果注意意分析问问题，找找到约束束信息，必将起起到事半半功倍的的效果。（四）小小 结结由于纵向向扩展问问题具有有很大的的灵活性性，很难难像多维维化问题题那样总总结出一一个统一一的谋划划策略的的思想，也难以以归纳出出较为完完整的策策略集，以上仅仅

35、仅是我我根据平平时练习习的经验验总结出出的自认认为有一一定推广广意义的的一些策策略，其其中也提提到了剪剪枝在纵纵向扩展展问题中中的应用用，尽管管它不是是一个具具体的策策略，但但对于规规模化问问题也有有普遍意意义，这这已经在在上文中中有所提提及。总总而言之之，我们们研究各各种策略略的目的的是一致致的，那那就是要要有效地地解决问问题。相相信通过过不断的的学习，并与其其他同学学以及教教练们进进行交流流探讨，一定会会探索出出更多，更具价价值的策策略。四 结 语语我们知道道，无论论算法如如何优化化，所解解决的问问题规模模终究是是有限的的，因此此解决规规模化问问题时，首先应应明确问问题的实实际规模模，然后

36、后量“体”裁“衣”，设计计适用的的算法。有时题题中还会会对问题题规模加加上了一一定的限限制条件件，例如如IOII999隐藏藏的码字字中，文本的的最大长长度为11,0000,0000，而“右侧最最小”覆盖序序列的总总数却不不超过110,0000个个，这就就使得问问题的实实际规模模大大降降低。所所以，审审好题是是解决规规模化问问题的第第一步。 我们在在信息学学竞赛中中所解决决的问题题都是经经过实际际问题理理想化后后的产物物，而在在现实生生活中，真正需需要处理理和解决决的是很很大规模模的数据据量，这这就是我我们现在在涉足规规模化问问题的一一大现实实意义，同时规规模化问问题也向向我们提提出了更更高层次

37、次的要求求。值得得注意的的是，规规模化问问题固然然重要，但它并并不是空空中楼阁阁，它是是建立在在小规模模问题基基础上的的，因此此，想要要很好地地解决规规模化问问题，必必须从基基础做起起，这样样的道理理也不只只是适应应于信息息学竞赛赛的。既既具备扎扎实的理理论基础础，又具具有实干干本领和和创新精精神，是是时代对对于跨世世纪青年年的基本本要求，也是我我们不息息奋斗的的目标。【附录】本文提到到的“降维”是一种种谋划策策略的思思想，与与通常意意义上的的降维一一定区别别。【程序】1由于枚枚举法效效率太低低，因此此仅给出出有效算算法的程程序。proggramm obbjecct;typee noode=r

38、eccordd存储储高精度度整数 vv:arrrayy1.1000 of lonnginnt; llastt:inntegger; endd;var n,i:iinteegerr; a:arrray1.10 off inntegger;存储储n维体的的信息 toot:nnodee;阶积和和procceduure reaadn;读入入n维体的的信息var i:iinteegerr; f:ttextt;begiin asssiggn(FF,iinpuut.ttxt);rreseet(FF); reeadlln(FF,n); foor ii:=11 too n do reaad(ff,ai); cl

39、losee(f);end;funcctioon nnum(s:iinteegerr):llonggintt;begiin nuum:=(s+2)*(s+1)*s ddiv 6;end;procceduure mulltipply(varr ndd:noode;s:llonggintt);高精度度乘法var c:llonggintt; i:iinteegerr;begiin c:=0; wiith nd do beggin forr i:=1 to lasst ddo bbegiin vi:=vi*s+cc; c:=vi divv 100; vi:=vi modd 100; eend; whii

40、le c0 ddo bbegiin iinc(lasst); vvlaast:=cc mood 110; cc:=cc diiv 110; endd; ennd;end;begiin reeadnn; wiith tott doo beggin ffilllchaar(vv,siizeoof(vv),00); vv1:=11;laast:=1; endd;初初始化 foor ii:=11 too n do mulltipply(tott,nuum(aai);计算算阶积和和 wiith tott doo输出出结果 forr i:=laast dowwntoo 1 do wriite(vii);

41、wrriteeln;end.2 由于于方法一一效率太太低，方方法二无无法实现现，仅给给出对应应方法三三的程序序。proggramm nuumbeer;consst iinpuutfiile=nuumbeer.iin; ooutpputffilee=nnumbber.outt;var f:texxt; n,m:llonggintt; mbb:loongiint;储存存当前真真因子个个数最多多的数 fnn:inntegger;储存存当前真真因子个个数最多多的数所所包含的的真因子子个数 s,t,ii,j:lonnginnt; s+1,tt为分段段统计时时的起点点、终点点 a:arrray1.3000

42、00 off inntegger; 每次次统计连连续3000000个数的的真因子子个数,包括每每个数本本身procceduure reaadn;begiin asssiggn(ff,innputtfille); reesett(F); reeadlln(ff,n,m); cllosee(F);end;funcctioon mmax(x,yy:loongiint):loongiint;返回回x,yy中大的的值begiin iff xy tthenn maax:=x eelsee maax:=y;end;procceduure outtputt;begiin asssiggn(FF,ouutpuu

43、tfiile); reewriite(F); wrriteeln(f,mmb); cllosee(F);end;begiin reeadnn; mbb:=00; ffn:=0; s:=n-1; whhilee smm thhen t:=m; filllchhar(a,ssizeeof(a),0); a11:=1;为方便便统计，设1包包含两个个因子（均为11） forr j:=1 to truunc(sqrrt(tt) do 枚枚举不同同因子 ffor i:=maxx(j+1,（s+11) ddiv j) to t ddiv j ddo iinc(aii*j-s,2); 需需要统计计的各因因子的

44、倍倍数 forr j:=trruncc(sqqrt(s+11) to truunc(sqrrt(tt) do incc(aj*jj-s); 统计计完全平平方数 forr i:=1 to t-ss doo将本本区间的的统计结结果与已已知最优优值比较较、取优优 iif aaifnn thhen beggin fnn:=aai; mbb:=ii+s; eend; s:=t; ennd; ouutpuut;end.3动态规规划的方方法只作作为理论论讨论，不具可可行性。$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+$M 163384,0,66553

45、360proggramm chhainn;consst mmaxnn=755; iinpuutfiile=innputt.txxt; ooutpputffilee=ooutpput.txtt;typee woord=strringgmaaxn;定定义单词词类型var f:texxt; wdd,prrev,anss_wdd:woord;wdd当前前单词；preev前驱单单词；aans_wd最长长词链 noow,mmax,i,ll:inntegger;noww包括括当前单单词的最最长词链链；l前驱驱单词的的长度；maxx最长长词链的的长度procceduure outtputt(stt:woord

46、);将stt串按小小写字母母输出varr i:inttegeer;bbegiin forr i:=1 to lenngthh(stt) ddo iif sstii=uupcaase(sti) thhen wriite(F,cchr(ordd(stti)+332) elsse wwritte(ff,stti); wrriteeln(F);end;begiin asssiggn(ff,innputtfille);resset(F); prrev:=;前前驱单词词清空 l:=0;前驱驱单词长长度置零零 reppeatt reeadlln(FF,wdd);读入一一个单词词 iff wdd=. tthe

47、nn brreakk;文文件结束束标志 noow:=0;前缀词词链个数数清零 foor ii:=11 too leengtth(wwd) do iif ii=ll thhen beggin iff prrevi=upccasee(wddi)含含有一个个前缀单单词 theen bbegiin iinc(noww); wwdii:=upccasee(wddi);用大写写字母标标记前缀缀的位置置 endd ellse if preeviiwdi theen bbreaak; 与与前驱单单词出现现分歧，跳出循循环 endd ellse breeak;大于于前驱单单词的长长度，跳跳出循环环 wdlenn

48、gthh(wdd):=uppcasse(wwdllenggth(wd);标记记末字母母，表示示为本身身的前缀缀 l:=lenngthh(wdd);递推给给下一个个单词 preev:=wd; if nowwmaax tthenn beeginn保留最最长的词词链 mmax:=noow; aans_wd:=wdd; endd; unntill trrue=fallse; cllosee(F); asssiggn(FF,ouutpuutfiile);reewriite(f); 输输出结果果 foor ii:=11 too leengtth(aans_wd) dooif aans_wdi=upccas

49、ee(anns_wwdii) theen ooutpput(coppy(aans_wd,1,ii); cllosee(F);end.4 问题题四IOOI999机机场跑道道，程程序laand_1.paas中实实际上也也用到了了剪枝条条件，由由于效果果不很明明显，因因此没有有着重讨讨论。llandd_3.paas仅仅仅是在llandd_2.paas的基基础上增增加了两两个剪枝枝条件，其余完完全相同同，因此此这里仅仅给出llandd_3.paas。$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+$M 20448,00,65553660proggr

50、amm laand_1;consst mmaxnn=7000; llastt=1000; 一次次性读入入的区域域列数（东西方方向） iinpuutfiile=laand.inpp; ooutpputffilee=llandd.ouut;typee arrr=aarraay00.mmaxnn oof iinteegerr; crrr=aarraay00.110 of lonnginnt; maaptyype=arrray1.maxxn of arrr;var f:texxt; u,v,cc,i,j:iinteegerr; xmmin,ymiin,xxmaxx,ymmax:inttegeer; 机

51、场场所在区区域的信信息 maap:mmapttypee;地地图 arrea,maxxareea:llonggintt; （arrea-当当前的最最大面积积；maaxarrea-最最大面积积的上限限；） Buuf:aarraay11.881911 oof CCharr; 88K bbufffer；缓冲区区 leen:aarraay11.mmaxnn oof ccrr; wiide:crrr;procceduure gett(leeft,rigght:inttegeer); 读读入地图图的leeft列列至riightt列var i,jj,k,no:inttegeer;begiin reesett(

52、F); foor ii:=vv doowntto 11 doo beeginn reaadlnn(F); forr j:=1 to lefft-11 doo reead(f,kk); forr noo:=lleftt too riightt doo iif nno=u tthenn reead(f,mmapnoii) elsse bbreaak; ennd;end;procceduure donne(sstl,edll:inntegger);求解以以stll为西面面界限且且其东面面界限不不超过eedl中中的最大大区域var i,jj,k,k0:inttegeer; minn,maax:iint

53、eegerr; maxxw:llonggintt;begiin iff loongiint(edll-sttl+11)*llonggintt(v)eedl) orr (mmapkimaax) or (maapkkiminn); lleni,jj:=k-sstl; endd; maaxw:=v; foor ii:=11 too v do beggin decc(maaxw); 当前宽宽度 forr k:=0 to c ddo bbegiin 求包包括i行行首位置置在内的的最低高高度(ii行首位位置高度度减k)一定的的区域的的最大面面积 wwideek:=lleni,kk; j:=i;北界限限 r

54、repeeat iff wiidek*maxxwaareaa thhen beggin areea:=widdekk*(lonnginnt(jj)-llonggintt(i)+1); xmiin:=stll;xmmax:=xmmin+widdekk-11; ymiin:=i;yymaxx:=jj; ennd; innc(jj); 北界界限累加加 iff jv tthenn brreakk; k00:=mmapstllj-mappsttli+k; iff (kk0c) theen bbreaak; iff leenjj,k00uu thhen maxxareea:=lonnginnt(vv)*l

55、longgintt(u) ellse maxxareea:=lonnginnt(vv)*1100; foor ii:=11 too 1000 ddo nnew(mappi); geet(11,1000); foor ii:=11 too u-99 do beggin donne(ii,i+99); dissposse(mmapi);释释放空间间 if areea=mmaxaareaa thhen breeak;已经经达到了了最大面面积的上上限，跳跳出循环环 if (i modd laast=1) andd (ii+laast+9900 thhen donne(ii,u); cllosee(F)

56、; asssiggn(ff,ouutpuutfiile);reewriite(F); wrriteeln(f,aareaa); wrriteeln(f,xxminn, ,yyminn, ,xxmaxx, ,yymaxx); cllosee(F);end.$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+$M 20448,00,65553660proggramm laand_3;consst mmaxnn=7000; llastt=1000;一次性性读入的的区域列列数（东东西方向向） iinpuutfiile=laand.inpp; ooutp

57、putffilee=llandd.ouut;typee arrr=aarraay00.mmaxnn oof iinteegerr; maaptyype=arrray1.maxxn of arrr;var f:texxt; u,v,cc,i,j:iinteegerr; xmmin,ymiin,xxmaxx,ymmax:inttegeer;机场所所在区域域的信息息 maap:mmapttypee;地地图 miin,mmax:arrray1.maxxn of inttegeer;分别存存储一定定区域内内的最小小高度、最大高高度 arrea,maxxareea:llonggintt;（areea-当前

58、前的最大大面积；maxxareea-最大大面积的的上限；） Buuf:aarraay11.881911 oof CCharr; 88K bbufffer；缓冲区区 procceduure gett(leeft,rigght:inttegeer);读入入地图的的lefft列至至rigght列列var i,jj,k,no:inttegeer;begiin reesett(F); foor ii:=vv doowntto 11 doo beeginn reaadlnn(F); forr j:=1 to lefft-11 doo reead(f,kk); forr noo:=lleftt too riightt doo iif nno=u tthenn re