思维训练 - 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 ...

最小表示法及其证明

问题

对于一个字符串S,求S的循环的同构字符串S’中字典序最小的一个。

我们举例说明,字符串"abcd"的循环同构字符串有:["abcd", "bcda", "cdab", "dabc"]

题目的目标是求这些字符串中字典序最小的那个。

暴力解法

暴力解法非常直观,直接枚举字符串的起点,然后找到构成最小字符串的那一个。

代码就不在这里写了。

最小表示法

最小表示法是解决同构字符串最小表示的巧妙算法。

其算法描述如下:

令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i] == S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S …
more ...

Single Number Problem

Introduction

There are a lot of interview problem based on the 1D-array, which is the one of the easiest "data structure".

But the problem about that simple data structure might not be that simple. Here is the summary of the problem about 1D-array.

Of course, most of them come from …

more ...

Codeforces 447D DZY Loves Modification

题意

给你一个n * m的矩阵,让你做K次操作,使得最后得到的值最大。

操作有两种:

一是在任意一行上操作,最终的结果值加上这一行数的和,然后这一行每一个数都要减去p。

二是在任意一列上操作,最终的结果值加上这一列数的和,然后这一列每一个数都要减去p。

数据范围:1 ≤ n, m ≤ 10^3; 1 ≤ k ≤ 10^6; 1 ≤ p ≤ 100

退化版的题目思路

如果我们只限定一种操作,此题就是简单题了。我们维护一个大根堆,堆中保存每一行(或列)之和。

每次操作只需要取出最大值,加到最终结果上。之后将这个值减去对应的p * n(或p * m),再加入堆中。

经过K次循环,就可以得到最后的答案了。

真正的题目思路

对于行和列同时操作,我们也可以套用这种方法。但是要解决对行操作后,对列上数字的值的影响 …

more ...

玩玩算法题1:Sherlock and Queries

题目大意

给你三个数组:A[N], B[M], C[M]。让你按如下pseudo-code给出的规则计算,求出最终A[N]每一项的值。

for i = 1 to M do
    for j = 1 to N do
        if j % B[i] == 0 then
            A[j] = A[j] * C[i]
        endif
    end do
end do

数据范围

1≤ N,M ≤ 10^5

1 ≤ B[i …

more ...

Codeforces Round #253 Tutorial


443A - Anton and Letters

Simple and easy, solved by two lines of python code.

ls = filter(lambda y: y, map(lambda x: x.strip(), raw_input()[1:-1].split(",")))
print len(set(ls))

443B - Kolya and Tandem Repeat

Brute force. Just enumerate the beginning and the end of the substring, and …

more ...