浅谈数形结合思想在信息学竞赛中的应用

浅谈数形结合思想在信息学竞赛中的应用安徽周源第1页共12页浅谈数形结合思想在信息学竞赛中的应用安徽周源目录目录............................................................1摘要............................................................2关键字..........................................................2引子............................................................3以形助数........................................................3[例一]Raney引理的证明.......................................3[题意简述]...............................................3[分析]...................................................3目标图形化............................................3小结..................................................4[例二]最大平均值问题(USACO2003MarchOpen)..................4[题意简述]...............................................4[分析]...................................................5目标图形化............................................5构造下凸折线..........................................5维护下凸折线..........................................6最后的优化：利用图形的单调性..........................7小结..................................................7以数助形........................................................7[例三]画室(POIoiVStageI).................................8[题意简述]...............................................8[分析]...................................................8目标数值化............................................9动态规划解题..........................................9小结.................................................10总结...........................................................10附录...........................................................11关于2003年上海市选拔赛题Sequence..........................11[题意简述]..............................................11[分析]..................................................11论文附件....................................................12参考文献.......................................................12浅谈数形结合思想在信息学竞赛中的应用安徽周源第2页共12页摘要数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。关键字信息学竞赛数学思想数形结合思想以数助形以形助数辩证矛盾多元性个体差异性思维、编程、时间、空间复杂度浅谈数形结合思想在信息学竞赛中的应用安徽周源第3页共12页引子数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。数形结合思想常包括以形助数、以数助形两个方面。以形助数正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。[例一]Raney引理的证明[题意简述]设整数序列A={Ai,i=1,2,…,N}，且部分和Sk=A1+…+Ak，序列中所有的数字的和SN=1。证明：在A的N个循环表示1中，有且仅有一个序列B，满足B的任意部分和Si均大于零。[分析]先来看一个例子，若有序列A=1,4,-5,3,-2,0，其6个循环表示为1.1,4,-5,3,-2,02.4,-5,3,-2,0,13.-5,3,-2,0,1,44.3,-2,0,1,4,-55.-2,0,1,4,-5,36.0,1,4,-5,3,-2其中只有第4个序列，部分和为3,1,1,2,6,1，满足成为序列B的条件。若要用一般的代数或是组合方法来证明这个有趣的结论，似乎无从下手，但若要想到了用“形”来帮忙，问题就简单多了。目标图形化周期性的推广A序列，得到一个无穷序列，便于观察其循环表示，得到：1先设一个序列是环状的，则从其任意一个字符处断开以后形成的非环序列即为该序列的一个循环表示。浅谈数形结合思想在信息学竞赛中的应用安徽周源第4页共12页A1,A2,…,AN,A1,A2,…,AN,…同时计算这个序列的部分和Si，因为这个序列是周期性的，因此对于所有的k0，均有Sk+N=Sk+1。如果做出这个函数的图像，则可以说函数有一个“平均斜率”为N1：每沿横轴正方向走N个单位，函数值就增加1。于是如下图所示，可以用两条斜率为N1的直线“夹住”函数包含的所有点：图1无穷序列的部分和函数图像图示中N=6，且使用了上文举的例子。注意较低的那条直线，在每连续的N个单位长度中，它与函数图像有且仅有一个交点，这是因为斜率是N1的直线在每N个单位长度中最多到达一次整数点。这个交点是在这以后的N个点中的最低值，因此由此处的后一个位置导出的循环表示的所有部分和均为正数。而同时每连续N个单位长度仅有一个交点也证明了解的唯一性。小结一个简单的几何论证就证明了著名的Raney引理，其简练是其他方法不能企及的。Raney引理有很广泛的应用，Catalan数以及扩展Catalan数的组合公式就可以用该引理轻松解决。比如今年上海市选拔赛第二天比赛中的序列(Sequence)以及OIBH练习赛中的项链，使用Raney引理都是最简单的方法之一。2用几何图形辅助思考，不只停留在组合计数这一类中，更渗透在算法设计和优化的每一个分支中，近年来流行的“斜率优化”法是另一个很好的例子。[例二]最大平均值问题(USACO2003MarchOpen)[题意简述]读入一列正数，a1,a2,…,aN，以及一个数F。定义1),(ijaajiaveji，i≤j。2用Raney引理解答Sequence的过程，详见附录。浅谈数形结合思想在信息学竞赛中的应用安徽周源第5页共12页求Max{ave(a,b),1≤a,b≤N，且a≤b-F+1}，即求一段长度大于等于F且平均值最大的子串。范围：F≤N≤105。[分析]简单的枚举算法可以这样描述：每次枚举一对满足条件的(a,b)，即a≤b-F+1，检查ave(a,b)，并更新当前最大值。然而这题中N很大，N2的枚举算法显然不能使用，但是能不能优化一下这个效率不高的算法呢？答案是肯定的。目标图形化首先一定会设序列ai的部分和：Si=a1+a2+…+ai，，特别的定义S0=0。这样可以很简洁的表示出目标函数)1(),(1ijSSjiaveij！如果将S函数绘在平面直角坐标系内，这就是过点Sj和点Si-1直线的斜率！于是问题转化为：平面上已知N+1个点，Pi(i,Si)，0≤i≤N，求横向距离大于等于F的任意两点连线的最大斜率。构造下凸折线有序化一下，规定对ij，只检查Pj向Pi的连线，对Pi不检查与Pj的连线。也就是说对任意一点，仅检查该点与在其前方的点的斜率。于是我们定义点Pi的检查集合为Gi={Pj,0≤j≤i-F}特别的，当iF时，Gi为空集。其明确的物理意义为：在平方级算法中，若要检查ave(a,b)，那么一定有Pa∈Gb；因此平方级的算法也可以这样描述，首先依次枚举Pb点，再枚举Pa∈Gb，同时检查k(PaPb)。若将Pi和Gi同时列出，则不妨称Pi为检查点，Gi中的元素都是Pi的被检查点。当我们考察一个点Pt时，朴素的平方级算法依次选取Gt中的每一个被检查点p，考察直线pPt的斜率。但仔细观察，若集合内存在三个点Pi,Pj,Pk，且ijk，三个点形成如下图所示的的关系，即Pj点在直线PiPk的上凸部分：k(Pi,Pj)k(Pj,Pk)，就很容易可以证明Pj点是多余的。浅谈数形结合思想在信息学竞赛中的应用安徽周源第6页共12页阴影重叠区域2号区域1号区域xyPjPiPk图2若k(Pt,Pj)k(Pt,Pi)，那么可以看出，Pt点一定要在直线PiPj的上方，即阴影所示的1号区域。同理若k(Pt,Pj)k(Pt,Pk)，那么Pt点一定要在直线PjPk的下方，即阴影所示的2号区域。综合上述两种情况，若PtPj的斜率同时大于PtPi和PtPk的，Pt点一定要落在两阴影的重叠部分，但这部分显然不满足开始时tj的假设。于是，Pt落在任何一个合法的位置时，PtPj的斜率要么小于PtPi，要么小于PtPk，即不可能成为最大值，因此Pj点多余，完全可以从检查集合中删去。这个结论告诉我们，任何一个点Pt的检查集合中，不可能存在一个对最优结果有贡献的上凸点，因此我们可以删去每一个上凸点，剩下的则是一个下凸折线。最后需要在这个下凸折线上找一点与Pt点构成的直线斜率最大——显然这条直线是在与折线相切时斜率最大，如图所示。yxPt图3维护下凸折线这一小节中，我们的目标是：用尽可能少的时间得到每一个检查点的下凸折浅谈数形结合思想在信息学竞赛中的应用安徽周源第7页共12页线。算法首先从PF开始执行：它是检查集合非空的最左边的一个点，集合内仅有一个元素P0，而这显然满足下凸折线的要求，接着向右不停的检查新的点：PF+1,PF+2,…,PN。检查的过程中，维护这个下凸折线：每检查一个新的点Pt，就可以向折线最右端加入一个新的点Pt-F，同时新点的加入可能会导致折线右端的一些点变成上凸点，我们用一个类似于构造凸包的过程依次删去这些上凸点，从而保证折线的下凸性。由于每个点仅被加入和删除一次，所以每次维护下凸