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

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

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

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

Leonardo Fibonacci 1175-1250 2018/11/29

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

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

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

January 2018/11/29

February 2018/11/29

March 2018/11/29

April 2018/11/29

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

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

Some other pictures 2018/11/29

2018/11/29

2018/11/29

2018/11/29

2018/11/29

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

Fibonacci Numbers in Nature 2018/11/29

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

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

trillium （ 延龄草） 2018/11/29

Columbine(耧斗菜) 2018/11/29

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

black-eyed susan 2018/11/29

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

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

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

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

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

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

sunflowers （向日葵） 2018/11/29

2018/11/29

2018/11/29

2018/11/29

Fibonacci in geometrical style 2018/11/29

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

Edouard Lucas                                         1842-1891 2018/11/29

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

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

Catalan number 2018/11/29

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

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

Easy or not ? 2018/11/29

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

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

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

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

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

7 sides, 42 ways: 2018/11/29

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

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

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

4 nodes: 5 nodes: 2018/11/29

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

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

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

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

(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

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

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

考虑（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

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

计算示意图： 2018/11/29

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

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

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

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

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

课后作业： 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

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

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

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

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

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

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

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

/*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

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

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

图示（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

匈牙利算法是基于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

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

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

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

实 例 分 析 2018/11/29

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

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

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

特别说明: 此题需要注意的一点，具体参见： http://acm.hdu.edu.cn/forum/read.php?tid=61&keyword=%B6%FE%B7%D6 2018/11/29

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

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

Sample input: 4 3 3 4 1 3 2 3 Output: 2 2018/11/29

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

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

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

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

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

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

Any Questions? 2018/11/29

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

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

ACM, 天天见！ 2018/11/29