今天， AC 你 了吗？ 2018/11/29.

Presentation on theme: "今天， AC 你 了吗？ 2018/11/29."— Presentation transcript:

1 今天， AC 你 了吗？ 2018/11/29

2 第九讲(1) 特殊的数 （Special Number） 2018/11/29

3 主要内容 Fibonacci Number Lucas number Catalan Number
Application to Special Number 2018/11/29

4 Fibonacci Number Fibonacci is perhaps best known for a simple series of numbers, introduced in Liber abaci and later named the Fibonacci numbers in his honour. The series begins with 0 and 1. After that, use the simple rule: Add the last two numbers to get the next. 0，1，1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,... 2018/11/29

5 Leonardo Fibonacci 2018/11/29

6 You might ask where this came from?
2018/11/29

7 In Fibonacci's day, mathematical competitions and challenges were common. In 1225 Fibonacci took part in a tournament at Pisa ordered by the emperor himself, Frederick II. It was in just this type of competition that the following problem arose: 2018/11/29

8 Beginning with a single pair of rabbits, if every month each productive pair bears a new pair, which becomes productive when they are 1 month old, how many rabbits will there be after n months? 2018/11/29

9 January 2018/11/29

10 February 2018/11/29

11 March 2018/11/29

12 April 2018/11/29

13 May、June… ??? 2018/11/29

14 The number series is—— 1、1、2、3、5… This if fibonacci！ 2018/11/29

15 Some other pictures 2018/11/29

16 2018/11/29

17 2018/11/29

18 2018/11/29

19 2018/11/29

20 Fibonacci number & Golden Section
A special value, closely related to the Fibonacci series, is called the golden section. This value is obtained by taking the ratio of successive terms in the Fibonacci series: 2018/11/29

21 Fibonacci Numbers in Nature
2018/11/29

22 white calla lily（白色马蹄莲）
2018/11/29

23 Euphorbia(一种非洲植物，不常见)
2018/11/29

24 trillium （ 延龄草） 2018/11/29

25 Columbine(耧斗菜) 2018/11/29

26 Bloodroot（一种罂粟科植物） 2018/11/29

27 black-eyed susan 2018/11/29

28 shasta daisy(大滨菊) with 21 petals
2018/11/29

29 Ordinary field daisies(雏菊) have 34 petals
2018/11/29

30 The association of Fibonacci numbers and plants is not restricted to numbers of petals.
2018/11/29

31 If we draw horizontal lines through the axils, we can detect obvious stages of development in the plant. 2018/11/29

32 The number of branches at any stage of development is a Fibonacci number.
2018/11/29

33 Furthermore, the number of leaves in any stage will also be a Fibonacci number.
2018/11/29

34 sunflowers （向日葵） 2018/11/29

35 2018/11/29

36 2018/11/29

37 2018/11/29

38 Fibonacci in geometrical style
2018/11/29

39 Lucas Number Lucas Numbers are the companions to the Fibonacci numbers and satisfy the same recurrence : L(n)=L(n-1)+L(n-2) Where L(1)=1,L(2)=3 The first few are 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... 2018/11/29

40 Edouard Lucas                                         2018/11/29

41 编程实现这类递归问题时应该注意什么问题？
Question: 编程实现这类递归问题时应该注意什么问题？ 2018/11/29

42 空间换 时 间！！ 2018/11/29

43 Catalan number 2018/11/29

44 先看一道题目： HDOJ_1134: Game of Connections 2018/11/29

45 示意图： 6 3 4 2 5 1 7 8 2018/11/29

46 Easy or not ? 2018/11/29

47 Catalan Number The Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, , , , , ...), named after Eugène Charles Catalan, arise in a number of problems in combinatorics. They can be computed using this formula: 2018/11/29

48 Eugène Charles Catalan
(1814—1894 Belgium) 2018/11/29

49 What can the Catalan numbers describe ?
2018/11/29

50 1. The number of ways a polygon with n+2 sides can be cut into n triangles
4 sides, 2 ways: 2018/11/29

51 5 sides, 5 ways: 6 sides, 14 ways: 2018/11/29

52 7 sides, 42 ways: 2018/11/29

53 2. the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time 3 numbers: (1 (2 3)) ((1 2) 3) 4 numbers: (1 (2 (3 4))) (1 ((2 3) 4)) ((1 2) (3 4)) ((1 (2 3)) 4) (((1 2) 3) 4) 2018/11/29

54 5 numbers: (1 ((2 3) (4 5))) (1 ((2 (3 4)) 5))
(1 (2 (3 (4 5)))) (1 (2 ((3 4) 5))) (1 ((2 3) (4 5))) (1 ((2 (3 4)) 5)) (1 (((2 3) 4) 5)) ((1 2) (3 (4 5))) ((1 2) ((3 4) 5)) ((1 (2 3)) (4 5)) ((1 (2 (3 4))) 5) ((1 ((2 3) 4)) 5) (((1 2) 3) (4 5)) (((1 2) (3 4)) 5) (((1 (2 3)) 4) 5) ((((1 2) 3) 4) 5) 2018/11/29

55 3.the number of rooted, trivalent trees with n+1 nodes
2018/11/29

56 4 nodes: 5 nodes: 2018/11/29

57 4. the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal
2 x 2 grid: 2018/11/29

58 3 x 3 grid: 4 x 4 grid: 2018/11/29

59 5. The number of binary trees with n nodes.
There are 5 binary trees with 3 nodes. 2018/11/29

60 6. Some other applications
（1）The number of ways 2n people, seated round a table, can shake hands in n pairs, without their arms crossing. （2）The self-convolving sequence, c[0]=1, c[n+1] = c[0]c[n] + c[1]c[n-1] c[n]c[0] 2018/11/29

61 (3) The recurring sequence c[0]=1, (n+2)c[n+1] = (4n+2)c[n], (n>=0).
(4)Another disguise is the number of ways n votes can come in for each of two candidates A and B in an election, with A never behind B. 2018/11/29

62 思考(1)： http://acm.hziee.edu.cn/showproblem.php?pid=1133
思考(1)： 2018/11/29

63 算法分析： 令f(m,n)表示有m个人手持￥50的钞票，n个人手持￥100的钞票时共有的方案总数。则可以分以下情况讨论这个问题：
2018/11/29

64 考虑（m+n）个人排队购票的情景，第（m+n）人站在第（m+n-1）个人的后面，则第（m+n ）个人的排队方式可以由下列两种情况获得：
(3)其他情况： 考虑（m+n）个人排队购票的情景，第（m+n）人站在第（m+n-1）个人的后面，则第（m+n ）个人的排队方式可以由下列两种情况获得： 1）第（m+n ）个人手持￥100的钞票，则在他之前的(m+n-1）个人中有m个人手持￥50的钞票，有（n-1）个人手持￥100的钞票，此种情况共有f(m,n-1); 2)第（m+n ）个人手持￥50的钞票，则在他之前的(m+n-1）个人中有m-1个人手持￥50的钞票，有n个人手持￥100的钞票，此种情况共有f(m-1,n); 2018/11/29

65 根据加法原理得到f(m,n)=f(m-1,n)+f(m,n-1) 于是得到f(m,n)的计算公式
2018/11/29

66 计算示意图： 2018/11/29

67 计算示意图： 1 2018/11/29

68 计算示意图： 1 2 3 5 4 9 14 2018/11/29

69 可以推出直接的公式： C(m+n,n)-C(m+n,m+1) 2018/11/29

70 思考(2)： 1130 How Many Trees? 2018/11/29

71 思考（3）： 1131 Count the Trees 2018/11/29

72 课后作业： 1130 How Many Trees? 1131 Count the Trees 1133 Buy the Ticket
1134 Game of Connections 1023 Train Problem II 2018 母牛的故事 2041超级楼梯 2067小兔的棋盘 2018/11/29

73 （Bipartite Graph & Applications）
第九讲(2) 二分图及其应用 （Bipartite Graph & Applications） 2018/11/29

74 主要内容 什么是二分图 二分图的最大匹配 匈牙利算法 二分图的最小顶点覆盖 DAG图的最小路径覆盖 二分图的最大独立集 处理技巧
2018/11/29

75 什么是二分图？ 如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称该图为“二分图”（ Bipartite Graph ） 2018/11/29

76 例：婚配问题 男 女 2018/11/29

77 二分图的最大匹配 在二分图的应用中，最常见的就是最大匹配问题，很多其他的问题都可以通过转化为匹配问题来解决。 2018/11/29

78 如何求二分图的最大匹配呢？ 2018/11/29

79 经典算法： 匈牙利算法 2018/11/29

80 /*hdoj_1150匈牙利算法 月下版 */ #include<iostream> #include<string> #include<vector> using namespace std; bool mark1[100],mark2[100]; int list[100]; int n,m,edge,num; vector<vector<int> > v; bool dfs(int to) { register int i,point,s = list[to]; for(i=0;i<v[s].size();i++) { point = v[s][i]; if(!mark2[point]) continue; mark2[point] = false; if(list[point]==-1 || dfs(point)){ list[point] = s; return true; } } return false; } void Solve() { int i,j,point; bool flog = false; memset(mark1,true,sizeof(mark1)); memset(list,-1,sizeof(list)); num=0; for(i=0;i<n;i++) { for(j=0;j<v[i].size();j++) if(list[v[i][j]] == -1) { mark1[i] = false; list[v[i][j]] = i; num++; if(i==0) flog = true; break; } } for(i=0;i<n;i++) { if(mark1[i]) { if(!v[i].empty()){ memset(mark2,true,sizeof(mark2)); for(j=0;j<v[i].size();j++) { point = v[i][j]; if(!mark2[point]) continue; mark2[point] = false; if(list[point] == -1 || dfs(point)) { list[point] = i; num++; break; } } } mark1[i] = false; } } if(flog || list[0] != -1) cout << num-1 << endl; else cout << num << endl; } int main() { int i,j,s,d; while(cin>>n) { if(n == 0)break; v.clear(); v.resize(n); cin >> m >> edge; for(i=0;i<edge;i++) { cin >> j >> s >> d; v[s].push_back(d); } Solve(); } return 0; } 2018/11/29

81 匈牙利算法(求二分图最大匹配) 谈匈牙利算法自然避不开Hall定理
Hall定理：对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： |T(A)| >= |A| 2018/11/29

82 图示（1）： 女1 男1 女2 男2 女3 返回 2018/11/29

83 图示（2）： X0=男2 V1={男2} V2 = Φ T(V1)={女1} Y=女1 V1={男2，男1} 女1 V2 ={女1}
M←M⊕E(P) ( 其中，P是从x0 →y的可增广道路 ) 男1 男2 女1 女2 女3 返回 2018/11/29

84 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：
1．任给初始匹配M； 2．若X已饱和则结束，否则进行第3步； 3．在X中找到一个非饱和顶点x0， 作V1 ← {x0}, V2 ← Φ； 4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2； 5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2； 6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4； 2018/11/29

85 图示（3）： T(V1)=V2 X0=男2 V1={男2} V2 = Φ T(V1)={女1} T(V1) != V2 Y=女1
男1 男2 女1 女2 返回 2018/11/29

86 NOTE: 真正求二分图的最大匹配的题目很少，往往做一些简单的变化，比如—— 2018/11/29

87 变种1： 二分图的最小顶点覆盖 在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是 “二分图的最小顶点覆盖”。
变种1： 二分图的最小顶点覆盖 在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是 “二分图的最小顶点覆盖”。 2018/11/29

88 实 例 分 析 2018/11/29

89 例：严禁早恋，违者开除！ 男生 女生 2018/11/29

90 例：任务安排 有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai,如果它在机器B上运行，则机器A需要设置为模式bi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。 ——hdoj_1150（LRJ_p331） ——ACM/ICPC Beijing 2002 2018/11/29

91 图示： 结论： 二分图的最小顶点覆盖数 = 二分图的最大匹配数 a0 a1 a2 a3 a4 b0 b1 b2 b3 b4
2018/11/29

92 特别说明: 此题需要注意的一点，具体参见：
2018/11/29

93 变种2： DAG图的最小路径覆盖 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
2018/11/29

94 例：空袭（Air Raid） 有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。
你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。 ——hdoj_1151 2018/11/29

95 Sample input: Output: 2 2018/11/29

96 “空袭”示意图 1 2 3 4 4’ 3’ 2’ 1’ 1 3 2 4 2018/11/29

97 结论： DAG图的最小路径覆盖数= 节点数（n）- 最大匹配数（m） 关键：求二分图的最大匹配数 2018/11/29

98 变种3: 二分图的最大独立集 ——hdoj_1068 Girls and Boys
变种3: 二分图的最大独立集 Girls and Boys 大学二年级的时候，一些同学开始研究男女同学之间的缘分。研究者试图找出没有缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量。 ——hdoj_1068 2018/11/29

99 输入数据格式： 7 0: (3) : (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 输出：5 2018/11/29

100 “Girls and Boys”示意图 0’ 1 5 4 3 2 6’ 5’ 4’ 3’ 2’ 1’ 6 2018/11/29

101 结论： 二分图的最大独立集数= 节点数（n）— 最大匹配数（m） 关键：求二分图的最大匹配数 2018/11/29

102 Any Questions? 2018/11/29

103 附：二分匹配练习题： 1068 (二分图最大独立集= n - m ) 1150 (二分图最小顶点覆盖= m )
2018/11/29

104 课后一定要练习！ 2018/11/29

105 ACM, 天天见！ 2018/11/29