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

浅谈补集转化思想在统计问题中的应用WinterCamp2003论文芜湖一中许智磊前言统计问题，是我们经常遇到的一类问题通常认为统计问题是对满足某些性质的对象进行计数的问题“枚举”往往是低效的代名词！！其解法或多或少地建立于枚举之上前言很多时候，我们就需要一些技巧来降低统计的时间复杂度离散化和极大化思想、二分法、事件表等方法经常可以起到很好的效果。因此它们作为常规的统计方法，在解题时首先被想到。前言然而这些常规方法也有不能奏效的时候这时我们就需要一些非常规的方法来解决问题其中的一种就是利用补集转化思想来帮助解决统计问题补集转化思想在很多方面有着广泛的应用，让我们来看看在解决统计问题方面它又有哪些精彩表现吧！例一单色三角形问题（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)优秀的算法！小结通过补集转化，我们在原来无法联系起来的“边”和“三角形”之间建立起确定的关系，并以此构造出组合计数的公式。单纯的枚举枚举+组合计数这个例子中补集转化思想的作用：为找到一个本质上不同的算法创造了条件例二海战游戏（改编自Ural1212SeaBattle）题目大意海战游戏是在一个N行M列的方格棋盘上摆放“军舰”，一艘军舰是连在一起的X行Y列方格，每个方格都全等于棋盘上的格子，于是军舰就可以摆放在棋盘上，使军舰的每个格子和棋盘的格子重合。摆放时必须遵守如下规则：任意两艘军舰的任意两个格子不得重合或在八个方向（即上、下、左、右、左上、右上、右下、左下）上相邻。现在已经摆放了L艘军舰（符合摆放的规则），下一步想要再摆放一个P行Q列的军舰，求出共有多少种不同的可能摆放方案。输入N、M、L，已经摆放的L艘军舰的信息（左上角和右下角的行列坐标），以及下一步要摆放的军舰的大小P、Q，输出方案数R。其中2=N,M=30000，0=L=30，1=P,Q=5。我们认为所有已摆放的军舰大小都在P*Q这样的规模。例如左图中已经摆放了一个1行2列的军舰和一个2行1列的军舰，如果我们要再摆一个1行2列的军舰，有两种方案。如果要再摆一个2行2列的军舰，只有一种方案。初步分析枚举每一种摆放方案并判断是否符合规则显然不可接受原题就是给定了一个网格，上面某些矩形区域已经被占用，现在要在里面放入一个新的矩形，不能和已被占用的格子重合或是相邻。这是典型的在有障碍点的网格上求摆放方案数的统计问题。看起来如此经典的问题，用常规的方法能否解决呢？初步分析实际上，用离散化可以设计出能够接受的算法。离散化的算法时间复杂度为O(min{M,N}*L)虽然对于原题勉强可以应付，但是一旦数据规模再稍稍扩大一点，必定超时。而且离散化的算法思考比较复杂，编程比较烦琐。几个工具在进一步地思考之前，我们先明确几个小问题，以作为下面研究的工具。在一个X行Y列的矩形A中放入一个P行Q列的矩形B，共有多少种摆放方案？结论一：矩形B能够放入矩形A中的充要条件是X=P且Y=Q，所以如果XP或YQ，方案数为0。否则矩形B的左上角可以位于矩形A的1至X-P+1行，1至Y-Q+1列，也就是总共有(X-P+1)*(Y-Q+1)种摆放方案。矩形A的左上角为(AX1,AY1)，右下角为(AX2,AY2)，矩形B的左上角为(BX1,BY1)，右下角为(BX2,BY2)，如果存在某两个格子a∈A，b∈B且a、b相邻或重合，就称A和B“相交”。如何判断A、B是否相交？这个问题稍稍复杂一点，但是仔细分析各种情况之后可以得出结论二：A和B相交的充要条件是(AX1=BX2+1)and(AX2=BX1-1)and(AY1=BY2+1)and(AY2=AY1-1)。几个工具X行Y列几个工具P行Q列2Q+Y列2P+X行设一个已经摆放的矩形A为X行Y列，新摆放的矩形B为P行Q列，矩形B怎样摆放才能和矩形A相交呢？根据结论二我们直接就可以得出结论三：矩形B能够与A相交的所有摆放方案位于一个2P+X行，2Q+Y列的矩形框内。这个矩形框是在矩形A的上、下各扩展P行，左、右各扩展Q列得到的。如动画所示，正中的黑色矩形代表已摆放的矩形A，闪烁的绿色矩形代表新矩形B能够与A相交的所有方案。几个工具当然，这样说还不是太严密，因为这个矩形框有可能超出了棋盘的边界，此时它的边就要调整到棋盘边界内。所以我们把结论三改为：矩形B能够与A相交的所有方案位于一个最多2P+X行，最多2Q+Y列的矩形框内。补集转化符合规则的摆放方案数R+违反规则的摆放方案数T=总共的摆放方案数S问题转化为：怎样高效地求出T根据结论一，S可以根据公式计算出来T也就是所有与已经摆放的军舰相交的方案数符合规则的摆放方案数R＝总共的摆放方案数S－违反规则的摆放方案数T补集转化不能简单地枚举每一艘已经摆放的军舰，计算与它相交的摆放方案数并累加起来。因为有些摆放方案会同时和不止一个军舰相交，例如下图中的蓝色矩形C同时和两个黑色矩形A与B相交矩形A矩形B矩形C排除重复的方法：有序化，只有在统计与某个方案相交的编号最小的已摆放军舰时才允许这个方案计入总数例如我们规定矩形A编号较小，则在处理矩形B时，方案C就不允许计入总数，因为矩形B并不是与方案C相交的编号最小的已摆放矩形。补集转化为了做到这一点，我们只需采取如下算法：依次处理每个已经摆放的矩形，设当前处理的矩形编号为i。在这个矩形周围一一枚举与它相交的摆放方案。对于每个方案，再依次枚举编号为1,2,……(i-1)的矩形，判断这些矩形能否与当前枚举的方案相交，如果发现有相交的情况，则此方案不能计入总数T，否则就将T加1。补集转化根据结论三，与每个已摆放的X行Y列的矩形相交的摆放方案位于它周围的一个矩形框内，这个矩形框最多2P+X行，最多2Q+Y列。再根据结论一，在其中摆放P行Q列的矩形最多只有(P+X+1)*(Q+Y+1)种方案。由于每个矩形的大小均在P*Q这样的级别，所以总共需要处理的方案数规模为O(P*Q*L)。对于每个方案，最多只需要枚举L－1个已摆放矩形判断是否与之相交。补集转化总共需要处理的方案数规模为O(P*Q*L)根据结论二，判断两个矩形是否相交的复杂度为O(1)。处理每个方案的复杂度为O(L)整个算法的复杂度仅为O(P*Q*L2)补集转化思维复杂度、编程复杂度较低在时间复杂度上，大大领先于离散化的常规解法小结本题从正面考虑，枚举量太大，所以常规的解法是采用离散化技巧来减少枚举量。但是从反面考虑，枚举量就非常小了。补集转化思想在这里起到的作用是帮助我们选择了合适的枚举对象，从而减少了枚举量。总结比较：两个例子都是利用补集转化思想解决统计问题不同点作用效果意义价值例一中指导我们设计出了本质不同的新算法似乎是解决这个问题的唯一可行方法例二中只是通过改变枚举对象减少了枚举量比常规方法更自然、更优秀的另一种方法相同点求解目标R较困难求R的补集T以及R、T的总和S相对较容易总结补集转化思想应用于统计问题的形式是多种多样的，可能从解决问题的各个方面帮助我们。补集转化思想不仅可以应用于一些非常规的统计问题，而且对于一些常规算法能够解决的问题，应用补集转化思想也许可以做得更好。总结补集转化思想，体现了矛盾对立统一，互相转化的一种哲学观念。在统计问题中灵活地应用补集转化思想，往往可以起到“出奇制胜”的效果，而这就要求我们注意培养逆向思维的能力，才能用好、用活补集转化思想。值得注意的是，利用补集转化思想解决统计问题作为一种非常规的统计方法，和一些常规的统计方法、技巧之间的关系是辨证的。虽然在本文的例子中，补集转化思想都优于常规方法，但是并不能认为常规方法一定不如非常规方法。大多数的统计问题，还是适合使用常规方法的。总结只有将常规方法和非常规方法都灵活地掌握，并对于具体问题选择合适的方法，才能够游刃有余地解决统计问题。感谢我的演讲到此结束，谢谢大家！