第1题 组合计数

答案：B（455）

题目

从7 本不同算法书和5 本不同数学书中选4 本，要求：

• 两类书都至少选1 本。

问一共有多少种选法？

第一步：为什么不能直接计算？

1、有的同学第一反应：

一共有

7+5=12 本书

选四本：

但是这样错了！

因为这里把下面两种情况也算进去了：

2、全部都是算法书：

算法 算法 算法 算法

全部都是数学书：

数学 数学 数学 数学

题目要求：

两类书都至少一本。

所以必须去掉这些情况。

方法可以使用，分类讨论法和补集法。

第二步：分类讨论

1、因为一共选4本。

算法书至少一本。

数学书至少一本。

那么算法书可能选：

1 本 2 本 3 本

（不能0本，也不能4本。）

所以只有三种情况。

2、第一种

（1）算法：

1本

数学：

3本

（2）算法方案数：

数学方案数：

方案数小计：

第二种

（1）算法：

2本

数学：

2本

（2）算法方案数：

数学方案数：

方案数小计：

第三种

（1）算法：

3本

数学：

1本

（2）算法方案数：

数学方案数：

方案数小计：

第三步：全部相加

（1）计算：

70+210=280 280+175=455

（2）所以答案：

方法二：补集法（竞赛常用）

1、先不考虑限制。

12本里面选四本：

2、去掉两种非法情况。

（1）全部都是算法书

7本里面选四本：

（2）全部都是数学书

5本里面选四本：

（3）因此：

495-35-5

得到：

455

两种方法比较

🎯 一句话总结

遇到题目中出现：

"两类都至少选一个"

一般有两种经典做法：

方法一——分类讨论：

第一类选1个 第一类选2个 第一类选3个 ……

把所有合法情况分别计算后相加。

方法二——补集法：

总方案 − 第一类一个都没选 − 第二类一个都没选

第2题 排列计数

答案：B（480）

1、题意

若干个人排成一排。

其中

甲乙不能相邻。

问共有多少种。

2、思路

这是经典题。

采用：

总方案 − 相邻方案

3、分步计算

第一步

所有排列

假设共有6个人

那么

6!=720

第二步

（1）甲乙绑在一起

把甲乙

看成一个整体。

又由于

甲乙

内部还能交换：

AB

BA

所以要乘2。

（2）于是，整体数量变成

5个人排列

即

（3）最后

720-240=480

所以答案

B

4、记忆口诀

以后遇到：

• 两人不能相邻

• 若干元素不能相邻

第一反应就是：

总数−相邻数

第3题 二项式展开

答案：C（15）

1、这是经典：

二项式定理

2、展开

(a+b)^n

第k项

3、怎样找常数项？

（1）秘诀：

指数全部加起来等于0。

令

x指数=0

即可求出k。

（2）找到对应组合数即可。

计算后得到

组合数

所以答案

15

第4题 杨辉三角

答案：A

1、看代码：

for (int i = 0; i <= n; i++) { c[i][0] = c[i][i] = 1; for (int j = 1; j < i; j++) c[i][j] = ________; }

2、杨辉三角公式：

组合数满足

C(i,j)=C(i−1,j−1)+C(i−1,j)

因此

c[i][j] = c[i-1][j-1] + c[i-1][j];

答案

A

3、为什么？

（1）因为，当前位置

就是

左上+正上

（2）例如

1 1 1 1 2 1 1 3 3 1

（3）数字3

就是

1+2

4、这是组合数学最重要公式之一。

以后：

DP

组合数

Lucas

都会反复使用。

第5题 快速幂

答案：C（13）

1、看程序

qpow(3,20,17)

2、不需要真的算3²⁰

因为要求的是

3、根据费马小定理

17是质数

（1）所以

（2）因此

=

（3）变成

（4）而

= 13

（5）所以答案

13

4、快速幂

不会直接计算巨大数字。

而是不断：

• 平方

• 取模

时间复杂度：

第6题 归并排序

答案：D（O(nlogn)）

1、归并排序每次：

长度 n ↓ 分成 n/2 ↓ n/4 ↓ ……

2、高度

就是

3、每层合并

需要

4、例如

8个数 第一层 8 第二层 4+4 第三层 2+2+2+2 第四层 1……

（1）每层工作量都是

8

共有

log₂8=3

层。

（2）于是

8×3

一般就是

这是归并排序最经典结论。

第7题 三角形面积

答案：A

1、这是平面几何经典公式。

三个点：

面积公式：

考试时直接代入坐标即可。

2、另一种理解

实际上它来源于：

叉积（Cross Product）

即

很多几何题都会利用叉积来判断：

• 三点是否共线

• 面积

• 左转右转

• 凸包

因此，这道题是在考察解析几何与向量叉积的基础应用。

1~7题知识点：

这7道选择题几乎覆盖了八级前半部分最重要的基础知识：排列组合、二项式定理、组合数递推、快速幂、分治排序、解析几何。