GESP八级c++复习资料（一定要保存、收藏！！！）

GESP8级主要考察点分为五个部分：倍增、最短路、最小生成树、数论和组合数学。

数论与组合数学

计数原理

加法计数原理

完成一件事，有

n

n

n 类办法，每类办法 互相独立。

• 第一类有 $m_1$
• 第二类有 $m_2$
• 第三类有 $m_3$
• ……
• 第 $n$

即总方法数是

m

1

+

m

2

+

m

3

+

⋯

+

m

n

m_1 + m_2 + m_3 + \\cdots + m_n

m1​+m2​+m3​+⋯+mn​。 关键词：分类、任选其一、互不干扰。

乘法计数原理

完成一件事，需要分成

n

n

n 个步骤，步骤之间 有先后顺序。

• 第一步有 $m_1$
• 第二步有 $m_2$
• 第三步有 $m_3$
• ……
• 第 $n$

即总方法数是

m

1

×

m

2

×

m

3

×

⋯

×

m

n

m_1 \\times m_2 \\times m_3 \\times \\cdots \\times m_n

m1​×m2​×m3​×⋯×mn​。 关键词：分步、缺一不可、先后顺序。

区分方法

能 一步 做完 → 分类 → 加法 → “或”。 必须 多步 做完 → 分步 → 乘法 → “且”、“先……再……” 。

阶乘

n

!

=

∏

i

=

1

n

i

=

n

×

(

n

−

1

)

×

(

n

−

2

)

×

⋯

×

2

×

1

n! = \\prod_{i=1}^{n}i = n \\times (n-1) \\times (n-2) \\times \\cdots \\times 2 \\times 1

n!=∏i=1n​i=n×(n−1)×(n−2)×⋯×2×1，注意

0

!

=

1

0! = 1

0!=1。

排列

从

n

n

n 个不同元素中，有序 取出

m

m

m 个排成一列，叫排列，通常记作

A

n

m

A_n^m

Anm​ 或

P

n

m

P_n^m

Pnm​。

A

n

m

=

n

!

(

n

−

m

)

!

=

∏

i

=

n

−

m

+

1

n

i

A_n^m = \\frac{n!}{(n-m)!} = \\prod_{i=n-m+1}^{n}i

Anm​=(n−m)!n!​=∏i=n−m+1n​i。

全排列：

A

n

n

=

n

!

A_n^n = n!

Ann​=n!

组合

从

n

n

n 个不同元素中，无序 取出

m

m

m 个组成一组，叫组合，通常记作

C

n

m

C_n^m

Cnm​ 或

(

n

m

)

\\binom{n}{m}

(mn​)。

C

n

m

=

A

n

m

m

!

=

n

!

m

!

(

n

−

m

)

!

C_n^m = \\frac{A_n^m}{m!} = \\frac{n!}{m!(n-m)!}

Cnm​=m!Anm​​=m!(n−m)!n!​。 性质：

• $C_n^m=C_n^{n-m}$
• $C_n^0=C_n^n=1$
• $C_n^m+C_n^{m+1}=C_{n+1}^{m+1}$
• ${\sum }_{i=0}^n{C}_n^i=2^n$

鸽巢原理（抽屉原理）

基本形式

把

n

+

1

n+1

n+1 个物体放入

n

n

n 个抽屉中，则 至少有一个抽屉 里包含 至少两个 物体。

推广形式

把

k

m

+

1

km+1

km+1 个物体放入

k

k

k 个抽屉中，则至少有一个抽屉里包含至少

m

+

1

m+1

m+1 个物体。

典型应用

• 任意 $13$
• 任意 $5$

卡特兰数

定义

第

n

n

n 个卡特兰数记作

C

a

t

a

l

a

n

(

n

)

Catalan(n)

Catalan(n)，公式为：

C

a

t

a

l

a

n

(

n

)

=

1

n

+

1

C

2

n

n

=

(

2

n

)

!

(

n

+

1

)

!

n

!

Catalan(n) = \\frac{1}{n+1}C_{2n}^n = \\frac{(2n)!}{(n+1)!n!}

Catalan(n)=n+11​C2nn​=(n+1)!n!(2n)!​。

初始值

C

a

t

a

l

a

n

(

0

)

=

1

Catalan(0) = 1

Catalan(0)=1，

C

a

t

a

l

a

n

(

1

)

=

1

Catalan(1) = 1

Catalan(1)=1，

C

a

t

a

l

a

n

(

2

)

=

2

Catalan(2) = 2

Catalan(2)=2，

C

a

t

a

l

a

n

(

3

)

=

5

Catalan(3) = 5

Catalan(3)=5，

C

a

t

a

l

a

n

(

4

)

=

14

Catalan(4) = 14

Catalan(4)=14。

典型应用场景

• 合法括号匹配的数量：$n$
• 出栈序列的数量：$n$
• 凸多边形三角剖分：$n$

整除

点击查看，博主原创