连并查集都忘记是怎么回事了，实在是不应该。还是复习一下为妙。
poj2524这一题是并差集的简单应用，先从这题开始。

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

input:
The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

output:
For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

sample input
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
sample output
Case 1: 1
Case 2: 7
题目描述
​世界上有许多不同的宗教，要记录全部是很困难的。你有兴趣找出在你所在的大学，有多少不同宗教信仰的学生。

你所在的大学有n个学生(0 < n <= 50000).问遍所有学生的宗教信仰是不实际的。并且，一些学生对于表达他们的信仰会觉得不舒服。一个避免这些问题的解决办法是问m(0 <= m <= n(n-1)/2)对学生，他们是否属于同一个宗教(也就是他们同时出现在相同的教堂).从这些数据里，你不能知道每一个人的信仰，但是可以知道校园里宗教数量的一个上界。你可以假设一个学生至多属于一个宗教。

输入：
输入中包含一些测试用例。每个例子由一行包含整数n和m开始。接下来的m行由两个整数i和j组成,i和j属于同一个宗教.学生从1到n编号.输入的结束由一行n = m = 0标示.

输出：
每一个测试用例，输出一个数字标示第几个测试用例(从1开始)跟着是这所大学的所有学生可能的最大宗教信仰数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <stdio.h>
#include <iostream>
using namespace std;
const int MAX=50001;
int father[MAX];
int rank[MAX];
void make_set(int x) {
    father[x] = x;
    rank[x] = 1;
}
int find_set(int x) {
    if (x != father[x]) {
        father[x] = find_set(father[x]);
    }
    return father[x];
}
void union_set(int x, int y) {
    int fx = find_set(x);
    int fy = find_set(y);
    if (fx == fy)
        return;
    if (rank[fx] > rank[fy]) {
        father[fy] = fx;
        rank[fx] += rank[fy] ;
    } else {
        rank[fy] += rank[fx];
        father[fx] = fy;
    }
}
int main() {
    int n, m, a, b;
    int test_case = 0;
    while (true) {
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0) {
            break;
        }
        test_case++;
        for (int i = 1; i <= n; i++) {
            make_set(i);
        }
        while (m--) {
            scanf("%d %d", &a, &b);
            union_set(a, b);
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (i == father[i]) {
                count++;
            }
        }
        printf("Case %d: %d\n", test_case, count);
    }
    return 0;
}

最近又玩了一遍manufactoria,发现有些关卡都快忘记怎么过的，这次还是写下来好了。
关卡按照从左到右，从上到下计数。
1. Move robots from the entrance(top) to the exit (bottom)! 将机器从入口(顶部)移到出口(底部)!
简单，不多说
2. If a robot’s string starts with blue, accept. Otherwise, reject! 如果机器以蓝色字符开头，则接受。否则，丢弃。
3. ACCEPT:if there are three or more blues! 如果有三个或三个以上的蓝色的，则接受
4. ACCEPT: if a robot contains NO red! 如果机器不包含红色的，则接受。
5. OUTPUT:The input,but with the first symbol at the end! 对于输入的字符，将第一个字符移到末尾作为输出
6. ACCEPT: if the tape has only alternating colors! 如果只存在交替字符，则接受。
意思就是字符如果是交替出现的则接受，如蓝红蓝红蓝，红蓝红蓝等等，而蓝蓝红，红蓝蓝等出现连续相同的字符，所以不接受
7. OUTPUT：Replace blue with green, and red with yellow! 输出：将蓝色换成绿色，将红色换成黄色。
8. ACCEPT: if the tape ends with two blues! 如果末尾是两个蓝色，则接受。
9. OUTPUT： Put a green at the begining, and a yellow at the end! 输出： 对于输入的字符，在开头中添加一个绿色字符，在末尾中添加一个黄色字符。
10. ACCEPT: Strings that begin and end with the same color! 如果开始字符和结束字符时相同，则接受。
11. ACCEPT: With blue as 1 and red as 0, accept odd binary string! 把蓝色当做1，红色当做0， 接受奇数二进制数。
其实就是接受蓝色结尾的字符。
12. ACCEPT: Some number of blue, then the same number of red! 接受： 一些蓝色的，然后相同数量的红色的。
也就是接受诸如蓝蓝红红，蓝蓝蓝红红红等，当然空字符也要接受，因为空字符代表0个蓝色，0个红色。
解决办法是每次除去一个蓝色和红色
13.OUTPUT: Swap blue for red, and red for blue! 输出： 将蓝色换成红色，红色换成蓝色。
也就是将字符串中的颜色互换。
14. OUTPUT: All of the blue, but none of the red! 输出字符串中的所有蓝色字符，不输出红色字符。
也就是将字符串中的所有红色字符去掉，留下蓝色的。
15. OUTPUT： The input, but with the last symbol moved to the front! 输出： 对于输入的字符，将最后一个字符移动最前面。
在末尾添加一个绿色，用来标示最后一个字符
16. OUTPUT: With blue as 1 and red as 0, multiply by 8! 输出：把蓝色当做1，红色当做0，将二进制字符串乘以8.
其实也就是在字符串末尾添加3个0，也就是添加三个红色
17.ACCEPT: With blue as 1 and red as 0, accept binary strings > 15! 接受：把蓝色当做1，红色当做0，接受大于15的字符串。
18. An equal number of blue and red, in any order! 只要字符串中包含相同个数的蓝色和红色，则接受。
使用与12相同的办法
19.OUTPUT：Put a yellow in the middle of the (even-lenght) string! 输出： 在字符串（偶数个字符串）的中间放置一个黄色字符。
在头尾都添加黄色，之后每个循环，头部的向前移一步，尾部的向后移一步。
20.ACCEPT: X blue, then X red, then X more blue, for any X! 接受： X个蓝色，然后X个红色，接着X个蓝色，对于X没有限制。
也就是接受蓝红蓝，蓝蓝红红蓝蓝等字符串，对于空字符也接受，因为它代表0个蓝色，然后0个红色，接着0个蓝色。
使用与12题相同的办法
21.OUTPUT: The input, but with all blues moved to the front! 输出：对于输入，将字符串中所有的蓝色移到前面。
逆向思维，将红色字符移到后面
22.OUTPUT: With blue as 1 and red as 0, add 1 to the binary string! 输出： 将蓝色当做1，红色当做0，将二进制字符串加上1.
在末尾添加一个黄色，每个循环，如果黄色左边的是蓝色，则蓝色变成红色，并且黄色左后退一个字符，
如果黄色左边的红色，则将红色变成蓝色，程序结束。
23. ACCEPT: With blue as 1 and red as 0, accept natural powers of four! 接受：把蓝色当做1，红色当做0，接受四的开方
24.ACCEPT: (Even-length) strings that repeat midway through! 接受：(偶数长度)接受从中间开始重复的字符串
意思就是接受的字符串是偶数长度，前半段和后半段是一样的，如蓝红红蓝红红，
25. ACCEPT: If there are exactly twice as many blues as red! 接受：如果蓝色的个数是红色个数的两倍，则接受。
每个循环，除去两个蓝色和一个红色
26. OUTPUT: Reverse the input string! 输出：将输入的字符串逆转输出
27.OUTPUT: Subtract 1 from the binary string!(Input >= 1) 输出：从二进制字符串中减去1(输入字符串>=1)
在末尾添加一个黄色，每个循环，如果黄色左边的是红色，则红色变成蓝色，并且黄色左后退一个字符，
如果黄色左边的蓝色，则将蓝色变成红色，程序结束。
28.ACCEPT: Perfectly symmetrical strings! 接受：完美对称字符串！
意思就是回文串，也就是从左读到右和从右读到左是一样的。
每个循环，头尾消去的字符是一样的。
29.ACCEPT: Two identical strings, separated by a green! 接受：两个相同的字符串，由绿色隔开。
30. ACCEPT: Read the tape as two numbers, A and B, split by a green: accept if A > B! 接受：读入的字符串当做两个二进制数，A和B，由一个绿色隔开，如果A>B则接受。
每次比较A和B的字符，分四种情况
蓝蓝，继续比较A和B剩余的字符
红红，继续比较A和B剩余的字符
蓝红，这种情况下，有个小技巧，将B的字符再消去一个，这时A剩余的字符比B剩余的字符长，则A>B
红蓝,A剩余的字符比B剩余的字符长，则A>B
31. OUTPUT: Read the tape as two numbers, A and B, split by a green: output A + B! 输出：读入的字符串当做两个二进制数，A和B，由一个绿色隔开，输出A+B的和！
将A和B都转成黄色字符，之后再将黄色字符转成二进制。

之前就选修过Angrew Ng的机器学习,但是那是一味的只追求进度，所以收获甚微，于是这次又重新选修了这门课。

这么课程使用Octave语言，这可以说是Matlab的开源版本，使用这种高阶语言，可以让我们更专注于算法层面。今天在实现sigmoid函数时，老是出错。原来是忘记了在每个for循环之后加上end. 还有一点需要说明的是,在Octave中，数组是从1开始的。

1
2
3
4
5
6
7
8

x = [1 2; 3 4]
g = zeros(size(x));
for i = 1:size(x,1)
    for j = 1:size(x,2)
        g(i,j) = 1 / (1 + e ^ (-x(i, j)));
    end 
end
g

习惯在命令行下工作，都忘记用什么软件打开PDF了，才发现是用evince打开。

于是在命令行下执行evince 文件名即可打开，例如要打开ex1.pdf,则执行evince ex1.pdf

挂载U盘
mount -t auto /dev/sdb1 /mnt/usb
如果在mnt目录下不存在usb目录 则先执行 mkdir /mnt/usb,其中/mnt/usb为挂载目录,也可以使用将U盘挂载到其它目录

之后卸载U盘
umount /mnt/usb

如果是文件名中包含中文，还会遇到乱码问题，所以还要加上-o iocharset=utf8

整数划分说的是给定一个正整数N，求一共有多少种方式将N分解成不超过N的正整数和。
例如：N=4时，一共有5种划分，如下：
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 1 + 1 + 1

如果没记错的话，在《C名题精选百则》中出现过这题。我们可以考虑更普遍的情况，将正整数N分解成不超过M的整数和的情况。
对于这种情况，可以将分解分成包含整数M和不包含整数M的情况。令f(N,M)为总共的分解方式，则
f(N,M) = f(N - M, M) + f(N, M -1)，于是写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def partition(n):
    return _partition(n, n)

def _partition(n, m):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m == 1:
        return 1
    else:
        return _partition(n - m, m) + _partition(n, m - 1)
for i in xrange(1, 10):
    print i, partition(i)

只是当n比较大时，递归的效率太慢了，于是用动态规划重写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def partition(n):
    dp = [[0 for i in xrange(n + 1)] for j in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][1] = 1
        dp[0][i] = 1
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            if i - j >= 0:
                dp[i][j] = dp[i - j][j] + dp[i][j - 1]
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[n][n]

for i in xrange(1, 10):
    print i, partition(i)

在欧拉工程中，很多时候都需要用到素数，而得到素数比较好就是用筛法生成。筛法还是很容易理解的，随便找一本教科书的可以找到。

有了这个函数后，要得到100以内的素数就非常容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13

def getPrimes(n):
    primes = [True for i in xrange(n + 1)]
    primes[0] = primes[1] = False
    for x in xrange(2, n + 1):
        if not primes[x]:
            continue
        m = x * x
        while m <= n:
            primes[m] = False
            m += x
    return [i for i in xrange(n + 1) if primes[i]]

print get_primes(100)

2014年8月16日更新：
才发现这个函数的速度还不理想，于是改成

1
2
3
4
5
6
7
8
9

def getPrimes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    i = 2
    while i * i <= n:
        if primes[i]:
            primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1)
        i += 1
    return [i for i in xrange(n + 1) if primes[i]]

之所以这么改，可参看Python筛法求素数的优化

知道这题，是在冼镜光的《C名题精选百则》中。记得这题是自己做出来的，所以稍微回忆一下，就能记起来。也许算法之所以这么难，就是因为不是自己想出来的，所以虽然看过，却很容易忘记。或许应该不只是看算法，而要知道原始作者的思考过程，这样才能真正理解。就像要想理解TCP/IP协议一样，比较好的办法是自己去设计TCP协议，看如何保证可靠传输。扯远了。

对于这题，很容易写出如下程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def max_con_sum(s):
    length = len(s)
    max_sum = s[0]
    i = 0
    temp_sum = s[0]
    while i + 1 < length:
        i += 1
        if temp_sum < 0:
            temp_sum = 0;
        temp_sum += s[i]
        if temp_sum > max_sum:
            max_sum = temp_sum

    return max_sum
L = [2,-3,3,50]
print max_con_sum(L)

而如果还想知道最大连续子序列的开始位置和结束位置，之需要再增加额外的记录信息即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def max_con_sum(s):
    length = len(s)
    max_sum = s[0]
    start = 0;
    end = 0
    i = 0
    temp_sum = s[0]
    while i + 1 < length:
        i += 1
        if temp_sum < 0:
            temp_sum = 0;
            start = i
        temp_sum += s[i]
        if temp_sum > max_sum:
            max_sum = temp_sum
            end = i

    return (max_sum,start,end)
L = [2, -3, 3, 50]
max_sum,start,end =  max_con_sum(L)
print max_sum,start,end

给你一个list L, 如 L=[2,8,3,50], 对L进行选择排序并输出交换次数,
如样例L的结果为1

对于这题，无非就是写一个选择排序，在排序过程中记下交换的次数。很意外的是Pythontip上竟然会有那么多人写错，
按照选择排序的定义，写一个应该是分分钟的事。或许这帮人都没看书。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

L=[2,8,3,50]
length = len(L)
count = 0
for i in xrange(length):
    minum = L[i]
    index = i
    for j in xrange(i + 1, length):
        if L[j] < minum:
            minum = L[j]
            index = j
    if index != i:
        L[i],L[index] = L[index],L[i]
        count += 1
print count

扔蛋问题说的是，100层楼，给两个特制鸡蛋。从某层扔下鸡蛋，鸡蛋就会碎。问至少要测试多少次才能试出这个层数。对于这个问题，许多人都可以背出答案14层。但如果是200层呢?

事实上，还可以对这题进行扩展，假设n层，e个鸡蛋，求至少要测试多少次，才能测出这个层数。

对于这题，可以用动态规划。还是在面4399时，面试官要我解释什么是动态规划，当时没能解释清楚。现在想来，动态规划有两个重要的因素，一个是最优子结构，还有一个是重叠子问题。按我的理解，最优子结构说的是，当前的最优解包含了子问题的最优解。重叠子问题说的是，子问题具有重叠部分。

而对于这题，可以写出一个递推公式,设n为楼层数,e为鸡蛋数。
f(n,e) = 1 + min{max{f(n - r, e),f(r - 1, e -1)}} 其中r属于{2,3,…,n - 1},初始条件为f(n,1) = n, f(1,e) = 1, f(2,e) = 2. 这里要求n,e都是正整数。
写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def egg(n, e=2):
    dp = [[n for i in xrange(e + 1)] for j in xrange(n + 1)]
    for i in xrange(1, n + 1):
        dp[i][1] = i
    for i in xrange(1, e + 1):
        dp[1][i] = 1
        dp[2][i] = 2
    for i in xrange(3, n + 1):
        for j in xrange(2, e + 1):
            for r in xrange(1, n):
                dp[i][j] = min(dp[i][j], 1 + max(dp[i - r][j], dp[r - 1][j - 1]))

    return dp[n][e]

print egg(100, 2)

对于鸡蛋数为2时，还有特殊的解法。在鸡蛋数为2时，楼层数与测试次数如下：
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
…
于是可以猜测,对于楼层数n ,只要找到第一个x ,使得 x * (x + 1) / 2 >= n即可，对于100,正好是14。类似地，对于开头提出的鸡蛋数为2，楼层数为200时，测试层数也可以类似的求解