资源描述：
《国家集训队2004论文集 周源》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、浅谈数形结合思想 在信息学竞赛中的应用安徽周源引子数与形是数学中两个最古老而又最基本的对象数形结合又是一种重要的数学思想在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。数形结合思想常包括以下几个方面：以形助数[例一]Raney的证明[例二]最大平均值问题以数助形[例三]画室以形助数繁杂代数关系后常隐藏着丰富的几何背景借助背景图形的性质，可以使原本复杂的数量关系和抽象的概念显得直观，从而找到设计算法的捷径。数？?opt(N)=max{…}f(i)=f(i-1)+f(i-2)形！！直线、圆……转化[例二]最大平均值问题(USACO)读入一列正数，a1
2、,a2,…,aN，以及数F求一段长度大于等于F且平均值最大的子串定义若i≤j，ave(i,j)=(ai+…+aj)/(j-i+1)目标：Max{ave(a,b)
3、a≤b-F+1}范围：F≤N≤100000例如N=4的序列中，F=22,5,2,5ave(2,4)=(5+2+5)/3=4最大初步分析O(N2)算法枚举一个b：称为检查点枚举符合条件a：称为被检查点，检查集合条件即为a≤b-F+1同时检查ave(a,b)目标图形化设部分和序列Si为{ai}前i项和，S0=0ave(i,j)=[Sj-Si-1]/[j-(i-1)]过两点的直线：Pi-1(i-1,Si-1)，Pj(j,Sj)问题转化：平面
4、上已知N+1个点，Pi(i,Si)，0≤i≤N求横向距离大于等于F的两点连线的最大斜率斜率公式！目标图形化数列{ai}=(2,5,2,5)，F=2部分和{Si}=(0,2,7,9,14)yx(0,0)(1,2)(2,7)(3,9)(4,14)ave(2,4)=k(P1P4)=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多余结论：每个点的检查集合只需要保留一个下凸函数即可在检查集合中查找斜率
5、最大点，即寻找切点维护下凸折线目标：得到每一个检查集合的下凸折线类似于求凸包过程线形时间内完成！yxP0PF最后的优化：利用单调性每次如何寻找切线？二分法：O(log2N)利用折线斜率单调性：O(1)更快，更简单请同学们自行思考yxZA[例二]最大平均值问题(USACO)小结一开始就确立了以平面几何为思考工具的正确路线重要结论：检查集合中有用的点构成一个下凸函数类似于计算几何中求凸包的方法维护一个下凸折线利用下凸函数斜率单调性得到找切线的简单方法围绕平面几何为中心，以斜率为主线整个解题过程一气呵成避免了令人头晕的代数式变换堪称以形助数的经典例题。以数助形一些试题给出的描述中图形极为复杂，容易使
6、选手陷入“迷魂阵”以数助形，一举抓住其本质特征，不失为解题的一种好方法。形？？数！！x2+y2=1(10101)2……转化[例三]画室(POIoiVStageI)定义尺寸为0的方阵为一个1*1的矩阵，在其唯一的一个方格中有一个小孔。对于i>0，递归的定义尺寸为i的方阵：尺寸为2的方阵尺寸为0的方阵[例三]画室(POIoiVStageI)已知尺寸N，和两个参数X和Y准备两个尺寸为N的方阵叠放在一起上面的方阵右移X列，上移Y行求两个方阵有多少个公共的孔？如N=2,X=2,Y=2有3个公共孔初步分析直接分析两个方阵相交后的情况是可行的集训队前辈解题报告的一个附图结论：“形”的路子很坎坷目标数值化将行
7、列按图示方法从0开始编号每个方格都有唯一坐标P(x,y)P(x,y)内有小孔？尺寸为2的方阵列：0123行：0123(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化为二进制a1a2a3…aN和b1b2b3…bN考察a1和b1对方格位置的影响a1=0且b1=1时方格内必无孔！方格的有孔性质当且仅当不存在
8、1≤i≤N满足ai=0且bi=1时方格P内有小孔。(a1,b1)分布图动态规划解题题目即求满足下列条件的方格P(x,y)个数0≤x,y，x+X,y+Y≤2N-1(x,y)，(x+X,y+Y)都满足有孔性质算法简述以位数为阶段通过记录x+X和y+Y进位情况保证无后效性时间复杂度：O(N)空间复杂度：O(1)简单的动态规划算法！[例三]画室(POIoiVStageI)小结“形”：情况复杂，不宜讨论“数
