算法合集之《浅谈补集转化思想在统计问题中的应用》.ppt

《算法合集之《浅谈补集转化思想在统计问题中的应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈补集转化思想在统计问题中的应用WinterCamp2003论文　芜湖一中　许智磊前言统计问题，是我们经常遇到的一类问题通常认为统计问题是对满足某些性质的对象进行计数的问题“枚举”往往是低效的代名词！！其解法或多或少地建立于枚举之上前言很多时候，我们就需要一些技巧来降低统计的时间复杂度离散化和极大化思想、二分法、事件表等方法经常可以起到很好的效果。因此它们作为常规的统计方法，在解题时首先被想到。前言然而这些常规方法也有不能奏效的时候这时我们就需要一些非常规的方法来解决问题其中的一种就是利用补集转化思想来帮助解决统计问题补集

2、转化思想在很多方面有着广泛的应用，让我们来看看在解决统计问题方面它又有哪些精彩表现吧！例一　单色三角形问题（POI9714TRO）题目大意空间里有n个点，其中任意三点不共线。每两点间都有红色或黑色边（只有一条，非红即黑！）连接。若一个三角形的三边同色，则称它为单色三角形。对于给定的点数和红色边的列表，找出单色三角形的个数。例如下图中有5个点，10条边，形成3个单色三角形。输入点数n、红色边数m以及这m条红色的边所连接的顶点标号，输出单色三角形个数R。3<=n<=1000，0<=m<=250000。初步分析自然的想法：用一个数

3、组记录每两点间边的颜色。枚举所有的三角形（这是通过枚举三个顶点实现的），判断它的三边是否同色，若同色则总数R加1（当然，初始时R为0）。空间上：O(n2)，需要一个1000*1000的大数组时间上：O(n3)，n达到1000，无法接受！常用技巧：无从下手。深入思考本题中单色三角形的个数可以非常庞大，所以一切需要枚举每个单色三角形的方法都是不可能高效的。单纯的枚举不可以，那么组合计数是否可行呢？从总体上进行组合计数很难想到。我们尝试枚举每一个点，设法找到一个组合公式来计算以这个点为顶点的单色三角形的个数。深入思考组合公式很难找

4、到！原因：从一个顶点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!!补集转化非单

5、色三角形的三条边共有红黑两种颜色其中两条边同色，另一条边异色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

6、很容易求出：补集转化Q求出之后，R=S－T=n*(n-1)*(n-2)/6-Q/2时间复杂度：O(m+n)空间复杂度：O(n)优秀的算法！小结通过补集转化，我们在原来无法联系起来的“边”和“三角形”之间建立起确定的关系，并以此构造出组合计数的公式。单纯的枚举枚举+组合计数这个例子中补集转化思想的作用：为找到一个本质上不同的算法创造了条件例二　海战游戏（改编自Ural1212SeaBattle）题目大意海战游戏是在一个N行M列的方格棋盘上摆放“军舰”，一艘军舰是连在一起的X行Y列方格，每个方格都全等于棋盘上的格子，于是军舰就可

7、以摆放在棋盘上，使军舰的每个格子和棋盘的格子重合。摆放时必须遵守如下规则：任意两艘军舰的任意两个格子不得重合或在八个方向（即上、下、左、右、左上、右上、右下、左下）上相邻。现在已经摆放了L艘军舰（符合摆放的规则），下一步想要再摆放一个P行Q列的军舰，求出共有多少种不同的可能摆放方案。输入N、M、L，已经摆放的L艘军舰的信息（左上角和右下角的行列坐标），以及下一步要摆放的军舰的大小P、Q，输出方案数R。其中2<=N,M<=30000，0<=L<=30，1<=P,Q<=5。我们认为所有已摆放的军舰大小都在P*Q这样的规模。例如左

8、图中已经摆放了一个1行2列的军舰和一个2行1列的军舰，如果我们要再摆一个1行2列的军舰，有两种方案。如果要再摆一个2行2列的军舰，只有一种方案。初步分析枚举每一种摆放方案并判断是否符合规则显然不可接受原题就是给定了一个网格，上面某些矩形区域已经被占用，现在要在里面放入一个新的矩形，不能和已