NOIP基础算之分治

分治策略一、分治思想分治法，又叫分治策略，顾名思义，分而治之。它的基本思想为：对于难以直接解决的规模较大的问题，把它分解成若干个能直接解决的相互独立的子问题，递归求出各子问题的解，再合并子问题的解，得到原问题的解。通过减少问题的规模，逐步求解，能够明显降低解决问题的复杂度。二、分治法的适用条件能使用分治法解决的问题，它们一般具备以下几个特征：①该问题可以分解成若干相互独立、规模较小的相同子问题；②子问题缩小到一定的程度能轻易得到解；③子问题的解合并后，能得到原问题的解；分治法在信息学竞赛中应用非常广泛，使用分治策略能生成一些常用的算法和数据结构，如快排、最优二叉树、线段树等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。三、分治的三步骤①分解：将要解决的问题分解成若干个规模较小的同类子问题；②解决：当子问题划分得足够小时，求解出子问题的解。③合并：将子问题的解逐层合并成原问题的解。分治算法设计过程图分治思想由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n＝6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲，都是2分为主。四、分治的框架结构if问题不可分{直接求解；返回问题的解；}else{对原问题进行分治；递归对每一个分治的部分求解;归并整个问题，得出全问题的解；}五、分治的典型应用1、求最大值和最小值2、非线性方程求根3、二分查找4、归并排序5、快速幂6、求解线性递推关系7、棋盘覆盖问题8、循环日程表问题9、寻找最近点对1、求最大值和最小值例题1：给n个实数，求它们之中最大值和最小值，要求比较次数尽量小。分析：假设数据个数为n,存放在数组a;ma=a>mama=a<minnminn=a;使用这一算法，比较次数为2n-1。若n=10,则比较18次。用分治法解决这个问题就是把集合a分成a1,a2两个子集，每个子集有n/2个元素，应用递归结构找出两个子集的最大元和最小元，比较得到的两个最大元和最小元即可得到整个集合a中的最大元和最小元。划分：把n个数均分为两半。即：划分点为d=r1r2/2，两个区间为。递归求解：求左半的最小值min1和最大值ma1以及右半最小值min2和最大值ma2。合并：所有数的最大值为ma，最小值为minn。核心代码voida,int&minn{intma1,min1,ma2,min2,d;ifr1==r2{ma=minn=;}elseifr2==r11{if;minn=;minn=;}}else{d=r1r2/2;a1,min1;a2,min2;ifma1>ma2ma=ma1;elsema=ma2;ifmin1<min2minn=min1;elseminn=min2;}}【思考试题】最大值最小化【问题描述】把一个包含n个正整数的序列划分成m个连续的子序列每个正整数恰好属于一个序列。设第i个序列的各数之和为Si，你的任务是让所有的Si的最大值尽量小。例如序列123254划分成3个序列的最优方案为123|25|4，其中S1=6，S2=7，S3=4，最大值为7；如果划分成12|32|54，则最大值为9；不如刚才的好。n<=10^6，所有数字之和不超过10^9。2、非线性方程求根【例题2】一元三次方程的解【题目描述】有形如：a3b2cd=0这样的一个一元三次方程。给出该方程中各项的系数a,b,c,d均为实数，并约定该方程存在三个不同实根根的范围在-100至100之间，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根根与根之间留有空格，并精确到小数点后4位。【文件输入】输入仅一行，有四个数，依次为a、b、c、d【文件输出】输出也只有一行，即三个根从小到大输出【样例输入】1-5-420【样例输入】-200200500分析如果精确到小数点后两位，可用简单枚举法：将从-10000到10000（步长001）逐一枚举，得到20000个f，取其值与0最接近的三个f，对应的即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值分析A当已知区间a,b内有一个根时；用二分法求根，若区间a,b内有根，则必有fa*fb<0。重复执行如下的过程：1若a00001>b或fab/2=0，则可确定根为ab/2并退出过程；2若fa*fab/2<0,则由题目给出的定理可知根在区间a,ab/2中,故对区间重复该过程；3若fa*fab/2>0,则必然有fab/2*fb<0,根在ab/2,b中,对此区间重复该过程。执行完毕,就可以得到精确到00001的根。分析B、求方程的所有三个实根所有的根的范围都在-100至100之间，且根与根之差的绝对值>=1。因此可知：在、这201个区间内，每个区间内至多只能有一个根。即：除区间，只有当fa=0或fa·fa1<0时，方程在此区间内才有解。若fa=0，解即为a；若fa·fa1<0，则可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。核心参考代码voiddividedouble1,double2{double0,y0,y1,y2;0=12/2;y1=cal1;y2=cal2;y0=cal0;if2-1<000001&&y1*y2<0{printf"%4f",21/2;return;}ify1*y0<0||0-1>1divide1,0;ify0*y2<0||2-0>1divide0,2;}3、归并排序归并排序的基本思想：归并排序充分应用分治算法的策略，将n个数分成n个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列，每个数列中有2个数；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说，归并过程为：（1）划分：把序列分成元素个数相等的两半；（2）递归求解：把两半分别排序；（3）合并：把两个有序表合成一个；分析显然，前两部分是很容易完成的，关键在于如何把两个有序表合成一个。每次只需要把两个序列中当前的最小元素加以比较，删除较小元素并加入合并后的新表。核心参考代码intteman];//辅助空间voidMergeSortintleft,intright//对区间left---right进行归并排序{ifleft==rightreturn;//只有一个元素mid=leftright/2;//找中间位MergeSortleft,mid;//对左边归并MergeSortmid1,right;//对右边归并i=left,j=mid1,id&&j<=rightifa;}【变形1】逆序对数目例题：求“逆序对”。给定一整数数组A=A1,A2,…An,若i<j且Ai>Aj,则<i,j>就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有<3,1>,<3,2>,<4,2>,<5,2>。问题是，输入n和A数组，统计逆序对数目。数据范围：1<=n<=30000。朴素算法原始的解决方案（双重循环）C:=0;Fori:=1ton-1doforj:=i1tondoifathenc:=c1;时间复杂度为On2分治算法：采用二分法求解:记数列a的逆序对数目为Dst,ed;

mid=,则有：Dst,ed=Dst,midDmid1,edF,ed其中Fst,mid,ed表示一个数取自A的逆序对数目。和归并排序一样，划分和递归求解都好办，关键在于合并：如何求出i在左边，而j在右边的逆序对数目呢？统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类：只要对于右边的每个j，统计左边比它大的元素个数fj，则所有fj之和便是答案。幸运的是，归并排序可以帮助我们“顺便”完成fj的计算：由于合并操作是从小到大进行排序的，当右边的a复制到T中时，左边还没有来得及复制到T的那些数就是左边所有比a大的数。此时累加器中加上左边元素个数mid-i1即可。即把“ifa=a;}”。4、二分查找【问题描述】给出从小到大排列的n个不同数a，试判断元素是否出现在表中。方法1：顺序查找：方法是一个个寻找，时间复杂度为On。这个方法并没有用到“n个数从小到大排列”这一个关键条件，因而时间效率低下。方法2：二分查找只需要比较log2n个元素。假设需要在aL<=m<=r，如果a>，那么元素只可能在a<，那么元素只可能在a中。合并：不需要合并。方法1：二分查找的递归实现intbsearchintL,intr,int{ifL>rreturn-1;intm=Lr/2;ifa>returnbsearchL,m-1,;elsereturnbsearchm1,r,;}方法2：二分查找的非递归实现：intbsearchintL,intr,int{intm;whileL<=r{m=Lr/2;ifa>r=m–1;elseL=m1;}return-1;//查找不成功}【扩展1】二分查找求下界，即第一次出现的位置intErfenintL,intr,int{intmid;whileL<r{mid=Lr/2;if<=ar=mid;elseL=mid1;}returnL;}【扩展2】二分查找求上界，即最后一次出现位置的后一个位置【思考题目】给出n个整数和m个询问，对于每个询问a,b，输出闭区间内的整数c的个数。【思路点拨】①先把所有的数据从小到大排序；②二分查找求下界，即第一次出现的位置low；③二分查找求上界，即最后一次出现位置的后一个位置high；④答案区间为：ans=high-low【变形1】查找等值点【问题描述】n个不同整数从小到大排序后放在数组A0~An-1中，是否存在i，使得Ai=i？若存在，试找到此点。5、快速幂【问题描述】计算an%，n<=109。方法1：朴素算法。每次乘以a，时间复杂度On。intpowerinta,intn{int=1;fori=1;i<=n;i*=a;return;}方法2：分治算法划分：如果n是偶数，考虑=n/2，否则考虑=n-1/2递归求解：计算a。合并：如果n是偶数，则an=a2，否则an=a2*a根据这个方法很容易写出程序：intpowerinta,intn{ifn==0return1;elseifn%2==1{int=powera,n-1/2;return*%*a%;}else{int=powera,n/2;return*%;}}方法3：用二进制实现快速幂计算cin>>b>>od{ans=ans*ans%;ifa==1ans=b%*ans%;//如果是奇数，就多乘b}cout<<ans<<endl;//输出b^od6、求解线性递推关系【例题】Fibonacci数【题目描述】Fibonacci数列定义为：f=1,f=1。现在请你求Fibonacci数列的第n项。【文件输入】输入文件只有一行为一个整数n1<=n<=2^31-1。【文件输出】输出文件只有一行为一个整数，表示Fibonacci数列的第n项mod32768的值。【样例输入】4【样例输出】3【数据范围】对于20%的数据，1<=n<=1000对于40%的数据，1<=n<=10000000对于100%的数据，1<=n<=2^31-1分析枚举，肯定超时voidprecalc_fibintn{f=1;forinti=2;i<=n;if;}先复习矩阵乘法•两个2*2矩阵相乘的公式为•可用倍增法在Ologn时间内求出幂忽略高精度一般情形7、棋盘覆盖问题分析8、循环日程表问题【例题】比赛安排【问题描述】设有2nn<=6个球队进行单循环比赛,计划在2n-1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为：

队1234

比赛1-23-4第一天

1-32-4第二天

1-42-3第三天【文件输入】一个整数n。【文件输出】输出比赛安排表。【样例输入】2【样例输出】1-23-4

1-32-4

1-42-3初看此题，感觉无法下手，因为没有任何直接可用的算法和数据结构。仔细分析，可以发现，将问题进