培玉 · 一试

专题地图 › 排列组合与概率

组合计数综合

从这里开始

分类计数之后，检查有没有重漏

说清所数对象，解释分类、重数和上界的取到构造；不能只给一个总数。

带我练直接挑战

看知识图谱

本专题核心公式速查

互动实验：棋盘染色与多米诺覆盖

组合综合题的外形很多，核心常是把对象编码准确，再找能把条件压缩的结构。计数要避免重复与漏计，极值要同时解释界与构造，过程题则要保留足够的状态或不变量。不要先凭题目外观套公式，先把边、状态、指标集或分组的含义说清。

1. 先修与破题直觉：将每个对象写成唯一的状态或图顶点；双计数时先明确数的关联对，避免同一条边被端点各数一次后忘记校正。

2. 核心条件辨析：对称除二之前查固定点；不变量只给可达的必要条件，不能代替路径构造或完整匹配。

3. 典型误区对比：先读下方交换固定点与可达性两组红绿卡，再做自测；把“不可能”的阻碍和“可以”的构造分成两份论证。

4. 方法迁移带练：从 $0$ 出发只许加 $3$ ，模三同余仍是必要条件，但 $- 3$ 仍不可达；若允许加或减 $3$ ，同余才在此模型中变为充分条件。

5. 分级真题实战：先练“关联双计数与度数估计”，再练“代数编码与操作不变量”；挑战“名额匹配与增广”时，候选匹配必须逐一检查冲突与剩余名额。

先修（培玉高中数学）：集合的基本运算分类加法计数原理与分步乘法计数原理排列与组合二项式定理

知识要点

先说清对象、顺序和重复

计数开始前先问：位置是否有标号，交换两个对象算不算新方案，相同数值是否区分。例：从 ${1, 2, 3, 4, 5}$ 取两个不同数，不计顺序有 $(2 5) = 10$ 对，其中相差 $1$ 的有 $4$ 对，所以不相邻的数对有 $6$ 对。若改成有序数对，两个数的身份和顺序都要保留。

关系图保留真正起作用的限制

每个对象作顶点，把需要追踪的两两关系作边。例：三个二元属性给出 $2^{3} = 8$ 个对象，只差一项时连边，每点恰有 $3$ 个邻点，边数为 $8 \cdot 3/2 = 12$ 。禁配选取对应独立集，允许配对对应匹配；两种图的边含义相反，必须先写明。

抽屉原理要先确认碰撞能用

把 $7$ 个对象放入 $3$ 个容器，至少一个容器有 $⌈ 7/3 ⌉ = 3$ 个对象。应用到数对时，容器可以是和值的余数，但两对相撞还不一定给四个不同元素；应先排除共用端点的可能。最优保证值由强制碰撞与不碰撞构造两边共同确定。

双计数必须给每个对象唯一身份

图的每条边有两个端点，所以 $\sum_{v} d (v) = 2∣ E ∣$ 。若统计“一个人同时属于哪两个组”，则总数是 $\sum_{x} (2 r _{x})$ 。例：四顶点路径的度数为 $1, 2, 2, 1$ ，度数和 $6$ 给出 $3$ 条边；中间两个点各贡献一条两边路径，共 $2$ 条。

交换对称先查固定点

交换两个位置通常把非固定对象两两配对。例： $1 \leq a, b \leq 3$ 有 $9$ 个有序数对，其中 $a = b$ 的固定点有 $3$ 个；限制 $a \leq b$ 后共有 $(9 + 3) /2 = 6$ 对。若要求严格不等，则先删固定点，再除以 $2$ 。多种坏事件同时出现时，还要用容斥核交集。

递推状态要足够预测下一步

状态只需保留未来会用到的信息，但不能更少。例：用 $3$ 种有标号颜色给四格长条染色，相邻不同，先格有 $3$ 种、后每格有 $2$ 种，共 $3 \cdot 2^{3} = 24$ 种。若还限制每种颜色的次数，就必须把已用次数纳入状态，不能沿用只记末色的递推。

代数编码先验一步，再谈全程

局部变化可以用加权和或模运算压缩。例：三个位置分别变化 $(1, - 2, 1)$ ，权重为 $(1, 2, 3)$ 时加权和变化 $1 - 4 + 3 = 0$ 。这只证明该量守恒，不能反推同一加权和的两个配置必可互达。质因数指数编码乘法时，也要检查反向恢复及整性。

极值题要同时交付界与构造

证明最大值，需先给所有合法对象共同满足的上界，再造一个达到上界的对象。例：五个排成一行的位置中不取相邻点，按前两对及末点分块，至多选 $3$ 点；取第 $1, 3, 5$ 点达到。若是“无论怎样都能找到”的最小规模，还须给前一规模的反例。

方法卡

关系图与禁配结构

把不能同时选的两个对象连线，合法选择就变成不含连线两端的点集。

完整讲解 · 例题 · 可练 63 题

一、是什么

先认识这些量

图的点代表对象，边代表冲突。不含任何相邻两点的点集叫独立集。只表示冲突，不表示先后顺序。

为什么这样做

每条边恰好对应一条禁配条件，故选点与原选择一一对应。先处理边最多的点，常能把问题拆成很小的分支。

先看一道例题

例 1：一条链

四件物品 $A, B, C, D$ ，禁配为 $A B, BC, C D$ 。选两件有几种？

怎么看出来：

只须排除两端有边的点对。

解：

所有点对为 $A B, A C, A D, BC, B D, C D$ ，删去三条边，剩下 $A C, A D, B D$ 。

答案：

$3$ 种。

二、什么时候想到它

题目里看到	应该想到
条件反复规定哪些两对象能共存、相邻或配对，或者要求同色、异色关系。	把不能同时选的两个对象连线，合法选择就变成不含连线两端的点集。
四件物品 $A, B, C, D$ ，禁配为 $A B, BC, C D$ 。选两件有几种？	只须排除两端有边的点对。

三、怎么用

列出所有对象作为点。
把每条禁配关系画成一条边。
按关键点选或不选分类，删掉不能选的邻点。
检查各类互斥且覆盖全部选择，再相加。

四、再做一道

例 2：三角冲突

$A, B, C$ 两两冲突， $D$ 与它们都不冲突。选两件有几种？

怎么看出来：

三角形内至多选一个点。

解：

合法点对必须含 $D$ ，另一个点可取 $A, B, C$ ，所以是 $A D, B D, C D$ 。

答案：

$3$ 种。

五、容易错在哪

边表示的必须是不能同时选，不能把相容关系误画为边。
独立集不是连通块，不能按连通块数量直接报答案。

真题

按这个方法练 · 63 题

收起并返回方法目录

关联双计数与度数估计

同一批关联分别从两端计数，两种总数必须相等。

完整讲解 · 例题 · 可练 51 题

一、是什么

先认识这些量

关联指一个对象与另一个对象满足指定关系，例如学生参加社团。图中一点连出的边数叫度数，每条边给两个端点各贡献一次。

为什么这样做

学生一端数参加次数，社团一端数人数，数的都是同一批“学生—社团”对。图的度数总和因此等于边数的两倍。

先看一道例题

例 1：轮值次数

$6$ 人每人值日 $2$ 次，每次恰好 $3$ 人。共有几次值日？

怎么看出来：

数“人—值日”关联。

解：

按人数共 $6 \cdot 2 = 12$ 次关联，每次值日贡献 $3$ 次，故值日 $12/3 = 4$ 次。让前三人与后三人各值两次即可实现。

答案：

$4$ 次。

二、什么时候想到它

题目里看到	应该想到
同一对象同时连着行和列、人和组、点和边，或一个局部量可以按多种索引累加。	同一批关联分别从两端计数，两种总数必须相等。
$6$ 人每人值日 $2$ 次，每次恰好 $3$ 人。共有几次值日？	数“人—值日”关联。

三、怎么用

写清所数的关联对是什么。
从第一类对象出发求总数。
从第二类对象出发再数一次。
令总数相等，并核整数性及能否实现。

四、再做一道

例 2：握手数

$5$ 人每人恰与另外 $2$ 人握手，每对至多一次。总共握手几次？

怎么看出来：

每次握手被两个人各数一次。

解：

度数和 $5 \cdot 2 = 10$ ，握手次数 $10/2 = 5$ 。五个人围成一圈各与左右邻居握手便可实现。

答案：

$5$ 次。

五、容易错在哪

两边必须在数同一种关联，不能一边计人而另一边计不带人的场次。
由等式求得整数还不一定可实现，应另核构型。

真题

按这个方法练 · 51 题

收起并返回方法目录

抽屉、平均与总量夹逼

把总量分到若干类；如果每类都低于目标，总量就会不够。

完整讲解 · 例题 · 可练 39 题

一、是什么

先认识这些量

抽屉原理说：把多于 $k q$ 个对象放进 $k$ 类，至少一类有 $q + 1$ 个。平均数是总量除以类数，最大一类不会低于平均数。

为什么这样做

假定每类至多 $q$ 个，则总数至多 $k q$ ；超过它就产生矛盾。要证明“至少需要”多少，还应构造未达到目标的极端分配。

先看一道例题

例 1：同余的三个数

任取整数，至少取多少个才能保证有三个模 $4$ 同余？

怎么看出来：

模 $4$ 有四类。

解：

每类至多两个时共 $8$ 个；取 $9$ 个必有一类至少三个。取 $0, 1, 2, 3, 4, 5, 6, 7$ 时每类恰两个，所以 $8$ 个不够。

答案：

$9$ 个。

二、什么时候想到它

题目里看到	应该想到
出现任意划分、总能找到、至少一个，或总量已经接近每部分可能的极限。	把总量分到若干类；如果每类都低于目标，总量就会不够。
任取整数，至少取多少个才能保证有三个模 $4$ 同余？	模 $4$ 有四类。

三、怎么用

明确对象和分类规则。
假设每类都未达到目标，求最大总量。
比这个总量多取一个，推出目标必达。
构造临界前的分配，检验保证数最小。

四、再做一道

例 2：负载下界

$17$ 本书放进 $5$ 个盒子，最满的盒子至少多少本？该界能取到吗？

怎么看出来：

最大数量至少是平均数向上取整。

解：

若每盒至多 $3$ 本，总量至多 $15$ ，矛盾，故至少 $4$ 本。分成 $4, 4, 3, 3, 3$ ，最满恰为 $4$ 。

答案：

至少 $4$ 本，能取到。

五、容易错在哪

抽屉必须覆盖全部对象，且每个对象只归入所选的一类。
平均数不是每一类的下界，只能保证至少有一类不小于平均数。

真题

按这个方法练 · 39 题

收起并返回方法目录

情况太多时：先定最受限的部分，再分类补全

不要一个个列。先定下最受限制的部分，按它的取值分成互不重叠、没有遗漏的几类，每类单独数清楚，最后相加。

完整讲解 · 例题 · 可练 102 题

一、是什么

分类相加，分步相乘

几类情况互不重叠、合起来是全部，总数就是各类相加。一件事分几步做，只有当后一步的选法个数不受前一步具体选了什么影响时，才能直接相乘。

为什么要分类：选法个数会变

用 $0, 1, 2, 3$ 组成数字不重复的三位数，先选末位 $0$ ，首位有 $3$ 种；先选末位 $2$ ，首位不能是 $0$ ，也不能是 $2$ ，只有 $2$ 种。首位的选法个数随末位变化，不能用一个数相乘，所以按末位分类。

先定哪一部分

优先定选择最少、又影响别的位置的部分：有条件的末位、首位不为 $0$ 、和固定时的最大数、棋盘的第 1 行。定下它以后，其余部分的条件通常变简单。

把这一类的范围说清楚

分类时要说明为什么没有别的情况。例如 $a < b < c$ ， $a + b + c = 15$ ，那么 $15 < 3 c$ ，所以 $c > 5$ 。写出这样的不等式，范围就排尽了，不用靠感觉。

相同的数码怎么排

排列里有相同的数码时，先给相同的数码选位置。 $1, 1, 2$ 排成一行：先选 $2$ 的位置，有 $3$ 种，其余放 $1$ ，共 $3$ 种。

先看一道例题

例 1：有重复数码的四位奇数

用数码 $1, 1, 2, 3$ （全部用上）能组成多少个四位奇数？

怎么看出来：

末位决定奇偶，它最受限，而且末位不同时，剩下的数码不一样，所以按末位分类。

解：

末位只能是 $1$ 或 $3$ ，不能是 $2$ 。末位是 $1$ ：前 $3$ 位排 $1, 2, 3$ ， $3$ 个不同数码有 $3 \times 2 \times 1 = 6$ 种。末位是 $3$ ：前 $3$ 位排 $1, 1, 2$ ，先选 $2$ 的位置，有 $3$ 种。合计 $6 + 3 = 9$ 。

答案：

$9$ 个。

二、什么时候想到它

题目里看到	应该想到
首位不能是 $0$ 、末位有条件	按受限的那一位分类
几个不同的数的和固定	按最大的数分类，用不等式定范围
直接列举太多，但少数几个位置决定其余	先定这几个位置，其余数量由它们决定
棋盘每行每列有个数要求	定第 1 行，按第 2 行和它的交叠分类（见进阶“按交叠分类”）
问有多少种三角形、多少种图形	按最大边或形状分类（见进阶“几何对象”）
$f (f (x))$ 这样的映射条件	按不动点或像分类（见进阶“映射的分类”）

三、怎么用

找最受限的部分。例如用 $0, 1, 2, 3$ 组成没有重复数字的三位偶数。末位只能是 $0$ 或 $2$ ，最受限；首位不能是 $0$ ，和末位有关。先定末位。
分类，并确认不重不漏。末位是偶数，只有 $0$ 、 $2$ 这 $2$ 种，每个数恰好属于其中 $1$ 类。
每类分别数。末位 $0$ ：首位从 $1, 2, 3$ 选，有 $3$ 种，中间从剩下的 $2$ 个选，有 $2$ 种，共 $6$ 个。末位 $2$ ：首位从 $1, 3$ 选，有 $2$ 种，中间从剩下的 $2$ 个选，有 $2$ 种，共 $4$ 个。
相加。 $6 + 4 = 10$ 。
检验。全部列出： $120, 130, 210, 230, 310, 320$ 和 $102, 132, 302, 312$ ，确实是 $10$ 个。

四、再做一道

例 2：和为 15 的三个数

从 $1, 2, \dots, 9$ 里选 $3$ 个不同的数，它们的和是 $15$ 。有多少种选法？

怎么看出来：

$3$ 个数不计顺序，排成 $a < b < c$ 。最大数 $c$ 定了， $a + b$ 也定了。

解：

因为 $a < b < c$ ，所以 $15 = a + b + c < 3 c$ ， $c > 5$ ；又 $c \leq 9$ 。 $c = 9$ ： $a + b = 6$ ，有 $(1, 5), (2, 4)$ ， $2$ 种。 $c = 8$ ： $a + b = 7$ ，有 $(1, 6), (2, 5), (3, 4)$ ， $3$ 种。 $c = 7$ ： $a + b = 8$ ， $b < 7$ ，有 $(2, 6), (3, 5)$ ， $2$ 种。 $c = 6$ ： $a + b = 9$ ， $b < 6$ ，有 $(4, 5)$ ， $1$ 种。合计 $2 + 3 + 2 + 1 = 8$ 。

答案：

$8$ 种。

五、容易错在哪

分类要互不重叠、没有遗漏，写完问一句：每种情况是否恰好属于一类。
先固定一种骨架时，要证明各骨架的补法数相同，且每个对象恰被计一次，才能乘骨架数；如果排序只是为了去重，就不再乘排列数。
列出了各类却没说明为什么只有这些，不算排尽，要用不等式或条件说明范围。
只有后一步的选法个数不受前一步影响才能直接相乘，否则要继续分类。
有重复数码或不计顺序的配对时，要注意同一种情况被数了几次。

进阶：按交叠分类

按交叠分类

两部分有重合时，第 2 部分的数法常常取决于它和第 1 部分重合多少。每种重合的个数算一类。第 1 部分的具体位置有几种，最后再乘。这样做的前提是每种位置下的计数都相同，这要由对称性说明。

例 3：每行 2 个黑格

$3$ 行 $4$ 列的方格表，每行恰涂 $2$ 个黑格，每列至多 $2$ 个黑格。有多少种涂法？

怎么看出来：

第 3 行的选法取决于前 $2$ 行在同一列重合多少，所以定第 1 行，按第 2 行和它重合的格数分类。

解：

第 1 行选 $2$ 列，有 $(2 4) = 6$ 种，这里 $(k n)$ 是从 $n$ 个里选 $k$ 个的选法数。由对称性，每种选法后面的数法相同，不妨设选了第 $1, 2$ 列。第 2 行与它重合 $2$ 格：第 2 行也选第 $1, 2$ 列， $1$ 种，这 $2$ 列已满，第 3 行只能选第 $3, 4$ 列， $1$ 种，共 $1$ 种。重合 $1$ 格：第 2 行有 $2 \times 2 = 4$ 种，例如选第 $1, 3$ 列，第 $1$ 列已满，第 3 行从其余 $3$ 列选 $2$ 列， $3$ 种，共 $12$ 种。重合 $0$ 格：第 2 行选第 $3, 4$ 列， $1$ 种，各列都只有 $1$ 个黑格，第 3 行任选， $6$ 种。合计 $1 + 12 + 6 = 19$ ，总数 $6 \times 19 = 114$ 。

答案：

$114$ 种。

进阶：几何对象

几何对象：按最大边或形状分类

三角形要定形状时，把三边排成 $a \leq b \leq c$ ， $c$ 定了以后条件就是 $a + b > c$ 。按全等算一种时， $a \leq b$ 这个次序已经避免了重复，不要再乘排列数。

例 4：周长固定的三角形

三边都是正整数、周长是 $12$ 的三角形，按全等算一种，有多少种？

怎么看出来：

排成 $a \leq b \leq c$ ，最大边 $c$ 定了就容易了，先用不等式求它的范围。

解：

$a + b + c = 12$ ，三角形要求 $a + b > c$ ，所以 $12 - c > c$ ， $c < 6$ 。 $c$ 是最大边， $12 \leq 3 c$ ， $c \geq 4$ 。 $c = 4$ ： $a + b = 8$ ， $a \leq b \leq 4$ ，只有 $(4, 4)$ 。 $c = 5$ ： $a + b = 7$ ， $a \leq b \leq 5$ ，有 $(2, 5), (3, 4)$ 。合计 $3$ 种。

答案：

$3$ 种： $(4, 4, 4), (2, 5, 5), (3, 4, 5)$ 。

进阶：映射的分类 · 先修：映射

映射：按特殊元素分类

映射 $f : A \to A$ 表示给 $A$ 的每个元素指定一个 $A$ 中的像。 $f (x) = x$ 的 $x$ 叫不动点。条件 $f (f (x)) = x$ 说明：不是不动点的元素必定两两成对， $f$ 把一对元素互换。所以按不动点的个数分类。配对时不要重复计算： ${1, 2} {3, 4}$ 和 ${3, 4} {1, 2}$ 是同一种配法。

例 5：两次映射回到自己

$A = {1, 2, 3, 4, 5}$ ，映射 $f : A \to A$ 满足对每个 $x$ 都有 $f (f (x)) = x$ 。这样的 $f$ 有多少个？

怎么看出来：

不是不动点的元素两两成对，所以不动点的个数决定结构。

解：

若 $f (x) = y \neq = x$ ，则 $f (y) = f (f (x)) = x$ ，所以 $x, y$ 互换成一对。总共 $5$ 个元素，成对的元素个数是偶数，所以不动点有 $5$ 、 $3$ 或 $1$ 个。 $5$ 个不动点： $1$ 种。 $3$ 个不动点：选一对互换， $(2 5) = 10$ 种。 $1$ 个不动点：选不动点有 $5$ 种，其余 $4$ 个元素配成 $2$ 对。固定其中一个元素，选它的搭档有 $3$ 种，剩下 $2$ 个自成一对，所以配法是 $3$ 种，共 $5 \times 3 = 15$ 种。合计 $1 + 10 + 15 = 26$ 。

答案：

$26$ 个。

进阶：先分组再排列

先分组，再排列

有和、整除这样的条件时，先定用哪些数字（分组），再排位置。每组的排列数相同就直接相乘，不同（比如含 $0$ 或重复数码）就分别算。一开始就排位置，容易把同一组数字反复数。

例 6：先定数字，再排

从 $1, 2, 3, 4, 5, 6$ 里选 $4$ 个不同的数字，组成四位数，要求各位数字之和是 $14$ 。有多少个这样的四位数？

怎么看出来：

和的条件只和选了哪些数字有关，先分组，排列放到最后。选 $4$ 个不如看没选的 $2$ 个。

解：

$6$ 个数字之和是 $21$ ，所以没选的 $2$ 个之和是 $21 - 14 = 7$ ，只有 ${1, 6}, {2, 5}, {3, 4}$ ， $3$ 种。每种选法的 $4$ 个数字互不相同，排成四位数有 $4 \times 3 \times 2 \times 1 = 24$ 种。总数 $3 \times 24 = 72$ 。

答案：

$72$ 个。

真题

按这个方法练 · 102 题

收起并返回方法目录

完整状态与逐层转移

只保留能决定下一步合法选择的信息，再按长度逐层更新。

完整讲解 · 例题 · 可练 33 题

一、是什么

先认识这些量

状态是当前局面的必要记录；若两个局面在这个记录相同时，后续可选动作相同，就可以合并计数。状态的计数是到达它的方案数。

为什么这样做

每个合法长串去掉末位都得到唯一短串，所以按最后一步把旧计数送入新状态，不会重复。状态不完整时这个理由就失效。

先看一道例题

例 1：不能连续为一

长度 $4$ 的零一串不允许相邻两个 $1$ ，有多少个？

怎么看出来：

以末位是零或一作状态。

解：

记两类数为 $(a_{n}, b_{n})$ ，则 $(a_{n + 1}, b_{n + 1}) = (a_{n} + b_{n}, a_{n})$ 。从 $(1, 1)$ 得 $(2, 1), (3, 2), (5, 3)$ ，总数 $8$ 。

答案：

$8$ 个。

二、什么时候想到它

题目里看到	应该想到
选择按顺序推进，局部限制只依赖最近若干步、当前端点或已经使用的对象。	只保留能决定下一步合法选择的信息，再按长度逐层更新。
长度 $4$ 的零一串不允许相邻两个 $1$ ，有多少个？	以末位是零或一作状态。

三、怎么用

先问下一步是否合法取决于哪些信息。
列出状态与初始计数。
对每种追加动作，把旧计数加到目标状态。
按要求汇总终态，并用短长度枚举检验。

四、再做一道

例 2：奇偶状态

长度 $4$ 的零一串中， $1$ 的个数为偶数的有多少个？

怎么看出来：

只需记一的个数的奇偶。

解：

加零保奇偶，加一换奇偶。长度一两态各 $1$ 个，随后每态变为两态之和，长度四每态 $8$ 个。

答案：

$8$ 个。

五、容易错在哪

禁止连续模式时，单记已经出现多少个一通常不够，还需记末尾信息。
不同旧状态转移到同一新状态时要相加，不能覆盖原计数。

真题

按这个方法练 · 33 题

收起并返回方法目录

代数编码与操作不变量

先找每次操作都不改变的量，用它排除不可能的目标。

完整讲解 · 例题 · 可练 35 题

一、是什么

先认识这些量

操作前后始终相等的量叫不变量。只保持余数也算不变量，例如整数总和模 $2$ 的余数，即奇偶性。

为什么这样做

一次操作保持该量，则连续任意多次也保持。初态与目标量不同，目标必不可达；量相同只说明这一条障碍不存在。

先看一道例题

例 1：每次翻两个

四个灯全灭，每次翻转两个不同的灯，能否得到恰一盏亮？

怎么看出来：

亮灯数量的奇偶性不变。

解：

若所翻两灯原有 $k$ 盏亮，亮灯总数变化 $2 - 2 k$ ，是偶数。初态为偶数，目标为奇数，所以不可达。

答案：

不能。

二、什么时候想到它

题目里看到	应该想到
条件含奇偶、乘法闭合、线性增量或局部加减操作，直接追踪整个配置困难。	先找每次操作都不改变的量，用它排除不可能的目标。
四个灯全灭，每次翻转两个不同的灯，能否得到恰一盏亮？	亮灯数量的奇偶性不变。

三、怎么用

用数字表示局面和一次操作。
计算总和、奇偶或乘积怎样变化。
证明选定的量每步保持。
比较初末态；若一致，仍须另找实际操作。

四、再做一道

例 2：搬移石子

三堆石子为 $(1, 2, 3)$ ，每次从非空堆搬一颗到另一堆。能否得到 $(2, 2, 3)$ ？能否得到 $(2, 2, 2)$ ？

怎么看出来：

搬移不改变总数。

解：

初始总数 $6$ ，第一目标总数 $7$ ，不可达。第二目标总数 $6$ ，且从第三堆搬一颗到第一堆就得到它。

答案：

第一种不能，第二种能。

五、容易错在哪

不变量相同是必要条件，不能据此直接宣称可达。
模意义下不变与数值完全不变应分清。

真题

按这个方法练 · 35 题

收起并返回方法目录

名额匹配与增广

一边列需求，另一边列名额；安排冲突时沿交替链重新分配。

完整讲解 · 例题 · 可练 10 题

一、是什么

先认识这些量

二分图的两类点分别是人和岗位，边表示此人能做此岗。匹配是一组没有公共端点的边。增广路从未安排的人走到空岗位，中间交替经过未选边和已选边。

为什么这样做

沿增广路把选与未选交换，原来安排的人仍有岗位，并多安排一个人。若一组人的全部可选岗位少于人数，则不可能人人有岗。

先看一道例题

例 1：给后来的让岗

甲可做 $X, Y$ ，乙只能做 $X$ 。如何各安排一个岗位？

怎么看出来：

甲先占了唯一岗时，可以转去另一岗。

解：

若先安排甲做 $X$ ，乙无岗。沿乙— $X$ —甲— $Y$ 交换，得到乙做 $X$ 、甲做 $Y$ 。

答案：

甲做 $Y$ ，乙做 $X$ 。

二、什么时候想到它

题目里看到	应该想到
每项任务要分给有限容量的承担者，或要把对象两两配齐且存在禁配关系。	一边列需求，另一边列名额；安排冲突时沿交替链重新分配。
甲可做 $X, Y$ ，乙只能做 $X$ 。如何各安排一个岗位？	甲先占了唯一岗时，可以转去另一岗。

三、怎么用

列出每人的可选名额。
先试一个不重复占岗的安排。
遇到冲突时，尝试把已有安排沿链挪动。
找到空岗就交换；若出现名额不足的整组，证明无解。

四、再做一道

例 2：局部名额不足

甲乙丙都只能做 $X, Y$ ，丁可做 $Z, W$ 。四人能各有不同岗位吗？

怎么看出来：

总岗位够多不代表每组都够用。

解：

甲乙丙三人的全部可选岗位只有两个，不可能注入两个名额。丁的两个选项不能解决这组三人的缺额。

答案：

不能。

五、容易错在哪

交换时必须沿整条交替链进行，否则可能使原已安排者失去岗位。
只检查总人数不超过总岗位数，不能保证存在匹配。

真题

按这个方法练 · 10 题

收起并返回方法目录

补集容斥与交换对称

先从全集扣除坏情况，再利用真正的一一对应减少重复分类。

完整讲解 · 例题 · 可练 18 题

一、是什么

先认识这些量

补集是全集中不符合条件的对象。容斥是在相加后减去被重复计算的交集。对称计数要有一个保持规则、可逆的交换。

为什么这样做

两个坏条件的并集数为各自数之和减去共同满足两条件的数。角色交换把两类一一配对时，两类数才相等；固定不动的对象须单独处理。

先看一道例题

例 1：都出现

用 $A, B, C$ 写长度 $3$ 的串，三种字母都出现的有多少个？

怎么看出来：

从全部串中扣除至少缺一种的串。

解：

共有 $27$ 串。缺指定字母有 $8$ 串，缺两种有 $1$ 串，故所求为 $27 - 3 \cdot 8 + 3 \cdot 1 = 6$ 。

答案：

$6$ 个。

二、什么时候想到它

题目里看到	应该想到
直接数合法对象很绕，但坏事件简单，或对象可通过交换、反序、零一互换成对对应。	先从全集扣除坏情况，再利用真正的一一对应减少重复分类。
用 $A, B, C$ 写长度 $3$ 的串，三种字母都出现的有多少个？	从全部串中扣除至少缺一种的串。

三、怎么用

确定全集及坏条件。
求各坏类和重叠类的数量。
用容斥扣除重计。
若用交换除以二，先检查是否有固定对象。

四、再做一道

例 2：交换与平局

从 $1, 2, 3, 4$ 中有放回地选有序数对 $(a, b)$ ，满足 $a > b$ 的有多少个？

怎么看出来：

交换两坐标，把大于和小于两类配对，先扣平局。

解：

共 $16$ 对， $a = b$ 有 $4$ 对。其余 $12$ 对两两交换，大于类有 $12/2 = 6$ 对。

答案：

$6$ 对。

五、容易错在哪

使用对称前须核交换后仍满足全部规则。
存在平局或固定对象时，不能把全集直接除以二。

真题

按这个方法练 · 18 题

收起并返回方法目录

误区对照

容易误以为

$1 \leq a, b \leq 3$ 的有序对共九个，限制 $a \leq b$ 后按交换对称除二即可。

应当这样想

对角线 $a = b$ 的三对为交换固定点，不能成二元组；其余六对两两配对。因此所求为 $3 + 6/2 = 6$ 。

为什么

按群作用除重需要检查轨道大小，固定点不是二元轨道。

容易误以为

从整数零出发每次只许加二，目标与零同为偶数，所以所有偶数都能到达。

应当这样想

奇偶不变量只排除了奇数。负偶数如 $- 2$ 虽同余，却不能由非负次加二到达；此操作的可达集是非负偶数。

为什么

操作方向是额外限制，不变量相同不自动给出合法路径。

概念自测

先想清楚，再确认判断。这些自测只帮助辨清概念，不计入真题做对率。

真题 · 300 道

从易到难排列。圆点表示你在这台设备上的做题情况：绿色做对、黄色部分做对、红色没做出。