离散与组合数学

集合；加法原理；乘法原理；排列；组合；杨辉三角。

概念

组合数学数「有多少种可能」。加法原理：互斥的几类方案数相加；乘法原理：分步且独立时各步方案数相乘。排列 $A_n^m$ 讲究顺序；组合 $C_n^m=\binom{n}{m}$ 不讲究顺序，常写 $C_n^m=\frac{n!}{m!(n-m)!}$ 或用杨辉三角第 $n$ 行第 $m$ 项。集合题考元素互异、子集个数 $2^n$ 等。与 cspj.math.number-theory 不同：组合问「选法个数」，数论问「能否整除」；与 cspj.algo.dp-basic 相邻——网格路径数既可用组合公式 $C_{m+n-2}^{m-1}$ ，也可 DP 递推，初赛单选往往直接考公式。

CSP-J 常考

cspj-r1-2019 第 7 题： $8$ 个相同球放入 $5$ 个相同空盒（可空），求分法数——相同物体分组，提示「全放一个袋只算一种」。
cspj-r1-2025 第 6 题： $5$ 男 $4$ 女选 $4$ 人且男女都有，用组合减缺一类的情况。
cspj-r1-2025 第 11 题：网格只能向右或向下，从 $(1,1)$ 到 $(4,5)$ 的路径数（乘法原理 / 组合数）。
cspj-r1-2024 第 3、14 题：杨辉三角或组合恒等式相关单选。
cspj-r2-2024 第 1 题（扑克牌）： $52$ 种花色点数各一张为完整牌组，求至少再借几张凑齐——用集合统计已出现种类，答案 $52-\text{种类数}$ 。

// 杨辉三角：C(n,m) = C(n-1,m-1) + C(n-1,m)
long long C[30][30];
void buildPascal() {
    for (int i = 0; i < 30; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
}

易错点

「相同球相同盒」与「不同人选不同队」模型不同，不要一律用 $C_n^m$ 。
网格路径：从 $(1,1)$ 到 $(x,y)$ 需走 $(x-1)+(y-1)$ 步，选向下步数即 $C_{x+y-2}^{x-1}$ ，坐标别当成步数。
杨辉三角下标从 $0$ 还是 $1$ 开始要与题面一致；阅读程序里二维数组行号易 off-by-one。
组合计数结果可能很大，复赛若超 int 要用 long long，但初赛单选通常给较小数值。

把 $8$ 个同样的球放在 $5$ 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）

提示：如果 $8$ 个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法。

—副纸牌除掉大小王有 $52$ 张牌，四种花色，每种花色 $13$ 张。

假设从这 $52$ 张牌中随机抽取 $13$ 张纸牌，则至少（）张牌的花色一致。

—些数字可以颠倒过来看，例如 $0,1,8$ 颠倒过来还是本身， $6$ 颠倒过来是 $9$ ， $9$ 颠倒过来看还是 $6$ ，其他数字颠倒过来都不构成数字。
类似的，一些多位数也可以颠倒过来看，比如 $106$ 颠倒过来是 $901$ 。假设某个城市的车牌只由 $5$ 位数字组成，每一位都可以取 $0$ 到 $9$ 。
请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

125

100

$5$ 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法?

$10$ 个三好学生名额分配到 $7$ 个班级，每个班级至少有一个名额，一共有（）种不同的分配方案。

504

有五副不同颜色的手套（共 $10$ 只手套，每副手套左右手各 $1$ 只），一次性从中取 $6$ 只手套，请问恰好能配成两副手套的不同取法有（）种。

120

180

150

$6$ 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（）种。

由 $1,1,2,2,3$ 这五个数字组成不同的三位数有（）种。

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 $\tt abcab$ 有（）个内容互不相同的子串。

$12$

$13$

$14$

$15$

小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有（）种选择时间段的方案。

一个班级有 $10$ 个男生和 $12$ 个女生。如果要选出一个 $3$ 人的小组，并且小组中必须至少包含 $1$ 个女生，那么有多少种可能的组合?()

$1420$

$1770$

$1540$

$2200$

某公司有 $10$ 名员工，分为 $3$ 个部门：A 部门有 $4$ 名员工，B 部门有 $3$ 名员工，C 部门有 $3$ 名员工。现需要从这 $10$ 名员工中选出 $4$ 名组成一个工作小组，且每个部门至少要有 $1$ 人。问有多少种选择方式？（）

120

126

132

238

有 $5$ 个男生和 $3$ 个女生站成一排，规定 $3$ 个女生必须相邻。问有多少种不同的排列方式？（）

$4320$ 种

$5040$ 种

$3600$ 种

$2880$ 种

编程题

扑克牌

C++时间 1 s内存 512 MB 文件 IO：poker.in → poker.out

小 P 从同学小 Q 那儿借来一副 $n$ 张牌的扑克牌。

本题中我们不考虑大小王，此时每张牌具有两个属性：花色和点数。花色共有 $4$ 种：方片、草花、红桃和黑桃。点数共有 $13$ 种，从小到大分别为 $\tt{A 2 3 4 5 6 7 8 9 T J Q K}$ 。注意：点数 $10$ 在本题中记为 $\tt T$ 。

我们称一副扑克牌是完整的，当且仅当对于每一种花色和每一种点数，都恰好有一张牌具有对应的花色和点数。由此，一副完整的扑克牌恰好有 $4 \times 13 = 52$ 张牌。以下图片展示了一副完整的扑克牌里所有的 52 张牌。

一副完整的扑克牌

小 P 借来的牌可能不是完整的，为此小 P 准备再向同学小 S 借若干张牌。可以认为小 S 每种牌都有无限张，因此小 P 可以任意选择借来的牌。小 P 想知道他至少得向小 S 借多少张牌，才能让从小 S 和小 Q 借来的牌中，可以选出 $52$ 张牌构成一副完整的扑克牌。

为了方便你的输入，我们使用字符 $\tt D$ 代表方片，字符 $\tt C$ 代表草花，字符 $\tt H$ 代表红桃，字符 $\tt S$ 代表黑桃，这样每张牌可以通过一个长度为 $2$ 的字符串表示，其中第一个字符表示这张牌的花色，第二个字符表示这张牌的点数，例如 $\tt{CA}$ 表示草花 $\tt A$ ， $\tt{ST}$ 表示黑桃 $\tt T$ （黑桃 10）。

输入格式

从文件 poker.in 中读入数据。

输入的第一行包含一个整数 $n$ 表示牌数。

接下来 $n$ 行：

每行包含一个长度为 $2$ 的字符串描述一张牌，其中第一个字符描述其花色，第二个字符描述其点数。

输出格式

输出到文件 poker.out 中。

输出一行一个整数，表示最少还需要向小 S 借几张牌才能凑成一副完整的扑克牌。

样例

输入 1

1
SA

输出 1

这一副牌中包含一张黑桃 $\tt A$ ，小 P 还需要借除了黑桃 $\tt A$ 以外的 51 张牌以构成一副完整的扑克牌。

输入 2

4
DQ
H3
DQ
DT

输出 2

这一副牌中包含两张方片 $\tt Q$ 、一张方片 $\tt T$ （方片 10）以及一张红桃 3，小 P 还需要借除了红桃 3、方片 $\tt T$ 和方片 $\tt Q$ 以外的 49 张牌。

数据范围

对于所有测试数据，保证： $1 \le n \le 52$ ，输入的 $n$ 个字符串每个都代表一张合法的扑克牌，即字符串长度为 $2$ ，且第一个字符为 $\tt{D C H S}$ 中的某个字符，第二个字符为 $\tt{A 2 3 4 5 6 7 8 9 T J Q K}$ 中的某个字符。

测试点编号	$n \le$	特殊性质
$1$	$1$	A
$2 \sim 4$	$52$	A
$5 \sim 7$	$52$	B
$8 \sim 10$	$52$	无

特殊性质 A：保证输入的 $n$ 张牌两两不同。

特殊性质 B：保证所有牌按照点数从小到大依次输入，点数相同时按照方片、草花、红桃、黑桃的顺序依次输入。

部分分

10 分
测试点 $1$ ： $n \le 1$ ，特殊性质 A。
30 分
测试点 $2 \sim 4$ ： $n \le 52$ ，特殊性质 A。
30 分
测试点 $5 \sim 7$ ： $n \le 52$ ，特殊性质 B。
30 分
测试点 $8 \sim 10$ ： $n \le 52$ ，无特殊性质。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

从 $5$ 位男生和 $4$ 位女生中选出 $4$ 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选法？

$126$

$121$

$120$

$100$

一个 $8 \times 8$ 的棋盘，左上角坐标为 $(1,1)$ ，右下角为 $(8,8)$ 。一个机器人从 $(1,1)$ 出发，每次只能向右或向下走一格。要到达 $(4,5)$ ，有多少种不同的路径？

$20$

$35$

$56$

$70$