book
归档: 文化课 
flag
mode_edit

惊奇地发现自己 OI 没有白学

卡特兰数

(2016·全国卷 Ⅲ) 定义「规范 01 数列」${a_n}$ 如下:${a_n}$ 共有 $2m$ 项,其中 $m$ 项为 $0$,$m$ 项为 $1$, 且 $\forall\ k \leq m$, 有 $a_1,\ a_2,\cdots,\ a_k$ 中 $0$ 的个数不少于 $1$ 的个数,若 $m=4$ ,则不同的「规范 01 数列」共有( C )

A. 18 个

B. 16 个

C. 14 个

D. 12 个

老师:「这个题我们也没有好的做法,一个一个枚举就好了」

(你只是不想讲一些奇怪的东西把大家的脑子搞乱吧(x

注意到题中描述的实际上就是配对的括号序列,所以我们可以尝试这样构造合法的括号序列:

一个长度为 $2m$ 的合法序列可以由长度为 $2i$ 和 $2m - 2 - 2i$ 的两个序列拼成,类似…这样:

2m == 6
[][____]
[[]][__]
[[__]][]
[[____]]

所以 dp 方程也就呼之欲出了(其实就是卡特兰数的递推式),

记 $f(m)$ 为长度为 $2m$ 的「规范 01 数列」的数量,那么 $$ f(m)=\sum_{i=0}^nf(i)f(m-i) $$

值得一提的是在请教纸夜姐之前我推出了大约 3~5 个假公式

DAG 路径计数

(2016·全国卷Ⅱ)如图,小明从街道的 $E$ 处出发,先到 $F$ 处与小红会合,再一起到位于 $G$ 处的老年公寓参加志愿者活动,则小明到老年公寓可以选择的最短路径条数为( B )

 +---------------------------------------G
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 +-------------------F-------------------+
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 +---------------------------------------+
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 |         |         |         |         |
 E---------------------------------------+

A. 24

B. 18

C. 12

D. 9

我们只需要 xjb 统计一下就行了

+-------------------1---------2---------3
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
1---------3--------6,1--------1---------1
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
1---------2---------3-------------------+
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
|         |         |         |         |
1---------1---------1-------------------+

所以答案就是 $6\times3 = 18$

传球游戏

(2018·河北保定质检)三个人踢毽,互相传递,每人每次只能踢一下,由甲开始踢,经过 $4$ 次传递,毽又被踢回给甲,则不同的传递方式有:( B )

A. 4 B. 6 C. 10 D. 16

记 $f(n),\ g(n),\ k(n)$ 分别为「经过 $n$ 次传递后,毽子在 甲/乙/丙 的手里」,考虑 $n = 4$ 的情况,由题意,此时毽子在甲的手里。那么,在上一次传递时,毽子一定在乙或丙的手里。换句话说,毽子由乙或丙传递给甲。

那么我们就有: $$ f(n)=g(n-1)+k(n-1) $$ $$ g(n)=f(n-1)+k(n-1) $$ $$ k(n)=f(n-1)+g(n-1) $$

往里面代值计算:

Function\Value of $n$01234
$f(n)$10226
$g(n)$01135
$k(n)$01135

所以答案就是 $f(4) = 6$ 了