浅谈补集转化思想在统计问题中的应用【资料】

《浅谈补集转化思想在统计问题中的应用【资料】》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈补集转化思想在统计问题中的应用目录前言2关键字2摘要2正文2例3题目大意3初步分析3深入思考3补集转化4小结5例二6题目大意6初步分析6几个工具7补集转化7小结8总结9、p亠、▲前s不管是在实际生活中还是在信息学竞赛里，都常常会遇到统计问题，即对满足某些性质的对象进行计数的问题。解决统计问题有一些常用的方法比如离散化、极大化、二分、事件表等等，利用它们基本上可以解决大多数的统计问题。我们不妨将这些方法称为解决统计问题的常规方法。然而世上的任何事物都是既有普遍性，乂有特殊性的。确实存在一部分统计问题，用常规方法是很难甚至是根

2、本无法解决的。对于这些问题，就应该具体情况具体分析，采用非常规的解法。本文中将耍讨论的就是这些非常规解法中的一种一一利用补集转化思想解决统计问题。关键字统计问题常规/非常规（统计）方法枚举时间/思维/编程复杂度补集转化组合计数有序化枚举对象枚举量摘要木文通过对两个例题——单色三角形问题（POI9714）和海战游戏（改编门Urall212）,探讨了补集转化思想在统计问题中的应用，分析比较了补集转化思想在两个例子中的作用效果和价值。最后得出结论：补集转化思想应用于统计问题屮往往有着很好的效果，我们应该注意培养逆向思维，掌握好这种非

3、常规的统计方法。正文统计问题，我们认为是对于满足某些性质的对象进行计数的问题。既然是计数，那么不可避免地，其解法或多或少地建立于枚举Z上。在很多情况下，“枚举”往往是低效的代名词。因此，我们通常所见到的统计问题，其最好解法动辄就达到0（（）、0（1?）的时间复杂度，也因此统计问题的规模往往不是很大，一般都在1000以内。如果光是这样也就罢了，更糟糕的是很多统计问题，按照直观的想法设计出来的算法往往具有令人望而生畏的时间复杂度：要么n的指数过高，耍么题目中给的n就是很大的，或者时间复杂度是关于另外一个很大的量M（往往是表格的尺寸

4、、图的边数等等）的表达式……总之，这个时候的统计问题实在不那么讨人喜欢。丁是我们又需要利用很多技巧来降低复杂度，离散化和极大化思想、二分法、事件表等技术都是非常有用的，在它们的帮助下，我们成功地解决了非常多的刁钻的统计问题，以至于这些技巧也已经成了理所当然的“常规”方法，很多木来棘手的统计问题也成了常规题。然而这些方法显然也冇不那么奏效的时候，这吋我们就需要一些非常规的方法來解决一些更加棘手的问题。这些非常规方法Z—就是利用补集转化思想来帮助解决统计问题。补集转化思想在很多方面有着广泛的应用，让我们来看看在解决统计问题方面它乂

5、有哪些精彩表现吧！例一单色三角形问题(POI9714TRO)题目大意空间里有n个点，任意三点不共线。每两点Z间都用红色或黑色线段(只有一条，非红即黑！)连接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。对于给定的红色线段的列表，找出单色三角形的个数。例如图一中有10条边,输入点数n、红色边数m以及这m条红色的边所连接的顶点标号，输岀单色三角形个数R。3<=n<=1000,0<=m<=250000o初步分析很自然地，我们想到了如下算法：用一个1000*1000的数组记录每两个点之间边的颜色，然后枚举所冇的三角形(这是

6、通过枚举三个顶点实现的)，判断它的三条边是否同色，如果同色则累加到总数R中(当然，初始时R为0)。这个算法怎么样呢？姑月•不论它非常奢侈地需要一个1M的大数组(POI97的时候还没有大内存)，它的时间复杂度已经高达O(C(n,3)),也就是0(2)的级别。对于n最大达到1000的木题来说，实在不能说是个好算法。那些常规的技巧能不能用到本题上呢？离散化和极人化看起來跟本题毫不沾边。由于木题的限制条件非常少，也不是求最值型的计数问题，所以二分和事件表看来也用不上。看来，想要循规蹈矩地解决这题是不可能了，我们需要全新的思路！深入思考

7、話稍进一步分析就会发现，本题中单色三角形的个数将是非常多的，所以一切需耍枚举出每一个单色三角形的方法都是不可能高效的。单纯的枚举不可以，那么组合计数是否可行呢？从总体上进行组合计数很难想到，那么我们尝试枚举每一个点，设法找到一个组合公式来计算以这个点为顶点的单色三角形的个数。这样似乎已经触及到问题的本质了，因为利用组合公式进行计算是非常高效的。但是仔细分析后可以发现，这个组合公式是很难找到的，因为对于枚举确定的点A,以A为一个顶点的单色三角形ABC不仅要满足边AB和边AC同色，而且边BC也要和AB、AC边同色，于是不可能仅仅通

8、过枚举一个顶点A就可以确定单色三角形。经过上面的分析，我们得出枚举+组合计数有可能是正确的解法，但是在组合公式的构造上我们遇到了障碍。这个障碍的本质是：从一个顶点A出发的两条同色的边AB、AC并不能确定一个单色三角形ABC,因为BC边冇可能不同色。C也就是说，我们无法在从同一