图论核心知识点与解题技巧（初一级别 / CSP 备考适用） 一、图论基础概念（必背） 1. 图的定义：图（Graph）由顶点（Vertex，也叫节点）集合VVV和边（Edge）集合 EEE 组成，记为 G=(V,E)G=(V, E)G=(V,E)。顶点用于表示对象，边表示对象之间的关系 。 2. 有向图与无向图： * 有向图：边具有方向性，例如 <u,v><u, v><u,v> 表示从顶点 uuu 指向顶点 vvv 的边，信息或关系是单向传递的，类似网页链接，网页 AAA 链接到网页 BBB，不代表 BBB 也链接到 AAA。 * 无向图：边没有方向，(u,v)(u, v)(u,v) 表示 uuu 和 vvv 之间有连接，关系是双向的，比如社交网络中的好友关系，若 AAA 是 BBB 的好友，那么 BBB 也是 AAA 的好友 。 1. 顶点的度数： * 无向图：顶点的度数是与该顶点相连的边的数量。例如在一个简单无向图中，若顶点 AAA 连接了 333 条边，那么顶点 AAA 的度数为 333。 * 有向图：分为入度和出度。入度是指向该顶点的边的数量，出度是从该顶点出发的边的数量。比如在一个表示任务依赖关系的有向图中，任务 BBB 有 222 个前置任务指向它，同时它指向 111 个后续任务，那么任务 BBB 的入度为 222，出度为 111。 1. 路径与环： * 路径：是一个顶点序列 v1,v2,⋯ ,vkv_1, v_2, \cdots, v_kv1 ,v2 ,⋯,vk ，其中任意相邻的顶点 viv_ivi 和 $ v_{i + 1}$ 之间都有一条边相连。例如在图中从顶点 111 经过边到顶点 222，再到顶点 333，则 1−2−31 - 2 - 31−2−3 构成一条路径。 * 环：在无向图中，是至少包含一条边且起始和结束顶点相同的路径；在有向图中，是从某个顶点出发，沿着有向边经过一系列顶点后又回到该顶点的路径。例如在一个无向图中，顶点 A−B−C−AA - B - C - AA−B−C−A 构成一个环；在有向图中 A→B→C→AA \to B \to C \to AA→B→C→A 构成有向环 。 1. 连通图与强连通图： * 连通图（针对无向图）：若图中任意两个顶点之间都存在路径，则称该图为连通图。比如一个表示城市交通的无向图，若任意两个城市之间都有道路可达，那么这个图就是连通图。 * 强连通图（针对有向图）：若有向图中任意两个顶点 uuu 和 vvv 之间，既存在从 uuu 到 $ v$ 的路径，也存在从 vvv 到 uuu 的路径，则称该图为强连通图。例如在一个表示公交站点单向线路的有向图中，若任意两个站点都能通过公交线路相互到达，就是强连通图。 1. 简单图与多重图： * 简单图：没有自环（即顶点到自身的边）且任意两个顶点之间最多只有一条边相连的图。如常见的表示人际关系的图，两个人之间要么是朋友关系（一条边），要么不是，且自己不会和自己成为朋友（无自环）。 * 多重图：允许有重复边，即同一对顶点之间可以有多条边，也可能存在自环。例如在一个表示城市间不同类型交通线路（公路、铁路等）的图中，两个城市之间可能既有公路连接又有铁路连接，这就形成了多重图。 1. 加权图：边带有权重的图，权重可以表示距离、成本、时间等实际意义的数值。例如在一个表示城市间距离的加权图中，边的权重就是两个城市之间的实际距离。 2. 子图：从原图中选取部分顶点和这些顶点之间的边所构成的图。例如在一个大型社交网络中，选取其中一个小团体成员及其相互关系，就构成了原图的一个子图。 3. 连通分量（无向图）：无向图中的极大连通子图。极大性意味着在这个子图中添加任何一个不属于它的顶点，都会破坏其连通性。例如一个非连通的无向图可能由多个相互独立的连通区域组成，每个区域就是一个连通分量。 4. 强连通分量（有向图）：有向图中的极大强连通子图。不同强连通分量之间可能存在单向路径，但不存在相互可达的路径。例如在一个复杂的有向任务依赖图中，可以划分出多个强连通分量，每个分量内的任务相互依赖，不同分量之间有一定的单向依赖关系。 5. 完全图：对于无向图，若任意两个不同顶点之间都有一条边相连，则称为完全图。假设有 nnn 个顶点，边的数量为 n(n−1)2\frac{n(n - 1)}{2}2n(n−1) 。例如 333 个顶点的完全无向图，每个顶点都与另外两个顶点相连，共 333 条边。 6. 二分图：顶点可以被分为两个不相交的集合 AAA 和 BBB，使得图中的每条边都连接集合 AAA 中的一个顶点和集合 BBB 中的一个顶点。比如在一个学生和课程的关系图中，学生为一个集合，课程为另一个集合，边表示学生选修课程，这可以构成一个二分图。 7. 有向无环图（DAG）：有向图中不存在环的图。在实际应用中，如课程先修关系图，课程 AAA 是课程 BBB 的先修课程，就有一条从 AAA 到 BBB 的有向边，且不会出现课程之间相互依赖成环的情况，这就是典型的有向无环图。 8. 欧拉图：包含一条经过每条边且每条边只经过一次的闭合路径（欧拉回路）的图。例如在一个一笔画问题中，如果一个图形可以从某一点出发，不重复地遍历所有边后回到起点，那么这个图形对应的图就是欧拉图。 9. 哈密顿图：包含一个经过每个顶点且每个顶点只经过一次的路径（哈密顿路径）的图。类似于旅行商问题，商人要访问每个城市一次且仅一次，若能找到这样的路线，对应的城市连接图就是哈密顿图 。 10. 平面图：可以嵌入在平面上，使得边不相交的图。例如一些简单的电路布线图，若能在平面上合理布局线路而不出现交叉，对应的图就是平面图。 二、图的表示方法（理解） 1. 邻接矩阵：用一个二维数组 matrixmatrixmatrix 来表示图中顶点之间的邻接关系。对于无向图，如果顶点 iii 和顶点 jjj 之间有边相连，则 matrix[i][j]=matrix[j][i]=1matrix[i][j] = matrix[j][i] = 1matrix[i][j]=matrix[j][i]=1（对于无权图），若有权则存储边的权重；对于有向图，如果存在从顶点 iii 到顶点 jjj 的有向边，则 matrix[i][j]=1matrix[i][j] = 1matrix[i][j]=1（无权）或存储权重。例如一个 333 个顶点的无向图，若顶点 111 和顶点 222 相连，顶点 222 和顶点 333 相连，其邻接矩阵为 [010101010]\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} 010 101 010 。邻接矩阵的优点是直观，便于判断两点之间是否有边相连，缺点是空间复杂度较高，为 O(n2)O(n^2)O(n2)，适用于稠密图（边的数量接近 n(n−1)n(n - 1)n(n−1) 的图） 。 2. 邻接表：对每个顶点，用一个链表（或数组）存储与之直接相连的顶点。例如顶点 vvv 的邻接表中存储着所有与 vvv 有边相连的顶点。对于无向图，若顶点 111 与顶点 222、顶点 333 相连，那么顶点 111 的邻接表可能是 [2,3][2, 3][2,3]；对于有向图，若存在从顶点 111 到顶点 222、顶点 333 的有向边，顶点 111 的邻接表同样是 [2,3][2, 3][2,3] 。邻接表空间复杂度为 O(n+m)O(n + m)O(n+m)，其中 nnn 是顶点数， mmm 是边数，适用于稀疏图（边的数量远小于 n(n−1)n(n - 1)n(n−1) 的图），在查找某个顶点的邻接顶点时效率较高 。 三、图论核心性质（掌握） 1. 握手定理（度数和与边数的关系）：在任何图中，所有顶点的度数之和等于边数的两倍。即 ∑v∈Vdegree(v)=2m\sum_{v \in V} degree(v) = 2m∑v∈V degree(v)=2m，其中 degree(v)degree(v)degree(v) 表示顶点 vvv 的度数， mmm 是边数。例如在一个有 444 条边的无向图中，所有顶点度数之和为 888 。这个性质可以帮助我们通过已知的度数或边数信息，推导其他未知量。 2. 连通图的边数下限：对于一个包含 $ n $ 个顶点的连通无向图，至少需要 $ n - 1 $ 条边。例如 $ 3 $ 个顶点的连通无向图，最少有 $ 2 $ 条边（如 $ 1 - 2 - 3 $ 这样的线性连接）。当边数恰好为 $ n - 1 $ 时，图的结构是一棵树，树是一种特殊的连通无向图，无环且边数最少 。 3. 有向无环图（DAG）的性质： * 一定存在入度为 000 的顶点和出度为 000 的顶点。例如在一个课程先修关系的 DAG 中，必定有不需要先修其他课程的基础课程（入度为 000），也有没有后续课程的最终课程（出度为 000）。 * 可以进行拓扑排序，将顶点排成一个线性序列，使得对于每一条有向边 <u,v><u, v><u,v>，顶点 uuu 在序列中出现在顶点 vvv 之前。拓扑排序在解决任务调度、依赖关系等问题中非常重要 。 1. 二分图的判定性质：一个图是二分图当且仅当图中不存在奇数长度的环。例如在一个表示男女匹配的图中，如果不存在奇数个顶点依次相连形成环的情况，那么这个图就是二分图，可以将顶点划分为男性集合和女性集合，且边只连接不同集合的顶点 。 2. 欧拉图的判定性质： * 无向图是欧拉图当且仅当图是连通的且每个顶点的度数都是偶数。例如一个 “日” 字形的无向图，每个顶点度数为偶数且连通，存在欧拉回路，可以从某点出发一笔画遍历所有边回到起点。 * 有向图是欧拉图当且仅当图是强连通的且每个顶点的入度等于出度。例如在一个表示单向循环道路的有向图中，若每个路口进入和出去的道路数量相等且任意两点可相互到达，就满足欧拉图条件 。 1. 哈密顿图的一些必要条件（非充分）：若图 G=(V,E)G=(V, E)G=(V,E) 是哈密顿图，对于 VVV 的任意非空真子集 SSS，均有 w(G−S)≤∣S∣w(G - S) \leq |S|w(G−S)≤∣S∣，其中 w(G−S)w(G - S)w(G−S) 表示图 GGG 删除顶点集 SSS 后得到的子图的连通分量个数，∣S∣|S|∣S∣ 表示集合 SSS 中顶点的个数。例如在一个有 555 个顶点的图中，若删除 222 个顶点后，剩余子图的连通分量个数不超过 222，则该图有可能是哈密顿图，但不满足此条件一定不是哈密顿图 。 2. 平面图的欧拉公式：对于连通的平面图，有 n−m+f=2n - m + f = 2n−m+f=2，其中 $ n $ 是顶点数， mmm 是边数， fff是面数（包括外部无限面）。例如一个简单的三角形平面图，顶点数 n=3n = 3n=3，边数 m=3m = 3m=3，面数 f=2f = 2f=2（内部一个面和外部无限面），满足 3−3+2=23 - 3 + 2 = 23−3+2=2 。通过这个公式，已知其中两个量可以求解第三个量，在判断图是否为平面图以及计算相关参数时很有用 。 > （注：文档1112\frac{11}{12}1211 的内容由 AI 生成） > （注：不为干啥，不为加精） > 给个赞吧QwQ

树核心知识点与解题技巧（初一级别 / CSP 备考适用） 在 CSP 初赛（笔试）中，树的考查聚焦于概念定义、性质推导、基础计算，不涉及复杂代码实现，核心是理解树的本质特征并能灵活运用公式解决问题。以下是针对初一级别备考的核心知识点与解题技巧，完全匹配初赛考查范围： 一、树的核心概念（初赛必背） 树是一种无环的连通无向图，是图论中最简单的连通结构，所有概念需精准记忆，避免与 “图”“森林” 混淆： 概念 定义（初赛核心考点） 树(Tree) 1. 连通（任意两点有且只有一条路径）；2. 无环；3. 边数 = 节点数 - 1（三个条件等价，初赛常用来判断 “是否为树”）。 森林(Forest) 由多棵互不连通的树组成（无环，但不连通）；边数 = 总节点数 - 树的棵数。 节点 - 根节点：有根树中唯一 “顶端” 节点（如二叉树的根）；- 叶子节点：度数为 1 的节点（无子节点）；- 父 / 子节点：有根树中，连接的上下层节点（如二叉树中，一个节点的直接下层是子节点）。 二叉树 每个节点最多有 2 个子节点（左子节点、右子节点），是初赛树类问题的高频载体。 特殊二叉树 - 满二叉树：除叶子外，所有节点都有 2 个子节点（叶子在同一层）；- 完全二叉树：按 “层序遍历” 顺序编号（1~n），所有节点编号与满二叉树完全对应（叶子只可能在最后两层，且最后一层叶子靠左）。 二、树的关键性质（初赛计算题核心） 初赛中 80% 的树相关题目围绕以下性质展开，需理解推导逻辑 + 牢记公式，避免死记硬背： 1. 通用性质（所有树适用） * 性质 1：边数与节点数的关系 对任意一棵树，若节点数为 n，边数为 m，则 m = n - 1（树的本质特征，初赛常用来 “反向计算节点数” 或 “判断是否为树”）。 例：一棵有 10 条边的树，节点数是多少？答：10 + 1 = 11。 * 性质 2：度数和与边数的关系 所有节点的度数之和 = 2 × 边数（图的通用性质，结合树的 “边数 = n-1”，可推导树的度数关系）。 例：一棵有 n 个节点的树，所有节点度数之和是多少？答：2 (n-1)。 * 性质 3：叶子节点数的计算（高频考点） 若树中只有 “叶子节点（度数 1）” 和 “度数≥2 的节点”，设叶子数为 L，度数≥2 的节点数为 k，则： 由度数和公式：L×1 + （度数≥2节点的总度数） = 2(n-1)，且 n = L + k，代入可简化为： L = （度数≥2 节点的总度数） - 2k + 2 最常见场景：树中只有叶子（度数 1）和度数为 2 的节点（如一条 “链”），此时 “度数≥2 节点的总度数 = 2k”，代入得 L = 2（链的两端是叶子，中间节点度数 2，符合常识）。 例：一棵树上有 3 个度数为 3 的节点，其余都是叶子，求叶子数？答：总度数 = 3×3 + L×1 = 9 + L；边数 =(3+L)-1 = L+2；度数和 = 2× 边数 → 9+L=2 (L+2) → L=5。 2. 二叉树的特殊性质（初赛重中之重） 二叉树的性质围绕 “节点数、层数、叶子数” 展开，尤其是完全二叉树的计算，几乎每年初赛都会涉及： 性质 内容（初赛必考） 性质 1：第 k 层节点数上限 若二叉树的根节点在第 1 层（初赛默认层数从 1 开始），则第 k 层最多有 2k−12^{k-1}2k−1 个节点。 性质 2：深度为 h 的节点数上限 深度（最大层数）为 h 的二叉树，最多有 2h−12^{h - 1}2h−1 个节点（即满二叉树的节点数）。 性质 3：完全二叉树的节点编号 对 n 个节点的完全二叉树，按层序编号（1~n），对任意编号为 i 的节点：- 左子节点编号：2i（若 2i ≤n，否则无左子节点）；- 右子节点编号：2i+1（若 2i+1 ≤n，否则无右子节点）；- 父节点编号：i//2（i>1 时，整除）。 性质 4：完全二叉树的叶子数 对 n 个节点的完全二叉树，叶子节点数为 n//2 或 (n+1)//2（两种情况等价，因整数除法特性）：- 若 n 为偶数：叶子数 = n/2；- 若 n 为奇数：叶子数 = (n+1)/2。 性质 5：完全二叉树的深度 深度 h = floor(log₂n) + 1（floor 表示 “向下取整”，初赛可通过 “2h−12^{h-1}2h−1 ≤n≤n≤n <2h<2^h<2h” 反向推导 h）。 三、初赛常见题型与解题技巧 初赛中树的题目以 “选择题”“填空题” 为主，题型固定，掌握技巧可快速得分： 题型 1：判断 “是否为树” 解题技巧：利用树的三个等价条件，满足任意一个即可判断： 1. 连通 + 无环； 2. 连通 + 边数 = 节点数 - 1； 3. 无环 + 边数 = 节点数 - 1。 例：一个有 5 个节点、4 条边的图，是否为树？答：若连通则是（边数 = 5-1=4）；若不连通则是森林。 题型 2：计算叶子节点数 解题技巧：分两步： 1. 确定 “非叶子节点的度数总和”（如 “2 个度数 3 的节点，1 个度数 4 的节点”，总和 = 2×3+1×4=10）； 2. 代入公式：叶子数 L = 非叶子节点总度数 - 2× 非叶子节点数 + 2（推导自 “度数和 = 2× 边数” 和 “边数 = 总节点数 - 1”）。 例：一棵树上有 1 个度数为 4 的节点，2 个度数为 3 的节点，其余为叶子，求叶子数？答：非叶子总度数 = 4+2×3=10；非叶子节点数 = 3；L=10 - 2×3 +2=6。 题型 3：完全二叉树的计算（高频） 解题技巧：牢记 “编号规则” 和 “叶子数公式”，优先用 “编号” 推导： * 求某节点的子 / 父节点：直接用 “左子 = 2i，右子 = 2i+1，父 = i//2”（注意判断 “是否存在子节点”，即编号≤n）； * 求叶子数：直接用 “n//2”（无论 n 奇偶，结果正确）； * 求深度：找到最大的 h 使得 2^(h-1) ≤n <2^h（如 n=10，23=8≤10<16=24，深度 h=4）。 例 1：完全二叉树有 15 个节点，求叶子数？答：15//2=7？错！15 是满二叉树（2^4-1=15），叶子数 = 8，此时用 “(15+1)//2=8” 更准确，本质是 “n 为奇数时叶子数 =(n+1)/2”。 例 2：完全二叉树中，编号为 6 的节点的左子节点编号是多少？答：2×6=12（若总节点数≥12，则存在，否则不存在）。 题型 4：森林与树的转换 解题技巧：利用森林的核心公式：边数 m = 总节点数 n - 树的棵数 k（森林是多棵树，每棵树满足 mi=ni−1m_i = n_i -1mi =ni −1，总和即 m=Σmi=Σni−Σ1=n−km=Σm_i=Σn_i -Σ1 =n - km=Σmi =Σni −Σ1=n−k）。 例：一个森林有 20 个节点、15 条边，求森林中有几棵树？答：k = n -m =20-15=5。 四、易错点提醒（初赛避坑） 1. 层数起点：初赛中二叉树的 “层数” 默认从 1 开始（根为第 1 层），若按 “第 0 层” 计算会出错（如第 k 层节点数会变成 2k2^k2k，而非 2k−12^{k-1}2k−1）； 2. 完全二叉树 vs 满二叉树：满二叉树是特殊的完全二叉树，但完全二叉树不一定是满的（最后一层叶子靠左），计算叶子数时别混淆； 3. 度数的定义：无向树中 “节点的度数” 是 “连接的边数”（根节点的度数也按边数算，如根有 2 个子节点，度数为 2），别误将 “子节点数” 当作 “度数”（有根树中父 / 子是相对概念，度数是图的绝对概念）。 通过以上知识点的梳理，结合 “性质记公式、题型练技巧”，可完全覆盖 CSP 初赛中树的考查范围，初一学生需重点掌握 “叶子数计算” 和 “完全二叉树的应用”，这两类题目占树相关分值的 70% 以上。 > （注：文档1112\frac{11}{12}1211 的内容由 AI 生成） > （注：不为干啥，不为加精） > 给个赞吧QwQ

组合学核心知识点与解题技巧（初一级别 / CSP 备考适用） 一、基础原理：组合学的 “底层逻辑” （一）加法原理：“选一类就能完成，把方法数加起来” 1. 核心定义 做一件事，有kkk类不同方法（每类方法单独用就能做完这件事，且各类方法不重复），第 1 类有n1n_1n1 种方法，第 2 类有n2n_2n2 种方法…… 第kkk类有nkn_knk 种方法，总方法数就是各类方法数的和。 2. 公式 总方法数 = n1+n2+⋯+nkn_1 + n_2 + \dots + n_kn1 +n2 +⋯+nk 3. 例子 从家到学校有 3 种方式：坐公交有 2 路、3 路（2 种选法），骑自行车有普通自行车、山地车（2 种选法），走路只有 1 种方式。总共有多少种去学校的方法？ 解：三类方法互斥，直接相加 → 2+2+1=52 + 2 + 1 = 52+2+1=5种。 （二）乘法原理：“分多步才能完成，把每步方法数乘起来” 1. 核心定义 做一件事，需要分kkk步完成（少一步都做不完），第 1 步有n1n_1n1 种方法，第 2 步有n2n_2n2 种方法…… 第kkk步有nkn_knk 种方法，总方法数就是每步方法数的乘积。 2. 公式 总方法数 = n1×n2×⋯×nkn_1 \times n_2 \times \dots \times n_kn1 ×n2 ×⋯×nk 3. 例子 搭配一套衣服：上衣有 3 件（T 恤、衬衫、卫衣），裤子有 2 条（牛仔裤、运动裤）。总共能搭出多少套不同的衣服？ 解：分两步（先选上衣、再选裤子），两步方法数相乘 → 3×2=63 \times 2 = 63×2=6套（如 T 恤 + 牛仔裤、T 恤 + 运动裤等）。 二、经典排列模型：“有序” 的计数方法 （一）圆排列：“围圆圈排队，固定一个人再算” 1. 核心定义nnn个不同的人（或物品）围在圆圈上排列，因为圆圈没有 “起点” 和 “终点”（比如 5 人围坐，顺时针换位置后相对顺序不变），所以先固定 1 个人的位置，再算剩下的人怎么排。 2. 公式nnn个不同元素的圆排列数 = (n−1)!(n-1)!(n−1)! （“!” 是 “阶乘”，如3!=3×2×1=63! = 3 \times 2 \times 1 = 63!=3×2×1=6，4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 244!=4×3×2×1=24，表示 “从这个数开始，乘比它小 1 的数，直到乘到 1”） 3. 例子 5 个同学围圆桌吃饭，有多少种不同的坐法？ 解：固定 1 个同学的位置，剩下 4 个同学全排列 → 4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 244!=4×3×2×1=24种。 （二）重复排列：“选了还能再选，每步都有NNN种选法” 1. 核心定义 从nnn个不同的物品里，选kkk个物品排列（选过的物品还能再选），因为每一步选的时候所有物品都在，所以每步都有nnn种选法。 2. 公式 总排列数 = nkn^knk （nnn是物品总数，kkk是要选的个数，“nkn^knk” 表示nnn乘kkk次，如23=2×2×2=82^3 = 2 \times 2 \times 2 = 823=2×2×2=8） 3. 例子 用数字 0、1、2 组成 3 位数（数字可重复，如 111、202），总共能组成多少个？ 解：分 3 步（百位、十位、个位）： * 百位不能是 0，有 2 种选法（1、2）； * 十位可以是 0、1、2，有 3 种选法； * 个位和十位一样，3 种选法； 总个数 = 2×3×3=182 \times 3 \times 3 = 182×3×3=18种。 （三）不相邻排列：“先排不限制的，再插要间隔的” 1. 核心定义 要排两类物品，其中一类（如 A）不能相邻，就先把另一类（如 B）排好，再在 B 的 “空隙” 里插 A（空隙包括 B 的两端，确保 A 不相邻）。 2. 步骤公式（分两步） ① 先排无限制的mmm个物品 B：排列数 = m!m!m!（mmm个不同物品的全排列）； ② 算 B 的空隙数：有m+1m+1m+1个空隙（如 3 个 B 排成 “B B B”，空隙是 “_ B _ B _ B _”，共 4 个）； ③ 从m+1m+1m+1个空隙里选nnn个插 A，排列数 = Am+1nA_{m+1}^nAm+1n （Aab=a×(a−1)×⋯×(a−b+1)A_a^b = a \times (a-1)\times\dots\times(a-b+1)Aab =a×(a−1)×⋯×(a−b+1)，表示从aaa个里选bbb个排队）； ④ 总排列数 = m!×Am+1nm! \times A_{m+1}^nm!×Am+1n 3. 例子 有 3 个男生和 2 个女生排队，要求女生不能相邻，有多少种排法？ 解：① 先排男生：3!=3×2×1=63! = 3 \times 2 \times 1 = 63!=3×2×1=6种； ② 男生的空隙数：3+1=43+1 = 43+1=4个（“_ 男 _ 男 _ 男 _”）； ③ 从 4 个空隙选 2 个插女生：A42=4×3=12A_4^2 = 4 \times 3 = 12A42 =4×3=12种； ④ 总排法 = 6×12=726 \times 12 = 726×12=72种。 （四）错位排列：“每个人都不拿自己的东西” 1. 核心定义nnn个不同的物品（如nnn封信），分给nnn个对应对象（如nnn个邮箱），但每个物品都不能分给自己对应的对象，这种排列叫错位排列，用D(n)D(n)D(n)表示nnn个元素的错位排列数。 2. 公式（递推公式） * 当n=1n=1n=1时：只有 1 个物品，无法错位，D(1)=0D(1) = 0D(1)=0； * 当n=2n=2n=2时：2 个物品交换位置，只有 1 种错位，D(2)=1D(2) = 1D(2)=1； * 当n>=3n>=3n>=3时：D(n)=(n−1)×[D(n−1)+D(n−2)]D(n) = (n-1) \times [D(n-1) + D(n-2)]D(n)=(n−1)×[D(n−1)+D(n−2)]（第nnn个物品先和前面n−1n-1n−1个中的一个交换，再分两种情况算剩下的错位数） 1. 例子 3 个同学（甲、乙、丙）各有 1 支笔（甲的笔、乙的笔、丙的笔），把笔分给 3 人，每人都不能拿自己的笔，有多少种分法？ 解：用递推公式算 → D(3)=(3−1)×[D(2)+D(1)]=2×(1+0)=2D(3) = (3-1) \times [D(2)+D(1)] = 2 \times (1+0) = 2D(3)=(3−1)×[D(2)+D(1)]=2×(1+0)=2种（实际为 “甲拿乙的、乙拿丙的、丙拿甲的” 和 “甲拿丙的、乙拿甲的、丙拿乙的”）。 三、其他高频题型：CSP 常考场景 （一）涂色问题：“抓自由变量，从约束多的位置入手” 1. 核心思路 涂色问题常涉及 “相邻区域不同色”“网格染色”，关键是确定 “自由选择的位置” 和 “被约束的位置”，优先从约束最多的位置（如角落、边缘）开始分析。 * 若有 “每行 / 每列” 全局约束（如 “网格染色，每两行交点同色数为偶数”），可尝试 “首行首列确定全局”：先自由选首行和首列的颜色，剩余位置颜色由首行首列唯一确定（需验证约束）； * 若仅 “相邻不同色”（如环形、线性涂色），线性从一端开始，环形先固定一个位置避免重复。 1. 例子 用红、绿两种颜色给 2×2 网格染色（无相邻约束），共多少种？ 解：每个小格有 2 种选择，4 个小格分步计算 → 2×2×2×2=162 \times 2 \times 2 \times 2 = 162×2×2×2=16种。 （二）握手 / 比赛场次问题：“无序组合，选 2 个就对应一次” 1. 核心思路nnn个人互相握手、nnn队单循环赛，本质是 “从nnn个中选 2 个”（无序，交换两人 / 两队顺序不影响结果），直接用组合数公式。 2. 公式 总次数 = C(n,2)=n(n−1)2C(n,2) = \frac{n(n-1)}{2}C(n,2)=2n(n−1) （C(n,k)C(n,k)C(n,k)表示从nnn个里选kkk个的组合数，C(n,k)=n!k!(n−k)!C(n,k) = \frac{n!}{k!(n-k)!}C(n,k)=k!(n−k)!n! ） 3. 例子 10 人互相握手，总次数 = C(10,2)=10×92=45C(10,2) = \frac{10 \times 9}{2} = 45C(10,2)=210×9 =45次； 8 队单循环赛，总场次 = C(8,2)=8×72=28C(8,2) = \frac{8 \times 7}{2} = 28C(8,2)=28×7 =28场。 （三）数字排列问题：“分类讨论，规避约束” 1. 核心思路 常涉及 “无重复数字”“首位≠0”“奇偶性” 等约束，需结合加法原理分类（如按个位奇偶性分），再用乘法原理分步计算。 2. 例子 用 0-5 组成无重复数字的三位偶数，共多少种？ 解：按个位分 3 类（个位 = 0/2/4）： * 个位为 0：首位从 1-5 选（5 种），十位从剩下 4 数选（4 种）→ 5×4=205 \times 4 = 205×4=20种； * 个位为 2：首位从 1,3,4,5 选（4 种），十位从剩下 4 数选（4 种）→ 4×4=164 \times 4 = 164×4=16种； * 个位为 4：同个位为 2，16 种； 总结果 = 20+16+16=5220+16+16 = 5220+16+16=52种。 （四）分组分配问题：“平均分组要除序，分配任务不除序” 1. 核心思路 * 若组别无区分（平均分组，如 “6 人分成 3 组，每组 2 人”）：需除以 “组数的阶乘”（消除重复分组顺序）； * 若组别有区分（分配任务，如 “6 人分给 3 个不同班级，每班 2 人”）：无需除序，直接分步选。 1. 公式与例子 * 平均分组（6 人分 3 组，每组 2 人）： 先分步选：C(6,2)×C(4,2)×C(2,2)=15×6×1=90C(6,2) \times C(4,2) \times C(2,2) = 15 \times 6 \times 1 = 90C(6,2)×C(4,2)×C(2,2)=15×6×1=90种； 除以组数阶乘（3 组）：90A(3,3)=906=15\frac{90}{A(3,3)} = \frac{90}{6} = 15A(3,3)90 =690 =15种（A(3,3)=3!=6A(3,3)=3! = 6A(3,3)=3!=6）。 * 分配任务（6 人分给 3 个不同班级，每班 2 人）： 直接分步选：C(6,2)×C(4,2)×C(2,2)=90C(6,2) \times C(4,2) \times C(2,2) = 90C(6,2)×C(4,2)×C(2,2)=90种。 （五）成对问题：“先定成对，再选不成对” 1. 核心思路 如 “手套选 k 只，恰好配 m 副”，先确定 m 副的选法，再从剩余种类中选 “不成对” 的，避免重复。 2. 例子 5 副不同颜色的手套（共 10 只），取 6 只恰好配 2 副，有多少种选法？ 解：① 选 2 副手套：C(5,2)=10C(5,2) = 10C(5,2)=10种； ② 从剩下 3 副中选 2 只不成对的（每副选 1 只）：C(3,2)×2×2=3×2×2=12C(3,2) \times 2 \times 2 = 3 \times 2 \times 2 = 12C(3,2)×2×2=3×2×2=12种（选 2 副，每副 2 种选择）； 总结果 = 10×12=12010 \times 12 = 12010×12=120种。 （六）容斥原理：“算并集，减重复，加回多减的” 1. 定义：由若干个确定的、互不相同的元素组成的整体，用大写字母表示（如集合AAA、集合BBB），元素用小写字母表示（如a∈Aa \in Aa∈A表示 “aaa是AAA的元素”，a∉Aa \notin Aa∈/A表示 “aaa不是AAA的元素”）。 * 例：“小于 5 的正整数” 可表示为集合A={1,2,3,4}A = \{1,2,3,4\}A={1,2,3,4}，其中元素1∈A1 \in A1∈A，5∉A5 \notin A5∈/A。 2. 关键属性： * 确定性：元素是否属于集合必须明确（如 “好看的颜色” 不能构成集合，因为 “好看” 无标准；“红色、蓝色” 可构成集合）。 * 互异性：集合中元素不重复（如{1,1,2}\{1,1,2\}{1,1,2}不是有效集合，需写成{1,2}\{1,2\}{1,2}）。 * 无序性：集合中元素顺序不影响（如{1,2}\{1,2\}{1,2}和{2,1}\{2,1\}{2,1}是同一个集合）。 3. 常用集合关系： * 子集：若AAA的所有元素都在BBB中，称AAA是BBB的子集，记为A⊆BA \subseteq BA⊆B（如A={1,2}A=\{1,2\}A={1,2}，B={1,2,3}B=\{1,2,3\}B={1,2,3}，则A⊆BA \subseteq BA⊆B）。 * 交集：由同时属于AAA和BBB的元素组成的集合，记为A∩BA \cap BA∩B（如A={1,2,3}A=\{1,2,3\}A={1,2,3}，B={3,4,5}B=\{3,4,5\}B={3,4,5}，则A∩B={3}A \cap B = \{3\}A∩B={3}）。 * 并集：由属于AAA或属于BBB的所有元素组成的集合，记为A∪BA \cup BA∪B（如A={1,2,3}A=\{1,2,3\}A={1,2,3}，B={3,4,5}B=\{3,4,5\}B={3,4,5}，则A∪B={1,2,3,4,5}A \cup B = \{1,2,3,4,5\}A∪B={1,2,3,4,5}）。 * 补集：在 “全体元素集合（全集UUU）” 中，不属于AAA的元素组成的集合，记为∁UA\complement_U A∁U A（如全集U={1,2,3,4,5}U=\{1,2,3,4,5\}U={1,2,3,4,5}，A={1,2}A=\{1,2\}A={1,2}，则∁UA={3,4,5}\complement_U A = \{3,4,5\}∁U A={3,4,5}）。 当需要计算 “多个集合的并集元素个数” 时，直接相加会重复计算 “交集部分”，容斥原理通过 “加并集、减交集、加三交集” 的方式，精准消除重复，是解决 “至少满足一个条件” 问题的核心工具。 1. 两个集合的容斥原理（基础版） * 公式：对于任意两个集合AAA和BBB，并集的元素个数 = 两个集合元素个数之和 - 交集的元素个数，即： ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ * 含义：先算AAA和BBB的总元素（∣A∣+∣B∣|A|+|B|∣A∣+∣B∣），但AAA和BBB重叠的部分（A∩BA \cap BA∩B）被算了两次，所以减去 1 次。 * 例子： 某班有 20 人喜欢数学，15 人喜欢英语，其中 8 人既喜欢数学又喜欢英语，求喜欢数学或英语的总人数。 解：设AAA=“喜欢数学的人”，BBB=“喜欢英语的人”，则∣A∣=20|A|=20∣A∣=20，∣B∣=15|B|=15∣B∣=15，∣A∩B∣=8|A \cap B|=8∣A∩B∣=8。 喜欢数学或英语的人数 = ∣A∪B∣=20+15−8=27|A \cup B| = 20 + 15 - 8 = 27∣A∪B∣=20+15−8=27人。 2. 三个集合的容斥原理（进阶版） * 公式：对于任意三个集合AAA、BBB、CCC，并集的元素个数 = 三个集合元素个数之和 - 每两个集合的交集之和 + 三个集合的交集，即： ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣ * 含义：先加三个集合总元素，再减去每两个的交集（消除两次重复），但此时三个集合的交集被多减了 1 次，所以加回 1 次。 * 例子： 某校参加数学、物理、化学竞赛的人数分别为 12、10、8，其中同时参加数学和物理的有 5 人，同时参加数学和化学的有 3 人，同时参加物理和化学的有 2 人，三个竞赛都参加的有 1 人，求至少参加一个竞赛的人数。 解：设AAA=“数学竞赛”，BBB=“物理竞赛”，CCC=“化学竞赛”，则： ∣A∪B∪C∣=12+10+8−5−3−2+1=21|A \cup B \cup C| = 12 + 10 + 8 - 5 - 3 - 2 + 1 = 21∣A∪B∪C∣=12+10+8−5−3−2+1=21人。 （七）鸽巢原理（抽屉原理）：“东西多，盒子少，必有一个盒子装得多” 鸽巢原理是解决 “必然存在某种情况” 的计数工具，核心是利用 “元素数量” 与 “容器数量” 的差距，推导确定性结论，常考 “至少有kkk个元素在同一容器” 的问题。 1. 基础鸽巢原理（简单版） * 核心结论：若有nnn个 “鸽巢”（容器），mmm个 “鸽子”（元素），且m>nm > nm>n，则至少有一个鸽巢里有 2 只或更多鸽子。 * 公式化表达：若m>nm > nm>n，则存在至少一个鸽巢，其鸽子数≥2\geq 2≥2。 * 例子： 13 个人中，为什么至少有 2 人生日在同一个月？ 解：“月份” 是鸽巢（共 12 个），“人” 是鸽子（共 13 个），13 > 12，因此至少有 2 人在同一月生日。 2. 进阶鸽巢原理（通用版） * 核心结论：若有nnn个鸽巢，mmm个鸽子，则至少有一个鸽巢里的鸽子数（⌈x⌉\lceil x \rceil⌈x⌉表示 “向上取整”，即不小于xxx的最小整数，如⌈2.1⌉=3\lceil 2.1 \rceil=3⌈2.1⌉=3，⌈3⌉=3\lceil 3 \rceil=3⌈3⌉=3）。 * 用途：计算 “至少有多少个元素在同一容器”，避免 “极端分配” 的误区（如 “尽量平均分配后，总有一个容器多 1 个”）。 * 例子： 25 个苹果分给 4 个小朋友，至少有一个小朋友能分到多少个苹果？ 解：⌈254⌉=⌈6.25⌉=7\lceil \frac{25}{4} \rceil = \lceil 6.25 \rceil = 7⌈425 ⌉=⌈6.25⌉=7，因此至少有一个小朋友分到 7 个苹果（验证：若每人分 6 个，共分4×6=244 \times 6 = 244×6=24个，剩 1 个，必须分给某一人，使其分到 7 个）。 四、解题技巧：“四步走” 规避陷阱 1. 明确目标 确定题目要计算 “排列 / 组合 / 分组 / 染色”，列出所有约束（如首位≠0、相邻不同色、至少 1 个等）。 2. 选择方法 * 遇 “或” 用加法（分类），遇 “且” 用乘法（分步）； * 有序用排列（A (n,k)），无序用组合（C (n,k)）； * 相邻用捆绑法，不相邻用插空法； * 正面复杂用反向（总情况 - 不符合情况）。 1. 计算验证 注意 “平均分组除序”“捆绑内部排列” 等细节，避免重复或遗漏。 2. 小值测试 用小数据验证逻辑（如分组问题用 n=4 分 2 组，公式算是否为 3 种，手动枚举确认）。 > （注：文档1920\frac{19}{20}2019 的内容由 AI 生成） > （注：不为干啥，不为加精） > 给个赞吧QwQ

(留个句号吧下次来你就是古人了） 欢迎观看我的Markdown学习史 出题的dalao:@无敌小浅大王 @155****6772(其实就是本贴的作者）@林小吉 想了解沈拓的看这个链接描述 介绍一下背景： 作为贪心算法转世的沈拓，曾经在杭州xiao码集训营XP03-A2班，由于他天天贪污食堂的饭菜，导致受到全班讨伐，创造了下列题目轰炸ta ————————————————————————————————————— Day 0上午(2025-08-10) U62303.贪心的沈拓 直接看题目描述（题不是我写的是这位兄台@无敌小浅大王）： /贪心的沈拓）总是在食堂拿走很多饭菜，每天出现的菜一共有n种，每一道菜的数量也不相同，可是贪心的沈拓因为拿走很多饭菜的原因，会受到大家的讨伐，一旦沈拓“贪”到的食物总量超过k个，那么沈拓就会"思慕"，沈拓向你们求助他应该如何在不"思慕"的情况下在哪一个区间内“贪”到的饭菜最多 没有则输出-1/ 有可能你食堂的资源点就是被ta清空的！！写起！！！ 还有这题也是写贪心沈拓的 ————————————————————————————————————— Day 0下午 那俩出题的兄台告诉我ta俩的题目数据是打表打出来的，大概率AC不了，服了 我会尽快创造出新的题目de! ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Day 1(实际过去好久了）(2025-08-31) 沈拓那道题也是由作者自己做出来了，快去看看吧！ （但是作者自己又加了3个测试点，用那些AC方法最后一个测试点过不了@无敌小浅大王 强烈建议改良 我自己造了道很简单的题XDU70062.贪心的沈拓2，快过来写！！！！！！ ————————————————————————————————————— Day 2(2025-09-07) bro的团队的朋友也出了一道题T66833.TEAMS-沈拓好贪心，快过来看看吧！ ——（插播一则广告 我和“TEAMS”的朋友们都在这里等你，快来一起学习吧！ Day 2下午 bro要的U70062.贪心的沈拓2的题解ta来了！！！！（作者自己看不懂了， dalao们自己评吧(题解给出者：@无敌小浅大王（棒！！！牛逼！！！ > > 代码1：（作者自己看不懂了，dalao们自己评吧（非人解法，人解法在下面） > > 这是人类解法（作者终于能看懂了）代码2： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Day 3(2025-09-20) 解锁了我的Markdown学习史（记录自己何时学会了Markdown排版的一些用法）

太好了： 看看这是什么

因为CSP考炸了，所以退了。。。

名称：头文件 代码：#include <iostream> <cmath> <cstdio> 要发的文字\HUGE 要发的文字要发的文字 名称：命名空间 代码：using namespace std； 名称：主函数 代码：int main（）{ } 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 老王老王老王 符号：// 作用：笔记 符号：/**/ 作用：多行笔记 代码：cont << "C++" 作用：输出内容（装进纸箱扔下山） 指令：endl 作用：换行 int 变量类型 a 变量名 定义多个变量，使用逗号隔开变量名 变量需要按照命名规则命名 Abc a123 A_1是合法的，变量名只能使用 大小写字母， 数字和下划线组成 Art 和art 不是同一个变量，字母严格区分大小写 123ABC不合法，第一个字符不能是数字 int不合法，变量名不能和关键字相同 等于号是赋值运算符， 是将等号右边的值传递给等于号的左边 cin不读取空格和换行 * 加法运算符 * 乘法运算符 —减法运算符 / 除法运算符 % 取余运算符 int范围 210的9次方 longlong超长整形 910的18次方 double可以存小数 1.78*10的308次方 初始类型转换 int a = 2.5; cout << a; 表达式计算类型转换 cout << 5 /2.0; *制类型转换 int a = 5; cout << (double)(a) / 2; 函数名 参数 举例 MAX 同类型的A和B MAX（4,5）=5 MIN 同类型的A和B MIN（4,5）=4 POW double型的A和B POW（2,4）=16 ABS 数字X（浮点/整）ABS （-3）=3 SQRT double类型X SQRT（81）=9.0 开始 -> 表达式？-> 语句组 ->结束 | | 否 -----------------> 名称：布尔类型 代码：bool 非0输出true（1），为0输出false （0） 名称：流程图 功能：表示思路 开始/结束：圆角矩形 执行步骤：长方形 条件判断：菱形 输入输出：*行四边形 下一步执行方向：箭头 if(a>b){ cout << "a最帅"; }else{ cout << "b最帅"; } 一个等号是赋值，两个等号是比较判断， 看左右是否相等 开始 -> 表达式？ 结束 | | 否 ------->语句组2 转意字符 \n换行符 \r回车键 \t水*制表符 \代表一个反斜杠字符 名称：三目运算符 形式：条件？表达式1：表达式2 （条件） ？ 表达式1 表达式2 ----------------------> if（表达式1） 语句组1 else if（表达式2） 语句组2 else 语句组3 名称：开关语句 代码：switch switch(常量表达式) { case 常量1：语句1；break 如果程序运行时遇到break语句就结束语句 case 常量2：语句2；break } 名称：字符类型 代码：char char c = '1' ;字符类型 名称：分支嵌套 简介：分支嵌套分支 作用：在分支语句内部，可以嵌套另一个分支语句来进行更加复杂的条件判断 闰年的判断条件：四年一闰，百年不闰，四百年再闰 if(y%40) { if(y%100!=0){ cout << "闰"; } } if(y%4000){ cout << "闰"; } 名称：逻辑与 符号：& 特点：全真才真，否则为假 名称：逻辑或 符号：|| 特点：全假才假，否则为真 名称：逻辑非 符号：! 特点：真变假，假变真 自增/自减运算符 代码：i++，i-- 表达式 等价写法 a b b= a; a=a+1 b=a 4 4 b= a; b=a a=a+1 4 3 b= --a; a=a-1 b=a 2 2 b= a--; b=a a=a-1 2 3 名称：while循环 简介：条件判断循环 while(i<=100000000000000000000000000000000000000000000000000000){ cout << "韩老师史诗级最毁灭级超世界第一称霸宇宙传说神级宇宙级超级无敌霹雳超神牛皮帅！！！" <<endl; i = i + 1; } (n%40&&n%100!=0||n%4000) 名称：for循环 初始值 ------->循环条件为真吗？----->执行循环体----->条件改变 ------> | | <----------------------------------- for(初始值，循环条件，条件改变){ 循环体 } 步骤1：初始化[初始值1] 步骤2： 若循环条件为真， 则依次执行[循环体，条件改变] 若[循环条件] 为假，则结束 步骤3：重复执行步骤2 for(int i = 1,i <= 100,i += 2) { } 名称：continue 翻译：停顿后继续 for(int i = 1 ; i<=10;i++){ if(i%2==1)continue; cout << i <<" "; } 作用：跳过本次循环 名称：break 翻译：终止 for(int i = 1; i <= 10 ; i++){ if(i%2==0)break; cout << i <<" "; } 作用：结束本层循环（终止当前所在的循环体） int a[10]={3,4,5,6,8,10}; cout << a[4]; 数组的使用 int arr[10] = {0,1,2,3,4,5}; for(int i = 7; i >= 0; i--) { cout << a[i] << " " ; } 统计字符 #include <bits/stdc++.h> using namespace std; int main(){ string a; int ans = 0; getline(cin,a); for(int i = 0;i < a.size();i++){ if(a[i] != ' ') ans++; } cout << ans; } 第几个字母 #include <bits/stdc++.h> using namespace std; int main(){ char s; cin >> s; if(s>='a'&&s<='z'){ cout << s-'a'+1 << endl; }else{ cout << s-'A'+1<<endl; } return 0; } 最大值与最小值之和 #include<bits/stdc++.h> using namespace std; int main(){ int n,a[110],min_=1000010,max_=-1; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; min_=min(min_,a[i]); max_=max(max_,a[i]); } int sum=0; for(int i=0;i<n;i++){ if(min_==a[i] || a[i]==max_){ continue; } sum += a[i]; } cout<<sum; return 0; } 倒序输出三角形 #include <iostream> #include <cstring> using namespace std; int main() { int n; char c; cin >> n; cin >> c; for(int i = 1; i<=n;i++){ for(int j = n;j>=i;j--){ cout << c; } cout << endl; } } printf("%md",x) ; %lf:输出浮点数型变量 %d: 输出整型变量 %md:右对齐m位输出 数位分离 #include<bits/stdc++.h> using namespace std; int main(){ string x; cin>>x; for(int i=x.size()-1;i>=0;i--){ cout<<x[i]<<" "; } return 0; } 乘法口诀表 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; if(n==0){ cout<<"Error"<<"\n"; } if(n>0&&n<=9){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<i<<"x"<<j<<"="<<setw(2)<<i*j<<" "; } cout<<"\n"; } } } 二维数组定义 int a [3] [5]; 数组类型 数组名 行数 列数 int a[3][5] = {{1,2,3,4,5},{6,7,8,9,0},{1,3,5,7,9}} ; #include <iostream> using namespace std; 函数的定义（功能的实现） int main(){ 函数的调用（完成功能） } 功能 参数 返回值 功能：要封装什么功能（一般一个函数实现一个功能） 参数：实现这个功能需要提供什么数据 返回值：实现功能后拿回的结果数据 名称：函数定义 简介：函数的三要素 返回值类型 函数名（形式参数表）{ 函数体 //执行语句 return //结果 } 函数的返回值类型 函数名（XXXX）{ 函数要做的事情 return …； } int add(int a,int b){ int c = a + b; return c; } int main(){ int d = add(3,5); cout << d; //cout << add(3,5); }

篇幅较长警告……好像没那么长\TEXTCOLOR{YELLOW}{篇幅较长警告……好像没那么长}篇幅较长警告……好像没那么长 正如标题一样，我们这次的文章有些极限，我们要进行极限挑战，内容是——速通极限。 本文主要会介绍以下内容： · 什么是极限 · 左极限和右极限 · 极限的四则运算 · 三明治定理（夹逼定理） · 连续性 · 介值定理 1. 什么是极限 极限标准写法如下： lim⁡x→Af(x)=L\displaystyle\lim_{x\to A} f(x)=L x→Alim f(x)=L 就是说，当 xxx 越来越靠近于 AAA，f(x)f(x)f(x) 的值会越来越靠近于 LLL。 比如说，当你 f(x)=x2f(x)=x^2f(x)=x2，xxx 越来越接近 333 的时候，f(x)f(x)f(x) 的值会越来越靠近多少？毫无疑问是 999。所以，我们可以写成 lim⁡x→3x2=9\displaystyle\lim_{x\to3}x^2=9x→3lim x2=9。 当然，并不是代表我可以直接带入 f(A)f(A)f(A) 得到 LLL 的值。极限表示的只是一个趋势，有时候当 f(A)f(A)f(A) 没有意义的时候，LLL 的值也能够求出来，比如： lim⁡x→2x2−3x+2x−2\displaystyle\lim_{x\to2}\dfrac{x^2-3x+2}{x-2} x→2lim x−2x2−3x+2 当 x=2x=2x=2 的时候，分母为 000，直接带入明显是不行的。但是，仔细观察会发现你可以进行因式分解： lim⁡x→2x2−3x+2x−2=lim⁡x→2(x−1)(x−2)x−2=lim⁡x→2x−1=1\displaystyle\lim_{x\to2}\dfrac{x^2-3x+2}{x-2}=\lim_{x\to2}\dfrac{(x-1)(x-2)}{x-2}=\lim_{x\to2}x-1=1 x→2lim x−2x2−3x+2 =x→2lim x−2(x−1)(x−2) =x→2lim x−1=1 我们只是表示一个趋势，因此 xxx 会趋向于 222，但是没有取到 222！因此，我们因式分解后进行约分是合法的。最后，计算出结果为 111。 当心一点：虽然在极限中，f(x)=x2−3x+2x−2f(x)=\dfrac{x^2-3x+2}{x-2}f(x)=x−2x2−3x+2 以及 g(x)=x−1g(x)=x-1g(x)=x−1 计算的结果是一样的，但是不代表两个函数等价。判断函数是否相等，首先应当判断它的定义域是否相等。因为 D(f)=R∖{2}D(f)=R\setminus\{2\}D(f)=R∖{2}，而 D(g)=RD(g)=RD(g)=R，g(x)g(x)g(x) 函数的自变量是可以取到 222 的，而 f(x)f(x)f(x) 不行，但是在极限中，f(x)  ⟺  g(x)f(x)\iff g(x)f(x)⟺g(x)。 顺便一提，所谓极限 lim⁡\limlim，就是来自于英语中的 limitlimitlimit 一词。 2. 左极限和右极限 极限也有左右？当然有。 顾名思义，左极限=在函数左边的极限，右极限=在函数右边的极限。数学意义上，左极限即 x<Ax<Ax<A 时的极限，右极限即 x>Ax>Ax>A 时的极限。 举个例子：f(x)=1xf(x)=\dfrac{1}{x}f(x)=x1 ，求 x→0x\to0x→0 时的左极限和右极限。 左极限写作 lim⁡x→A−f(x)\displaystyle\lim_{x\to A^-}f(x)x→A−lim f(x)。我们可以举例子来看看什么是左极限： 当 x=−1x=-1x=−1 时，f(x)=−1f(x)=-1f(x)=−1 当 x=−12x=-\dfrac{1}{2}x=−21 时，f(x)=−2f(x)=-2f(x)=−2 当 x=−13x=-\dfrac{1}{3}x=−31 时，f(x)=−3f(x)=-3f(x)=−3 当 x=−15x=-\dfrac{1}{5}x=−51 时，f(x)=−5f(x)=-5f(x)=−5 …… 可以发现，当 xxx 越来越靠近 000 但还是满足 x<0x<0x<0 的时候，我们的 1x\dfrac{1}{x}x1 会越来越靠近于 −∞-\infty−∞。因此，我们可以写作： lim⁡x→0−1x=−∞\displaystyle\lim_{x\to0^-}\dfrac{1}{x}=-\infty x→0−lim x1 =−∞ 所以，它在 000 的右边带了个负号，代表它是负的，换言之就是小于 000 时的极限。同理适用于右极限。 右极限写作 lim⁡x→A+f(x)\displaystyle\lim_{x\to A^+}f(x)x→A+lim f(x)。我们依旧举例子来看看什么是右极限： 当 x=1x=1x=1 时，f(x)=1f(x)=1f(x)=1 当 x=12x=\dfrac{1}{2}x=21 时，f(x)=2f(x)=2f(x)=2 当 x=13x=\dfrac{1}{3}x=31 时，f(x)=3f(x)=3f(x)=3 当 x=15x=\dfrac{1}{5}x=51 时，f(x)=5f(x)=5f(x)=5 …… 可以发现，当 xxx 越来越靠近 000 但还是满足 x>0x>0x>0 的时候，我们的 1x\dfrac{1}{x}x1 会越来越靠近于 ∞\infty∞。因此，我们可以写作： lim⁡x→0+1x=∞\displaystyle\lim_{x\to0^+}\dfrac{1}{x}=\infty x→0+lim x1 =∞ 那么，左极限和右极限有什么用呢？我们可以看一看极限 lim⁡x→01x\displaystyle\lim_{x\to0}\dfrac{1}{x}x→0lim x1 的值。 当 x→0−x\to0^-x→0− 时，极限结果为 −∞-\infty−∞；当 x→0+x\to0^+x→0+ 时，极限结果为 ∞\infty∞。很明显，左极限和右极限是不同的。我们假设极限 lim⁡x−>Af(x)\displaystyle\lim_{x->A}f(x)x−>Alim f(x) 存在（设为 LLL），那么，当 x→A−x\to A^-x→A− 时，f(x)→Lf(x)\to Lf(x)→L，同理，当 x→A+x\to A^+x→A+ 时，f(x)→Lf(x)\to Lf(x)→L，即左极限和右极限相等。然而，这里，左极限和右极限完全不同，因此，这里极限不存在，记作： lim⁡x→01xDNE\displaystyle\lim_{x\to0}\dfrac{1}{x}DNE x→0lim x1 DNE 3. 极限的四则运算 你不用为 极限的四则运算 这个话题感到太担忧。相信你的直觉，如下！ lim⁡x→Af(x)=M,lim⁡x→Bg(x)=N\displaystyle\lim_{x\to A}f(x)=M,\lim_{x\to B}g(x)=Nx→Alim f(x)=M,x→Blim g(x)=N，那么： 对于极限的加法运算，有 lim⁡x→Af(x)+g(x)=M+N\displaystyle\lim_{x\to A}f(x)+g(x)=M+Nx→Alim f(x)+g(x)=M+N。 对于极限的减法运算，有 lim⁡x→Af(x)−g(x)=M−N\displaystyle\lim_{x\to A}f(x)-g(x)=M-Nx→Alim f(x)−g(x)=M−N。 对于极限的乘法运算，有 lim⁡x→Af(x)⋅g(x)=MN\displaystyle\lim_{x\to A}f(x)\cdot g(x)=MNx→Alim f(x)⋅g(x)=MN。 对于极限的除法运算，有 lim⁡x→Af(x)g(x)=MN\displaystyle\lim_{x\to A}\dfrac{f(x)}{g(x)}=\dfrac{M}{N}x→Alim g(x)f(x) =NM 。 4. 三明治定理（夹逼定理） 你可以随意在超市中看到三明治，可以随意在汉堡店中看到汉堡（这不废话吗 但是这很形象）。这两种物品都是由上下两层面包，中间一些“夹心”构成的。如果你知道，这个在“三明治”中的东西上面有一层面包，下面也有一层面包，那你可以迅速判断出这是其中的“夹心”，即使你很用力地把两片面包夹在一起，中间几乎没有空隙，但是中间“夹心”也在，而且也夹在了这个位置。这是理所当然的。 我们在生活中的判断技巧也可以利用在数学中。如果对于任意的 xxx 都有 g(x)≤f(x)≤h(x)g(x)\leq f(x)\leq h(x)g(x)≤f(x)≤h(x)，且当 lim⁡x→Ag(x)=lim⁡x→Ah(x)=L\displaystyle\lim_{x\to A}g(x)=\lim_{x\to A}h(x)=Lx→Alim g(x)=x→Alim h(x)=L，则： lim⁡x→Af(x)=L\displaystyle\lim_{x\to A}f(x)=L x→Alim f(x)=L 这个定理看上去朴素，实际上确实没那么豪华，但是证明第一重要极限的时候需要它。 5. 连续性 5.1. 在一点上连续 我们考虑两个函数： f(x)=x2−3x+2x−2f(x)=\dfrac{x^2-3x+2}{x-2}f(x)=x−2x2−3x+2 以及 g(x)=x−1g(x)=x-1g(x)=x−1 它们唯一的区别就在于定义域中包不包含 x=2x=2x=2，毋庸置疑。但是令人惊奇的是它们在 x=2x=2x=2 时的极限是一模一样的。 不难发现，lim⁡x→2f(x)=lim⁡x→2g(x)=1\displaystyle\lim_{x\to2}f(x)=\lim_{x\to2}g(x)=1x→2lim f(x)=x→2lim g(x)=1，这个已经在上文讨论过了。 但是我们直接带入 x=2x=2x=2 呢？不难发现 lim⁡x→2f(x)≠f(2)\displaystyle\lim_{x\to2}f(x)\neq f(2)x→2lim f(x)=f(2)，但是 lim⁡x→2g(x)=g(2)\displaystyle\lim_{x\to2}g(x)=g(2)x→2lim g(x)=g(2)。 更一般化的，有一类函数（假设下面的 h(x)h(x)h(x) 是其中之一），横坐标为一个特定常数 AAA 时，它的图像满足 lim⁡x→Ah(x)=h(A)\displaystyle\lim_{x\to A}h(x)=h(A)x→Alim h(x)=h(A)。这类函数的特点，就是在绘制其图像到 x=Ax=Ax=A 时，我们不用把笔从纸面上抬起再挪到 h(A)h(A)h(A) 处或者跳过 x=Ax=Ax=A 时的点，我们称之为 在 x=Ax=Ax=A 处连续。 5.2. 在一段区间上连续 让我们延续上面的定义。 很明显，这里和上面的区别就在于在区间上连续而非一点。 但我们不妨把区间看成一个个点——对于 ∀k∈[a,b]\forall k\in[a,b]∀k∈[a,b]，若 lim⁡x→kh(x)=h(k)\displaystyle\lim_{x\to k}h(x)=h(k)x→klim h(x)=h(k)，则称函数 h(x)h(x)h(x) 在 [a,b][a,b][a,b] 区间内连续。 换言之，你在绘制函数 h(x)h(x)h(x) 的 [a,b][a,b][a,b] 段时用不着抬笔。 6. 介值定理 最后，让我们以介值定理收尾。 我们已经了解了什么叫做连续，（说白了就是绘制图像时不用抬笔）那么在函数 f(x)f(x)f(x) 在区间 [a,b][a,b][a,b] 段内连续的前提下，如果 f(a)f(a)f(a) 到 f(b)f(b)f(b) 的区间中，值域在 [A,B][A,B][A,B] 区间内，对于 ∀K∈[A,B]\forall K\in[A,B]∀K∈[A,B]，必然 ∃k\exist k∃k 满足 f(k)=Kf(k)=Kf(k)=K。 证明：因为连续，所以满足，简单的想想都能够知道。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本文阅读与理解的难度较小，相比往期较容易理解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往期话题： 详解函数#1 幂函数、指数函数和对数函数 详解函数#2 三角函数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参考文献：《普林斯顿微积分》

测试点信息 #1 AC 0ms/3.34m #2 AC 0ms/3.16m #3 AC 1ms/3.09m #4 AC 1ms/3.13m #5 AC 0ms/3.23m #6 AC 1ms/3.25m #7 AC 0ms/3.36m #8 AC 0ms/3.15m #9 AC 0ms/3.28m #10 AC 0ms/3.34m #11 WA 0ms/3.31m #12 AC 0ms/3.32m #13 AC 0ms/3.36m #14 AC 0ms/3.36m #15 AC 0ms/3.35m #16 AC 0ms/3.31m #17 AC 1ms/3.16m #18 AC 0ms/3.36m

要发的文字\HUGE 要发的文字要发的文字

题目描述 你需要编写一个C++程序来模拟Minecraft中的简单世界生成。程序需要根据给定的种子值(seed)生成一个二维的方块世界，并输出该世界的俯视图。 世界由以下方块类型组成： 'G'：草方块 (Grass) 'D'：泥土 (Dirt) 'S'：沙子 (Sand) 'W'：水 (Water) 'B'：基岩 (Bedrock) 输入格式 第一行包含三个整数：世界宽度w(5≤w≤50)，世界高度h(5≤h≤50)和种子值s(0≤s≤1000) 第二行包含一个整数n(1≤n≤10)，表示要生成的层数 输出格式 输出生成的世界俯视图，一个h×w的字符矩阵 每行代表世界的一行，字符之间用空格分隔 说明/提示 世界生成规则： 最外层必须是基岩(B) 从外向内，第n层是水(W) 第n+1层是沙子(S) 第n+2层是泥土(D) 最内层是草方块(G) 如果层数超过世界尺寸，则从外向内依次填充 可以使用取模运算和种子值s来增加随机性，例如： 对于坐标(i,j)，可以使用(i*j+s)%5来决定是否替换默认方块类型 建议使用二维数组来存储世界数据 注意边界条件处理 代码： #include <iostream> #include <vector> #include <algorithm> using namespace std; char determineBlock(int distance, int n, int i, int j, int seed) { if (distance == 0) return 'B'; if (distance <= n) return 'W'; if (distance == n + 1) return 'S'; if (distance == n + 2) return 'D'; } void generateMinecraftWorld(int width, int height, int seed, int layers) { vector<vector<char>> world(height, vector<char>(width)); } int main() { int width, height, seed, layers; cin >> width >> height >> seed >> layers; } 输出： B B B B B B B B B B B W W W W W W W W B B W W W W W W W W B B W W W W W W W W B B W W W W W W W W B B W W W W W W W W B B W W W W W W W W B B B B B B B B B B B

老师在直播间里大声吐槽J组出题人阴：“真的太阴了，阴的没边”（可能有记错的，但是大体就是这样）

我的评价： * 明显 AI 码风这一块； * 完善程序还是我出的不错；至于简洁易懂的代码，我心里自然记得的； * 交互题玩上瘾了。

我和“奶龙”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1832397130290507776

我和“奶龙”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1832397130290507776

如梦令（其一） 上课十分枯燥，作业令人睡觉。写到十二点，题目还剩不少。不好，不好，老师又要咆哮。 如梦令（其二） 起床已经不早，早饭还没吃饱。系好红领巾，背一万斤书包。快跑，快跑，一定不能迟到。

* 君子喻于义，小人喻于利。所以既喻于义又喻于利的人，就是亦喻。 * 人有耻，则能有所不为。人无耻，则无所不能也。 * 多行不义，必自闭。 * 有朋自远方来，虽远必诛。 * 人有尺，则能有所不为。 翻译：人只有尺子，没有量角器，则有些事情做不了，比如画角。 * 孔子曰：打架用砖乎！不宜乱乎，照脸乎，使劲乎，乎不着，再乎，右手乎完左手乎，板砖乎断用鞋乎，既然乎，岂可一人独乎，有朋一起乎，不亦乐乎！乎着，往死里乎，乎不死再乎。你明乎，不眀乎？明乎则已，不明乎则拿砖照脸乎！一乎则明，如一乎不明，再一乎，搞定也。

是不是我的世界玩多了

https://www.acgo.cn/application/1849745109827825664

一.课堂案例一. 课堂案例一.课堂案例 T2 观星 T1. 二进制矩阵中的最短路 二.上节课作业二.上节课作业二.上节课作业 T1 填图颜色 T2. 被包围的区域