《算法合集之浅谈补集转化思想在统计问题中的应用》由会员分享，可在线阅读，更多相关《算法合集之浅谈补集转化思想在统计问题中的应用（10页珍藏版）》请在金锄头文库上搜索。
1、浅谈补集转化思想在统计问题中的应用 目录前言2关键字2摘要2正文2例一3题目大意3初步分析3深入思考3补集转化4小结5例二6题目大意6初步分析6几个工具7补集转化7小结8总结9前言不管是在实际生活中还是在信息学竞赛里，都常常会遇到统计问题，即对满足某些性质的对象进行计数的问题。解决统计问题有一些常用的方法比如离散化、极大化、二分、事件表等等，利用它们基本上可以解决大多数的统计问题。我们不妨将这些方法称为解决统计问题的常规方法。然而世上的任何事物都是既有普遍性，又有特殊性的。确实存在一部分统计问题，用常规方法是很难甚至是根本无法解决的。对于这些问题，就应该具体情况具体分析，采用非常规的解法。本文
2、中将要讨论的就是这些非常规解法中的一种利用补集转化思想解决统计问题。关键字统计问题常规非常规（统计）方法枚举时间思维编程复杂度补集转化组合计数有序化枚举对象枚举量摘要本文通过对两个例题单色三角形问题（POI9714）和海战游戏（改编自Ural1212），探讨了补集转化思想在统计问题中的应用，分析比较了补集转化思想在两个例子中的作用效果和价值。最后得出结论：补集转化思想应用于统计问题中往往有着很好的效果，我们应该注意培养逆向思维，掌握好这种非常规的统计方法。正文统计问题，我们认为是对于满足某些性质的对象进行计数的问题。既然是计数，那么不可避免地，其解法或多或少地建立于枚举之上。在很多情况下，“枚
3、举”往往是低效的代名词。因此，我们通常所见到的统计问题，其最好解法动辄就达到O(n2)、O(n3)的时间复杂度，也因此统计问题的规模往往不是很大，一般都在1000以内。如果光是这样也就罢了，更糟糕的是很多统计问题，按照直观的想法设计出来的算法往往具有令人望而生畏的时间复杂度：要么n的指数过高，要么题目中给的n就是很大的，或者时间复杂度是关于另外一个很大的量M（往往是表格的尺寸、图的边数等等）的表达式总之，这个时候的统计问题实在不那么讨人喜欢。于是我们又需要利用很多技巧来降低复杂度，离散化和极大化思想、二分法、事件表等技术都是非常有用的，在它们的帮助下，我们成功地解决了非常多的刁钻的统计问题，以
4、至于这些技巧也已经成了理所当然的“常规”方法，很多本来棘手的统计问题也成了常规题。然而这些方法显然也有不那么奏效的时候，这时我们就需要一些非常规的方法来解决一些更加棘手的问题。这些非常规方法之一就是利用补集转化思想来帮助解决统计问题。补集转化思想在很多方面有着广泛的应用，让我们来看看在解决统计问题方面它又有哪些精彩表现吧！例一单色三角形问题（POI9714 TRO）题目大意图一空间里有n个点，任意三点不共线。每两点之间都用红色或黑色线段（只有一条，非红即黑！）连接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。对于给定的红色线段的列表，找出单色三角形的个数。例如图一中有5个点，10条
5、边，形成3个单色三角形。输入点数n、红色边数m以及这m条红色的边所连接的顶点标号，输出单色三角形个数R。3=n=1000，0=m=250000。初步分析很自然地，我们想到了如下算法：用一个1000*1000的数组记录每两个点之间边的颜色，然后枚举所有的三角形（这是通过枚举三个顶点实现的），判断它的三条边是否同色，如果同色则累加到总数R中（当然，初始时R为0）。这个算法怎么样呢？姑且不论它非常奢侈地需要一个1M的大数组（POI97的时候还没有大内存），它的时间复杂度已经高达O(C(n,3)，也就是O(n3)的级别。对于n最大达到1000的本题来说，实在不能说是个好算法。那些常规的技巧能不能用到本
6、题上呢？离散化和极大化看起来跟本题毫不沾边。由于本题的限制条件非常少，也不是求最值型的计数问题，所以二分和事件表看来也用不上。看来，想要循规蹈矩地解决这题是不可能了，我们需要全新的思路！深入思考稍稍进一步分析就会发现，本题中单色三角形的个数将是非常多的，所以一切需要枚举出每一个单色三角形的方法都是不可能高效的。单纯的枚举不可以，那么组合计数是否可行呢？从总体上进行组合计数很难想到，那么我们尝试枚举每一个点，设法找到一个组合公式来计算以这个点为顶点的单色三角形的个数。这样似乎已经触及到问题的本质了，因为利用组合公式进行计算是非常高效的。但是仔细分析后可以发现，这个组合公式是很难找到的，因为对于枚
7、举确定的点A，以A为一个顶点的单色三角形ABC不仅要满足边AB和边AC同色，而且边BC也要和AB、AC边同色，于是不可能仅仅通过枚举一个顶点A就可以确定单色三角形。经过上面的分析，我们得出枚举组合计数有可能是正确的解法，但是在组合公式的构造上我们遇到了障碍。这个障碍的本质是：ACB图二一从一个顶点A出发的两条同色的边AB、AC并不能确定一个单色三角形ABC，因为BC边有可能不同色。也就是说，我们无法在从同一个顶点出发的某两条边与所有的单色三角形之间建立一种确定的对应关系。补集转化让我们换一个角度，从反面来看问题：因为每两点都有边连接，所以每三个点都可以组成一个三角形（单色或非单色的），那么所有
8、的三角形数S=C(n,3)=n*(n-1)*(n-2)/6。又因为单色三角形数R加上非单色三角形数T就等于S，所以如果我们可以求出T，那么显然，R=ST。于是原问题就等价于：怎样高效地求出T。纯枚举的算法想都不用想就被排除，那么在上面分析中夭折的枚举组合计数的算法又怎样呢？这个算法原先的障碍是无法在“某两条边”与“单色三角形”之间建立确定的对应关系。那么有公共顶点的某两条边与非单色三角形之间是否有着确定的关系呢？对了！这种关系是明显的：ACB图三非单色三角形的三条边，共有红黑两种颜色，也就是说，只能是两条边同色，另一条边异色。假设同色的两条边顶点为A，另外两个顶点为B和C，则从B点一定引出两条
9、不同色的边BA和BC，同样，从C点引出两条不同色的边CA和CB。这样，一个非单色三角形对应着两对“有公共顶点的异色边”。另一方面，如果从一个顶点B引出两条异色的边BA、BC，则无论AC边是何种颜色，三角形ABC都只能是一个非单色三角形。也就是说，一对“有公共顶点的异色边”对应着一个非单色三角形。ACBACBOR图四很明显，我们要求的非单色三角形数T就等于所有“有公共顶点的异色边”的总对数Q的一半。而这个总对数是很好求的：每个顶点有n-1条边，根据输入的信息可以知道每个顶点i的红边数Ei，那么其黑边数就是n-1-Ei。枚举顶点A，则根据乘法原理，以A为公共顶点的异色边的对数就是Ei*(n-1-E
10、i)。所以 求出Q之后，答案R=ST=n*(n-1)*(n-2)/6-Q/2。这个算法的时间复杂度仅为O(m+n)，空间复杂度是O(n)，非常优秀。直观的枚举算法无法实现，常用的技巧没有用武之地考虑枚举组合计数正面分析，组合公式很难构造从反面思考（补集转化思想），得到突破小结在这个例子中，我们经历了如下的思维过程：补集转化思想在其中起着至关重要的作用：通过补集转化，我们才能够在原来无法联系起来的“边”和“三角形”之间建立起确定的关系，并以此构造出组合计数的公式。这样，就由单纯的枚举算法改为了枚举+组合计数的算法，大大降低了时间和空间复杂度。在这里，补集转化思想的作用体现在为找到一个本质上不同的
11、算法创造了条件。例二海战游戏（改编自Ural1212 Sea Battle）题目大意“海战游戏”是在一个N行M列的方格棋盘上摆放“军舰”，一艘军舰是连在一起的X行Y列方格，每个方格都全等于棋盘上的格子，于是军舰就可以摆放在棋盘上，使军舰的每个格子和棋盘的格子重合。但摆放时必须遵守如下规则：任意两艘军舰的任意两个格子不得重合或相邻（指在上、下、左、右、左上、右上、右下、左下八个方向上相邻）。现在已经摆放了L艘军舰（符合摆放的规则），下一步想要再摆放一个P行Q列的军舰，求出共有多少种不同的可能摆放方案。输入N、M、L，已经摆放的L艘军舰的信息（左上角和右下角的行列坐标），以及下一步要摆放的军舰的大小P、Q，输出方案数R。其中2=N,M=30000，0=L=30，1=P,Q=P且Y=Q，所以如果XP或YQ，方案数为0。否则矩形B的左上
