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

* * * * * * * * * * * * * * * * * * 补集转化 非单色三角形的三条边共有红黑两种颜色 其中两条边同色，另一条边异色 A C B 一个非单色三角形 两对“有公共顶点的异色边” 如果从一个顶点B引出两条异色的边BA、BC，则无论AC边是何种颜色，三角形ABC都只能是一个非单色三角形 补集转化 A C B A C B 一对“有公共顶点的异色边” 一个非单色三角形 OR 非单色三角形数T=“有公共顶点的异色边”的总对数Q/2 补集转化 每个顶点有n-1条边，根据输入的信息可以知道每个顶点i的红边数E[i]，那么其黑边数就是n-1-E[i]。根据乘法原理，以i为公共顶点的异色边的对数就是E[i]*(n-1-E[i])，所以 Q很容易求出： 补集转化 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 + sigma Di/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 最小。这是一个最小费用流模型,这里不再赘述。 至此我们顺利地使用补集转化解决了此题。 * * * * * * * * * * * * * * * * * * * * * * 二分倍增与补集转换思想的应用 长沙市第一中学 曹利国 分治思想 分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下； 分解(Divide)：将原问题分成一系列子问题。 解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。 合并(combine)；将子问题的结果合并成原问题的解。 分治思想 如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1＜k＜=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。 分治思想 问题S 问题S 问题S S的解 问题S1 …… 问题S2 问题Si 问题Sn …… S1的解