算法合集之《浅谈数形结合思想在信息学竞赛中的应用》.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,IOI2004,冬令营演示文稿,安徽周源,浅谈数形结合思想在信息学竞赛中的应用,安徽 周源,引子,数与形是数学中两个最古老而又最基本的对象,数形结合又是一种重要的数学思想,在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。,数形结合思想常包括以下几个方面：,以形助数,例一,Raney,的证明,例二,最大平均值问题,以数助形,例三,画室,以形助数,繁杂代数关系后常隐藏着丰富的几何背景,借助背景图形的性质，可以使原本复杂的数量关系和抽象的概念显得直观，从而找到设计算法的捷径。,数,？,?,opt,(,N,)=max,f(i,)=f(i-1)+f(i-2),形！,直线、圆,转化,例二,最大平均值问题,(USACO),读入一列正数，,a,1,a,2,a,N,，以及数,F,求一段长度大于等于,F,且,平均值最大,的子串,定义若,i,j,，,ave(,i,j,)=(,a,i,+,a,j,)/(,j,-,i,+1),目标：,Maxave(,a,b,)|,a,b,-,F,+1,范围：,F,N,100 000,例如,N=4,的序列中，,F=2,2,5,2,5,ave(2,4)=(5+2+5)/3=4,最大,初步分析,O(,N,2,),算法,枚举一个,b,：称为,检查点,枚举符合条件,a,：称为,被检查点,，,检查集合,条件即为,a,b,-,F,+1,同时检查,ave(,a,b,),目标图形化,设部分和序列,S,i,为,a,i,前,i,项和，,S,0,=0,ave(,i,j,)=,S,j,-S,i,-1,/j-(i-1),过两点的直线：,P,i,-1,(,i,-1,S,i,-1,),，,P,j,(,j,S,j,),问题转化：,平面上已知,N,+1,个点，,P,i,(,i,S,i,),，,0,i,N,求横向距离大于等于,F,的两点连线的最大斜率,斜率公式！,目标图形化,数列,a,i,=,(2,5,2,5),，,F=2,部分和,S,i,=(0,2,7,9,14),y,x,(0,0),(1,2),(2,7),(3,9),(4,14),ave(2,4)=k(P,1,P,4,)=4,距离,3,构造下凸折线,考察检查点,Z,三个被检查点,从左到右三个点,A,B,C,若,B,是上凸点？,构造下凸折线,若,B,不多余,k(BZ,),有可能最大,若,k(BZ,),大于,k(AZ,),Z,在,1,号区域,若,k(BZ,),大于,k(CZ,),Z,在,2,号区域,若,k(BZ,),最大,Z,在阴影重叠区域,!,与,B,在,Z,左方矛盾,B,多余,结论：,每个点的检查集合只需要保留一个,下凸函数,即可,在检查集合中查找斜率最大点，即寻找,切点,维护下凸折线,目标：,得到每一个检查集合的下凸折线,类似于求凸包过程,线形时间内完成！,y,x,P,0,P,F,最后的优化：利用单调性,每次如何寻找切线？,二分法：,O(log,2,N),利用折线,斜率单调性,：,O(1),更快，更简单,请同学们自行思考,y,x,Z,A,例二,最大平均值问题,(USACO),小结,一开始就确立了以,平面几何,为思考工具的正确路线,重要结论：,检查集合中有用的点构成一个下凸函数,类似于计算几何中求凸包的方法维护一个下凸折线,利用下凸函数,斜率单调性,得到找切线的简单方法,围绕,平面几何,为中心，以,斜率,为主线,整个解题过程一气呵成,避免了令人头晕的代数式变换,堪称以形助数的经典例题。,以数助形,一些试题给出的描述中图形极为复杂，容易使选手陷入“迷魂阵”,以数助形，一举抓住其本质特征，不失为解题的一种好方法。,形？,数！,x,2,+,y,2,=1,(10101),2,转化,例三,画室,(POI,oi,V Stage I),定义尺寸为,0,的方阵为一个,1*1,的矩阵，在其唯一的一个方格中有一个小孔。,对于,i,0,，递归的定义尺寸为,i,的方阵：,尺寸为,2,的方阵,尺寸为,0,的方阵,例三,画室,(POI,oi,V Stage I),已知尺寸,N,，和两个参数,X,和,Y,准备两个尺寸为,N,的方阵叠放在一起,上面的方阵右移,X,列，上移,Y,行,求两个方阵有多少个公共的孔？,如,N,=2,X,=2,Y,=2,有,3,个公共孔,初步分析,直接分析两个方阵相交后的情况是可行的,集训队前辈解题报告的一个附图,结论：“形”的路子很坎坷,目标数值化,将行列按图示方法,从,0,开始,编号,每个方格都有唯一坐标,P(,x,y,),P(,x,y,),内有小孔,？,尺寸为,2,的方阵,列：,0,1,2,3,行：,0,1,2,3,(0,3),(1,3),(0,2),(1,2),(2,3),(3,3),(2,2),(3,2),(0,1),(1,1),(0,0),(1,0),(2,1),(3,1),(2,0),(3,0),(0,3),(1,3),(0,2),(1,2),(2,3),(3,3),(2,2),(3,2),(0,1),(1,1),(0,0),(1,0),(2,1),(3,1),(2,0),(3,0),目标数值化,将,x,y,化为二进制,a,1,a,2,a,3,a,N,和,b,1,b,2,b,3,b,N,考察,a,1,和,b,1,对方格位置的影响,a,1,=0,且,b,1,=1,时方格内必无孔！,方格的,有孔性质,当且仅当不存在,1,i,N,满足,a,i,=0,且,b,i,=1,时,方格,P,内有小孔。,(a,1,b,1,),分布图,动态规划解题,题目即求满足下列条件的方格,P(,x,y,),个数,0,x,y,，,x,+,X,y,+,Y,2,N,-1,(,x,y,),，,(,x,+,X,y,+,Y,),都满足有孔性质,算法简述,以位数为阶段,通过记录,x,+,X,和,y,+,Y,进位情况保证无后效性,时间复杂度：,O(,N,),空间复杂度：,O(1),简单的动态规划算法！,例三,画室,(POI,oi,V Stage I),小结,“形”：情况复杂，不宜讨论,“,数”：方格的有孔性质和有公共孔性质,更简单的解题,面对复杂的图形,化形归数,往往是抓住题目要害的好方法,总结,数,形,客观事物,数学,数形结合思想,抽象,总结,数,形,数形结合思想,例三,画室,例二,最大平均值问题,互相转化,辩证矛盾关系,多元性,个体差异性,解法不唯一,但是较好的,一定程度上,唯一的解法,本质化工具,形象化工具,不同的人对难度感觉不同,以形助数,以数助形,总结,数,形,数形思想,辩证矛盾关系,多元性,个体差异性,将抽象的数学、计算机语言与直观的图形,结合起来,将抽象思维与形象思维,结合起来,实现抽象概念与具体形象的,联系,和,转化,结合,更快更好更简单的解决实际问题,谢谢大家,Thanks,例二,关于找切线的方法,利用折线斜率单调性：,若已知一条切线,ZA,A,左方点可删去,平摊复杂度,O(1),实现方法,设一个不回溯指针,y,x,Z,A,