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

二分倍增与补集转换思想的应用长沙市第一中学曹利国分治思想分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；1.分解(Divide)：将原问题分成一系列子问题。2.解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。3.合并(combine)；将子问题的结果合并成原问题的解。分治思想如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1＜k＜=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。分治思想问题S问题S问题SS的解问题S1……问题S2问题Si问题Sn……S1的解……S2的解Si的解Sn的解……问题的分解子集解的合并子问题求解分治的应用解决一类求方程的根的问题解决真假硬币的称量问题基于NLgN算法效率的排序和查找问题(归并排序，二分查找)倍增算法快速幂分治的应用(分段处理)例题：取余运算（mod.exe）输入b，p，k的值，编程计算bpmodk的值。其中的b，p，k*k为长整型数。【输入输出样例】mod.in2109mod.out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）综上所述，该题可采用分治得思想进行递推求解。我们计算出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的位置分析000000000000000000010000..考虑前缀和000000000000000000011111..我们可以用二分法找到0/1分界点，即唯一的1的位置每次二分时，扫描每一类点，统计点的前缀和复杂度O(N*logS)，S为数轴长，即值域二分再转化问题NOIP2010，第三题关押罪犯将N个人分成两组，其中M对人有Ci的不和谐值，其中如果两人在同一组，并且它们两人不和谐，那么就会有Ci的不和谐值。要求找出一个分组方案，使得最大不和谐值最小。分析直接做不好下手由于要求最大值最小，即一个上界，所以我们可以二分这个上界那么我们就能确定哪些人不能在一组(不和谐值大于上界的)此时我们只需判断这个图能否构成二分图即可。用简单的BFS即可解决这个问题用BFS做二分图判定二分图判定:判断一个图能否形成二分图我们从任一点开始，令其在二分图左边，然后开始BFS，每次搜到的点放对面即可，直至所有点放完或出现矛盾正确性：对于每个联通量而言，一个点如果确定，其他点均确定，而这个点放左，放右实际上是对称的方案二分的选择有趣的元素(2011克罗地亚竞赛):如果一个数列中2*K的元素中前K个元素和与后K个元素和都不大于S那么我们说这些元素是有趣的。给你一个长度为N的数列A,求各个元素从本身开始能构成的最长有趣元素的长度。一个简单的想法枚举i，二分最远j使得i~j与j+1~j+j-i+1为有趣的ijj+1j+j-i+1时间复杂度O(NlogN)看似没问题的二分算法其实是错误的如S=100,N个数为11989811当i=1，二分j=2时不合法，而其实j=3时合法错误的原因二分是需要问题满足单调性的形象的说就如刚才讲过的北京省选题，每个点的状态形如:000000000000111111111110代表合法，1代表不合法而不能是凌乱的00010110111010001010000还是可以二分我们考虑枚举起点再二分是不对的但是如果枚举中间点再二分是没有错的!所以我们枚举中间点，再二分最远扩展距离这样我们得到若干区间，我们将包含的区间去掉再处理一下就能得到答案！用单调队列还可以做到O(N)倍增算法如何设计最少的面值拼出连续最大的面值？答案自然是1,2,4,8..即2^k倍增算法就基于这个性质，我们通过解决所有2^k的问题来解决整个问题倍增算法解决RMQ问题RMQ问题：给定N个数，M个询问(a,b)每次回答第a个数到第b个数中的最小值线段树等常数较大，能不能不利用高级数据结构做到O(NlogN)分析我们用F[i][k]表示从i开始，连续2^k个数的最小值那么有F[i][0]=A[i]容易得到由于2^k个数的最小值是前2^(k-1)个数的最小值或者后2^(k-1)个数的最小值。F[i][k]=min{F[i][k-1],F[i+2^(k-1)][k-1]}分析那么我们很简单的预处理出了F数组主要代码如下读入A[i]，F[i][0]=A[i]循环k=1~logN循环i=1~NF[i][k]=min{F[i][k-1],F[i+2^(k-1)][k-1]}分析至于回答，类似拼钱我们每次找出一张最大面值如回答2~6的最小值我们先找到2^2=4，用F[2][2]更新答案那么现在变成5~6，我们找到2^1=2用F[5][1]更新答案总时间复杂度O(NlogN)，常数小，方便写，容易理解。倍增的其他应用LCA（最近公共祖先问题）或一些静态的树路径询问(树上两点路径权和/最值)我们用F[i][k]表示i到其2^k个祖先的的信息用跟刚才类似的倍增的方法可以在logN的时间内回答询问后缀树组的倍增法构造…例一单色三角形问题（POI9714TRO）题目大意空间里有n个点，其中任意三点不共线。每两点间都有红色或黑色边（只有一条，非红即黑！）连接。若一个三角形的三边同色，则称它为单色三角形。对于给定的点数和红色边的列表，找出单色三角形的个数。例如下图中有5个点，10条边，形成3个单色三角形。输入点数n、红色边数m以及这m条红色的边所连接的顶点标号，输出单色三角形个数R。3=n=1000，0=m=250000。初步分析自然的想法：用一个数组记录每两点间边的颜色。枚举所有的三角形（这是通过枚举三个顶点实现的），判断它的三边是否同色，若同色则总数R加1（当然，初始时R为0）。空间上：O(n2)，需要一个1000*1000的大数组时间上：O(n3)，n达到1000，无法接受！常用技巧：无从下手。深入思考本题中单色三角形的个数可以非常庞大，所以一切需要枚举每个单色三角形的方法都是不可能高效的。单纯的枚举不可以，那么组合计数是否可行呢？从总体上进行组合计数很难想到。我们尝试枚举每一个点，设法找到一个组合公式来计算以这个点为顶点的单色三角形的个数。深入思考组合公式很难找到！原因：从一个顶点A出发的两条同色的边AB、AC并不能确定一个单色三角形ABC，因为BC边有可能不同色。ACB边单色三角形补集转化从反面来看问题：每两点都有边连接，所以每三个点都可以组成一个三角形（单色或非单色的），所有的三角形数S=C(n,3)=n*(n-1)*(n-2)/6。单色三角形数R加上非单色三角形数T就等于S，所以如果我们可以求出T，那么显然，R=S－T。原问题转化为：怎样高效地求出T补集转化原先的枚举＋组合计数算法的障碍是无法在“边”与“单色三角形”之间建立确定的对应关系。边非单色三角形YES!!补集转化非单色三角形的三条边共有红黑两种颜色其中两条边同色，另一条边异色ACB一个非单色三角形两对“有公共顶点的异色边”如果从一个顶点B引出两条异色的边BA、BC，则无论AC边是何种颜色，三角形ABC都只能是一个非单色三角形补集转化ACBACB一对“有公共顶点的异色边”一个非单色三角形OR非单色三角形数T=“有公共顶点的异色边”的总对数Q/2补集转化每个顶点有n-1条边，根据输入的信息可以知道每个顶点i的红边数E[i]，那么其黑边数就是n-1-E[i]。根据乘法原理，以i为公共顶点的异色边的对数就是E[i]*(n-1-E[i])，所以Q很容易求出：niiEniEQ1])[1(*][补集转化Q求出之后，R=S－T=n*(n-1)*(n-2)/6-Q/2时间复杂度：O(m+n)空间复杂度：O(n)优秀的算法！小结通过补集转化，我们在原来无法联系起来的“边”和“三角形”之间建立起确定的关系，并以此构造出组合计数的公式。单纯的枚举枚举+组合计数这个例子中补集转化思想的作用：为找到一个本质上不同的算法创造了条件WC2007剪刀石头布在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到A胜过B，B胜过C而C又胜过A的有趣情况，不妨形象的称之为剪刀石头布情况。有的时候，无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生，即有多少对无序三元组(A,B,C)，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要，将(A,B,C)、(A,C,B)、(B,A,C)、(B,C,A)、(C,A,B)和(C,B,A)视为相同的情况。有N个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。分析题目大意对于一个竞赛图，给定一些边，要求你通过给剩下的边定向，最大化图中的三元环。竞赛图：基础图(将有向边变为无向边)为完全图的有向图三元环：三个点组成的环分析最大化三元环并不好想，利用补集转化三元环的个数P=图中所有由三个点构成的子图个数-这些子图中不是三元环的个数。容易证明，三个点的竞赛图不是三元环的充要条件是图中有一点入度等于2。分析三元环的个数P=图中所有由三个点构成的子图个数A-这些子图中不是三元环的个数B，入度为DiP=A-B=C(n,3)-sigma{C(Di,2)}=n*(n-1)*(n-2)/6-sigma{Di*(Di-1)/2}=n*(n-1)*(n-2)/6-sigma{Di^2}/2+sigmaDi/2=n*(n-1)*(n-2)/6+n*(n-1)/4-sigma{Di^2}/2=n*(n-1)*(n-2)/6+m/2-sigma{Di^2}/2分析可以发现除Di^2外，全为常数项，所以我们的问题转化为最小化sigma{Di^2}即我们需要给每条未定向边定向，使得sigma{Di^2}/2最小。这是一个最小费用流模型,这里不再赘述。至此我们顺利地使用补集转化解决了此题。