基础算法选讲课件.ppt

《基础算法选讲课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基础算法选讲长沙市一中康望程主要内容分治归并排序快速幂平面最近点对二分二分问题在转化转化问题再二分二分的选择倍增RMQ树上路径询问*分治分而治之不啰嗦了归并排序快速幂A^B%PA,P<=10^9,B<=10^18将B二进制分解A^b1*A^b2*…其中b1+b2+…=B根据同余有a*b%c=(a%c)*(b%c)%c复杂度降至O(logB)代码推荐写成递归的快速幂代码实现functionpow(a,b:int64)if(b=0)exit(1);t=pow(a,bdiv2);t=t*t%P;if(b%2=1)exit(t*a%P)elseexit(t);Endf

2、unction平面最近点对给定平面内N个点坐标求出最小的两点间的欧几里得距离N<=10^5分析当一个点集中只有两个点时，它们的距离就是最近距离；当一个点集中有三个点时，它们的距离也可以直接求出；当一个点集中的点数量大于3时，则将数组拆分成两半，分别计算左右子集的最近距离的平方d（将数量>3的数组一直拆分，最后到只有2个或3个点的点集时即能求解），收集距离中线两侧小于d的点，在这些点中寻找垂直距离小于d的两个点，若存在则说明其为当前能找到的最近点对，更新d为这两点的距离。将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中

3、递归地求最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。如果这两个点分别在S1和S2中，问题就变得复杂了。为了使问题变得简单，首先考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1，x2，...，xn。最接近点对即为这n个实数中相差最小的两个实数。显然可以先将点排好序，然后线性扫描就可以了。但我们为了便于推广到二维的情形，尝试用分治法解决这个问题。假设我们用m点将S分为S1和S2两个集合，这样一来，对于所有的p(S1中的点)和q(S2中的点)，有p

4、找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{

5、p1-p2

6、,

7、q1-q2

8、}由此易知，S中最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{q3,p3}，如下图所示。如果最接近点对是{q3,p3}，即

9、p3-q3

10、

11、S

12、=2thenδ:=S中这2点的距离elseif

13、S

14、=0then

15、δ:=∞elsebegin1.m:=S中各点x坐标值的中位数;构造S1和S2，使S1={p∈S

16、px≤m}和S2={p∈S

17、px>m}2.δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);3.δm:=min(δ1,δ2);4.设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合，P2是S2中距分割线l的距离在δm之内所有点组成的集合。将P1和P2中的点依其y坐标值从小到大排序，并设P1*和P2*是相应的已排好序的点列;5.通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在δm之内的所有点(最多6个)可以完成合并。当P1

18、*中的扫描指针逐次向上移动时，P2*中的扫描指针可在宽为2δm的一个区间内移动。设δl是按这种扫描方式找到的点对间的最小距离;6.δ=min(δm,δl);end;return(δ);end;Yandex.Algorithm2011FinalsProblemB.Superset一个点集被称为Super当且仅当其中任意两点至少符合以下3项之一在同一水平线上在同一竖直线上以这两点为矩形的顶点，这个矩形内（包括边界）上有除开这两点外的其他点给定N<=10^4个点要求添加至多2*10^5个点，使得这个点集是Super的输出方案分析类似平面最近点对假设分出的左

19、右两点集已经是super的了考虑跨越中线的点对黑板保证最多只有NlogN个点10000*log10000=140000二分t=-1,l=start,r=end,midwhile(l<=r)dobeginmid=(l+r)>>1;if(Check(mid))l=mid+1,t=mid;elser=mid-1;end;t=-1???转化问题再二分例题(北京08省选)：在数轴上有N类点，每一类用S,E,D来表示，意思是这些点分布在S,S+D,S+2D…S+kD(S+kD<=E)已知最多只有一个坐标上有奇数个点，要求找出它或指出不存在。N<=100000,S,E,D<

20、=10^9分析我们用0表示偶数个点，1