思维训练 - Thinkin' in induction 2

最大导出子图(maximal induced graph)

你现在在组织一个学术会议。现在你有一份人员名单。假定名单中的每一个人都同意到达,并且有充足的时间交流意见。同时,每一个科学家都写下了他愿意与其进行交流的科学家的名字。

现在,问题来了:挖掘机技术哪家强?

如果要保证每一位科学家至少能与k位到场的科学家进行深入的交♂流♂。那么我们最多可以邀请多少人到会?

注:如果A愿意和B交流,AB一定会进行交流。反之亦然。

我们可以把问题转化成数学语言:对于一个无向图G=(V, E),试求得G的最大导出子图H,使得H中所有顶点的度大于或等于k,或者证明这样的子图是不存在的。

我们继续使用归纳的思想来解决这个问题。

易得,对于顶点数为k的图,如果存在k-导出子图,则该图必为一个完全图。

假设,对于任意顶点数小于n的图,我们总可以找到图的k-最大导出子图。

对于有n个顶点的图G来说,如果有任意顶点的度小于k,那么对于图G的任意子图,此顶点的度总小于k。

所以,对于图中任意度小于k的点,必然不属于所求的子图。于是,我们每次删除一个不属于k-导出子图的点,就可以把有n个顶点的图问题化归为n-1顶点的图问题。

一对一映射

给定一个集合A和一个映射关系f。求A的一个子集S,使得f对于S是一个一对一映射 …

more ...

思维训练 - Thinkin' in induction

热身题 - 24Game

原题请戳我

题意

给你一个包含整数1...n的集合S。接下来进行n-1次操作,每次操作从集合S中选取两个数,在加、减、乘三种运算中选取一种,将结果放回再集合S。在n-1次操作完成后,集合S中只剩下一个数。求问一种取数和运算策略,使最后的结果为24。

举例:

S = [1, 2, 3, 4, 5]

我们选取(2, 5),并进行加法运算,获得结果7。再将7放回集合S中。

此时,S = [1, 3, 4, 7]。

数据范围

1 <= n <= 100000

解答

建议:请思考10分钟后再来看答案

我们日常写代码,往往是为了实现一个功能或者实现一套逻辑。这时候,我们做的事一般是从零开始,然后逐步迭代,最终实现目标。

这是正常的一种思维方式,也是不错的思维 …

more ...