二分的应用与补集转换思想.ppt

《二分的应用与补集转换思想.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二分倍增与补集转换思想的应用长沙市第一中学曹利国分治思想分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；分解(Divide)：将原问题分成一系列子问题。解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。合并(combine)；将子问题的结果合并成原问题的解。分治思想如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1＜k＜=n，而且在求出了这些子问题的解之后，还可找到适当的方

2、法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。分治思想问题S问题S问题SS的解问题S1……问题S2问题Si问题Sn……S1的解……S2的解Si的解Sn的解……问题的分解子集解的合并子问题求解分治的应用解决一类求方程的根的问题解决真假硬币的称量问题基于NLgN算法效率的排序和查找问题(归并排序，二分查找)倍增算法快速幂分治的应用(分段处理)例题：取余运算（mod.exe）输入b，p，k的值，编程计算bpmodk的值。其中的b，p，k*k为长整型数。【输入输出样例】mod.in2109mod.out

3、2^10mod9=7分析1、用高精度计算比较烦，复杂度太高2、转而用其他方法求解（1）取模运算的一个规律：a*bmodk=(amodk)*(bmodk)modk（2）运用规律可以把样例数据分解：b19=b2*9+1=b9b9b，其中的指数9可以继续分解为2×4＋1，4再分解程2×2＋0，2＝1×2＋0，1＝0×1＋1。反过来，我们可以从0出发，通过乘以2再加上1或0推得1，2，4，9，19，然后依次以这些数为指数的自然数除以k的余数。分析（3）不难看出，前面乘以2后要加上的1或0就是该数对应二进制数各位上的数字1或0。如，19＝（10011）2。求解的过程也就是将二进制数还原为十进制数的

4、过程。（4）综上所述，该题可采用分治得思想进行递推求解。我们计算出A^(2^k)，即A,A^2,A^4,A^8…这需要logK的时间而我们回答A^K，则根据K的二进制位上的1来相乘A^11=A^8*A^2*A也只需要logK次问题转化再二分例题(北京08省选)：在数轴上有N类点，每一类用S,E,D来表示，意思是这些点分布在S,S+D,S+2D…S+kD(S+kD<=E)已知最多只有一个坐标上有奇数个点，要求找出它或指出不存在。分析我们用0表示偶数个点，1表示奇数个点那么数轴上的点分布如下000000000000000000010000..因为数轴太大，点太多我们无法快速判断1的位置分析0

5、00000000000000000010000..考虑前缀和000000000000000000011111..我们可以用二分法找到0/1分界点，即唯一的1的位置每次二分时，扫描每一类点，统计点的前缀和复杂度O(N*logS)，S为数轴长，即值域二分再转化问题NOIP2010，第三题关押罪犯将N个人分成两组，其中M对人有Ci的不和谐值，其中如果两人在同一组，并且它们两人不和谐，那么就会有Ci的不和谐值。要求找出一个分组方案，使得最大不和谐值最小。分析直接做不好下手由于要求最大值最小，即一个上界，所以我们可以二分这个上界那么我们就能确定哪些人不能在一组(不和谐值大于上界的)此时我们只需判断

6、这个图能否构成二分图即可。用简单的BFS即可解决这个问题用BFS做二分图判定二分图判定:判断一个图能否形成二分图我们从任一点开始，令其在二分图左边，然后开始BFS，每次搜到的点放对面即可，直至所有点放完或出现矛盾正确性：对于每个联通量而言，一个点如果确定，其他点均确定，而这个点放左，放右实际上是对称的方案二分的选择有趣的元素(2011克罗地亚竞赛):如果一个数列中2*K的元素中前K个元素和与后K个元素和都不大于S那么我们说这些元素是有趣的。给你一个长度为N的数列A,求各个元素从本身开始能构成的最长有趣元素的长度。一个简单的想法枚举i，二分最远j使得i~j与j+1~j+j-i+1为有趣的

7、ijj+1j+j-i+1时间复杂度O(NlogN)看似没问题的二分算法其实是错误的如S=100,N个数为11989811当i=1，二分j=2时不合法，而其实j=3时合法错误的原因二分是需要问题满足单调性的形象的说就如刚才讲过的北京省选题，每个点的状态形如:000000000000111111111110代表合法，1代表不合法而不能是凌乱的00010110111010001010000还是可以二分我们考虑枚举起点再二分是不对的但是如果