浅谈补集转化思想在统计问题中的应用.doc

浅谈补集转化思想在统计问题中的应用.doc:..浅谈补集转化思想在统计问题中的应用目录前言 2关键字 2摘要 2正文 2例一 3题目大意 3初步分析 3深入思考 3补集转化 4小结 5例二 6题目大意 6初步分析 6几个工具 7补集转化 7小结 8总结 9刖言不管是在实际生活中还是在信息学竞赛里,都常常会遇到统计问题,即对满足某些性质的对象进行计数的问题。解决统计问题有一些常用的方法比如离散化、极大化、二分、事件表等等,利用它们基本上可以解决大多数的统计问题。我们不妨将这些方法称为解决统计问题的常规方法。然而世上的任何事物都是既有普遍性,又有特殊性的。确实存在-•部分统计问题,用常规方法是很难甚至是根本无法解决的。对于这些问题,就应该具体情况具体分析,采用非常规的解法。本文中将要讨论的就是这些非常规解法中的一•种一一利用补集转化思想解决统计问题。关键字统计问题常规/非常规(统计)方法枚举时间/思维/编程复杂度补集转化组合计数有序化枚举对•象枚举量摘要本文通过对两个例题——单色三角形问题(POI9714)和海战游戏(改编自Urall212),探讨了补集转化思想在统计问题中的应用,分析比较了补集转化思想在两个例子中的作用效果和价值。最后得出结论:补集转化思想应用于统计问题中往往有着很好的效果,我们应该注意培养逆向思维,掌握好这种非常规的统计方法。正文统计问题,我们认为是对于满足某些性质的对象进行计数的问题。既然是计数,那么不可避免地,其解法或多或少地建立于枚举之上。在很多情况下,“枚举”往往是低效的代名词。因此,我们通常所见到的统计问题,其最好解法动辄就达到0(子)、0(!?)的时间复杂度,也因此统计问题的规模往往不是很大,-•般都在1000以内。如果光是这样也就罢了,更糟糕的是很多统计问题,按照直观的想法设计出来的算法往往具有令人望而生畏的时间复杂度:要么n的指数过高,要么题目中给的n就是很大的,或者时间复杂度是关于另外一个很大的量M(往往是表格的尺寸、图的边数等等)的表达式……总之,这个时候的统计问题实在不那么讨人喜欢。于是我们又需要利用很多技巧来降低复杂度,离散化和极大化思想、二分法、事件表等技术都是非常有用的,在它们的帮助下,我们成功地解决了非常多的刁钻的统计问题,以至于这些技巧也己经成了理所当然的“常规”方法,很多本来棘手的统计问题也成了常规题。然而这些方法显然也有不那么奏效的时候,这时我们就需要一些非常规的方法来解决一些更加棘手的问题。这些非常规方法之一就是利用补集转化思想来帮助解决统计问题。补集转化思想在很多方面有着广泛的应用,让我们来看看在解决统计问题方面它又有哪些精彩表现吧!例一单色三角形问题(POI9714TRO)题目大意空间里有n个点,任意三点不共线。每两点之间都用红色或黑色线段(只有一条,非红即黑!)连接。如果一个三角形的三条边同色,则称这个三角形是单色三角形。对于给定的红色线段的列表,找出单色三角形的个数。例如图一中有5个点,10条边,形成3个单色三角形。输入点数n、红色边数m以及这m条红色的边所连接的顶点标号,输出单色三角形个数R。3<=n<=1000,0<=m<=250000o初步分析很自然地,我们想到了如下算法:用一个1000*1000的数组记录每两个点之间边的颜色,然后