1.迷宫类问题（示例代码） 2.连通块问题（示例代码）

图 图 (Graph) 是由若干个给定的点、及若干条连接两个顶点的边所构成的图形，这种图像通常用来描述描述某些事物之间的某种特定的关系 图常用G(V,E)G(V, E)G(V,E)表示，VVV (Vertex) 为顶点集合， EEE (Edge) 为边集合 顶点的个数称为图的阶 图是图论的研究对象 图论这一部分的知识点，侧重图结构的描述、图结构的存储和遍历、少量剧本的图论算法的实现 分类 无向图：可以直接由某一状态回到前一个状态 有向图：不能直接由某一状态回到前一个状态，<a,c><a, c><a,c>和<c,a><c, a><c,a>为两条有向边 有向图的基图：忽略有向图所有边的方向， 得到的无向图称为该有向图的基图 完全图和有向完全图 完全图(Complete Graph)：无向图中任何一对顶点之间都有一条边 一个nnn阶的完全图有n∗(n−1)2\frac{n * (n - 1)}{2}2n∗(n−1) 条边 有向完全图(Directed Complete Graph)：有向图中任何一对顶点之间都有两条有向边 稀疏图和稠密图 稀疏图：边的数目相对较少(远小于n∗(n−1)n * (n - 1)n∗(n−1)) 稠密图：边的数目相对较多(接近于完全图或者完全有向图) 平凡图和零图 平凡图：只有一个顶点的图 零图：没有边的图 自环和重边 自环：一个顶点 重边：两个顶点有多条边 权 带权图(Weighted Graph)：边上带有权值的图 权：可以抽象的理解为金钱、时间、长度 简单图和多重图 简单图(Simple Graph)：一种无向图或有向图， 其中不存在自环和重边 多重图(Multi Graph)：一种无向图或有向图， 其中存在自环和重边 连通 路径：在图G(V,E)G(V, E)G(V,E)中， 从顶点vvv出发， 沿着一些边经过顶点vp1,vp2,vp3,...v_{p1}, v_{p2}, v_{p3}, ...vp1 ,vp2 ,vp3 ,... 到达顶点vjv_{j}vj ， 则称顶点序列(vi,vp1,vp2,vp3,...,vj)(v_i, v_{p1}, v_{p2}, v_{p3}, ... , v_j)(vi ,vp1 ,vp2 ,vp3 ,...,vj ) 连通：若从顶点uuu到vvv有路径， 则称顶点uuu和vvv是连通的 连通图：如果无向图中任意一对顶点都是连通的，则称此图为连通图 强连通图：如果有向图中，若每一对顶点uuu和vvv， 即存在uuu到vvv的路径，也存在vvv到uuu的路径，则称此图为强连通图 度 * 图中顶点的度：与该顶点相连的边的数量 * 在无向图中，一个顶点的度数就是和该顶点相连的边的数量 * 在有向图中，一个顶点的度数就是该顶点的入度和出度的和。（入度就是指向该的的边的数量，出度是从该顶点出发的边的数量） 图/树 树(Tree)：如果一个无向连通图中不存在回路，则称这种图为树 树是一种特殊的图 树也可以从数据结构的角度去定义，涉及的术语有 子树、孩子结点、度、层次 树作为一种非线性的数据结构，是由n(n≥0)n(n\ge 0)n(n≥0)个结点组成的有限集合 如果n==0n==0n==0时，称为空树，如果n>0n > 0n>0，树有且只有一个特点的结点——根节点(root) 度：结点拥有的子树的数量为结点的度，度为000的结点为叶子结点，度不为000的结点为分支结点 树的前驱和后继：除根结点没有前驱外，其余结点都有唯一的一个前驱结点。每个结点可以有000个或多个后继结点。结点的直接后继称为结点的孩子，结点的直接前驱称为结点的父亲 树中结点的层次：书中根节点为第一111层，根节点的孩子为第二222层，以此类推。书中结点的最大层次称为树的深度(高度) 注意：部分题目中的根节点为第000层 C++建树 求树直径(距离最远的两个点) bfs与dfs模板 二叉树 二叉树(Binary Tree) 是一种度数最大为222的树，即二叉树的每个结点最多有两个子节点，每个子节点分别称为左子树、右子树 链也是一种树 一颗深度为kkk且有2k−12^k - 12k−1个结点的二叉树称为满二叉树 若二叉树的高度为kkk，则共有kkk层，除第kkk层外，其他各层111~(k−1)(k - 1)(k−1)的结点数都达到最大个数，且第kkk层缺少的结点是从左到右并连续的，这就是完全二叉树 对任意一颗二叉树，如果其叶子结点的数量为n0n_0n0 ，度为2的结点数为n2n_2n2 ，则一定满足n0=n2+1n_0 = n_2 + 1n0 =n2 +1 证明：1、n=n0+n1+n2n = n_0 + n_1 + n_2n=n0 +n1 +n2 。2、孩子结点有n1+2n2n_1 + 2n_2n1 +2n2 ，所以n=n1+2n2+1n = n_1 + 2n_2 + 1n=n1 +2n2 +1。由此可得n0=n2+1n_0 = n_2 + 1n0 =n2 +1 具有n(n≥0)n (n \ge 0)n(n≥0)个结点的完全二叉树的深度为⌊log⁡2n⌋+1\lfloor \log_{2}{n} \rfloor + 1⌊log2 n⌋+1(⌊⌋\lfloor \rfloor⌊⌋是向下取整) 如将一颗具有nnn个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,...,n1, 2, ..., n1,2,...,n，则有以下关系： 1. 若i=1i = 1i=1，则结点iii为根，无父结点 2. 若i>1i > 1i>1，则iii的父结点编号为⌊i/2⌋\lfloor i / 2 \rfloor⌊i/2⌋ 3. 若2∗i>n2 * i > n2∗i>n，则iii无左孩子，否则其左孩子编号为2∗i2 * i2∗i 4. 若2∗i+1>n2 * i + 1 > n2∗i+1>n，则iii无右孩子，否则其右孩子编号为2∗i+12 * i + 12∗i+1 二叉搜索树 二叉搜索树(Binary Search Tree) 是一种应用十分广泛的二叉树 二叉搜索树具有的性质： 1. 若左子树不空，则左子树上所有的结点的值均小于它根结点的值 2. 若右子树不空，则右子树上所有的结点的值均大于它根结点的值 3. 左，右子树也是一个二叉搜索树 满A叉树结点 f[k]=20+21+......+2(k−1)f[k] = 2^0 + 2^1 + ...... + 2^(k- 1)f[k]=20+21+......+2(k−1) 2∗f[k]=21+22+......+2(k−1)2 * f[k] = 2^1 + 2^2 + ...... + 2^(k- 1)2∗f[k]=21+22+......+2(k−1) 2∗f[k]−f[k]=2k−202 * f[k] - f[k] = 2^k - 2^02∗f[k]−f[k]=2k−20 f[a]=(ak−1)/(a−1)f[a] = (a^k - 1) / (a - 1)f[a]=(ak−1)/(a−1)

#include<bits/stdc++.h> #include<iostream> using namespace std; int isp(int n) { int sum=1; while (n > 0){ sum=n*sum; n--; } return sum; } int main(){ int n; cin>>n; cout<<isp(n); return 0; }

,,,

https://www.acgo.cn/contest/2204/detail?matchRoundId=2204&examId=40534&teamCode=1793944541884059648&openLevel=2

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

https://www.acgo.cn/contest/2026/detail?matchRoundId=2026&examId=39081&teamCode=1661232050350374912&openLevel=2 邀请码：SHAi

4. 游戏的规则是，在你和小码君面前有 N 个数，同时将给出一个数 C ,要求你和小码君在这组数内找到两个数，满足 A−B=C 。找出的数对越多，你们的排名越高。 为了计算赢得比赛的可能性，你们打算先计算出所有满足此条件的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入格式 第一行包含两个正整数 N 和 C 。 接下来的一行包含 N 个正整数，表示你将在这 N 个数中找数对。 输出格式 共一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。 样例组 输入#1 复制 4 1 1 1 2 3 输出#1 复制 3 提示说明 对于 75% 的数据，1 ≤ N ≤ 2000。 对于 100% 的数据，1 ≤ N ≤ 2×10 5 ，0 ≤ a i ≤ 2 30 , 1 ≤ C ≤ 2 30 。 样例解释： 4 个数，分别为 1 1 2 3，总共有 3 对 A-B 的值等于 1。 这三对分别为 2-1、2-1、3-2（不同位置的数字一样的数对算不同的数对）

倒计时 倒计时

1.想要投稿超难50题的人可以关注@阿墨（创题）在自己的个人题单里创建名为”稿超难50题“的题单把需要投稿的题目放入题单里@阿墨（创题）每周日查看。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 嗯嗯嗯额-_-

1.想要投稿超难50题的人可以关注@阿墨（创题）在自己的个人题单里创建名为”稿超难50题“的题单把需要投稿的题目放入题单里@阿墨（创题）每周日查看。 2..想要挑战超难50题的人可以关注@阿墨（创题）在他的个人题单挑战。

AC - Accepted（答案正确） WA - Wrong Answer（答案错误） TLE - Time Limit Exceeded（超出时间限制） RE - Runtime Error（运行时错误） CE - Compilation Error（编译错误） MLE - Memory Limit Exceeded（超出内存限制） OLE - Output Limit Exceeded（输出限制超出） PE - Presentation Error（格式错误）

创超难题，选中的超难题可加入超难50题 ，欢迎加入 加入链接： https://www.acgo.cn/application/1793981382078676992

全部给我AC传送门（点击）

STL库 包含很多数据结构，可以节省手搓的时间直接用： vector: 动态数组 queue: 队列 priority_queue: 优先队列 deque: 双向队列 set: 有序集合 multiset: 有序集合，但允许相同的元素 unordered_set: 无序集合 map: 字典，以键值对的方式储存数据 unordered_map: 无序的字典，通过哈希实现 bitset: 一种二进制数据结构，常用于加速位运算 倍增 一种基于指数增长模式的算法设计技术 典型例题：求a^b % (1e9+7), a<=1e9, b<=1e9 模板： ST表 一种用于解决区间最小/最大值的数据结构 模板： 矩阵快速幂 矩阵作为倍增的对象 矩阵类乘法的实现： 可以用来加速一些递推方程的计算，例如： 斐波那契数列的地推方程可以表示为：f[n]=f[n-1]+f[n-2] 使用矩阵可以表示为： [Fn+1Fn]=[1110]n⋅[11]\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix} [Fn+1 Fn ]=[11 10 ]n⋅[11 ] 其中 FnF_nFn 表示第 n 个Fibonacci数。 并查集 一种处理不相交集合的数据结构和算法 模板：

图 图是若干个给定的顶点，以及若干条连接两个顶点的边所构成的图形。这种图形通常用来描述 常用G(V,E)G(V,E)G(V,E)表示。某些事物之间的某种特定关系，用顶点代表事物，用连接两个顶点的边表示相应两个事物具有某种关系。 VVV为顶点集合，EEE为边集合。 图是图论的研究对象 顶点的个数叫做图的阶 相关定义 * 有向图的基图：忽略有向图所有边的方向得到的无向图 * 完全图：无向图中任何一对顶点之间都有一条边 * 有向完全图：有向图中任何一对顶点u和v都存在<u,v><v,u>两条有向边 * 稀疏图：边的数目相对少（远小于n(n−1)n(n-1)n(n−1)) * 稠密图：边的数目相对多（接近于完全图或有向完全图） * 平凡图：只有一个顶点的图 * 零图：边集合为空的图 * 自环：一个顶点连接到自身的边 * 重边：两个顶点之间有多条边 * 权值图：边带有全权值的图 * 简单图： 一种无向图或有向图，其中不存在自环与重边 * 多重图：一种无向图或有向图，其中存在自环与重边 * 路径：在图G(V,E)中从顶点viv_ivi 出发，沿着一些边经过一些顶点viv_ivi ,vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,vp3v_{p3}vp3 ,……,vpmv_{pm}vpm 到达顶点vjv_jvj ，则称顶点序列{viv_ivi ,vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,vp3v_{p3}vp3 ,……,vpmv_{pm}vpm ,vjv_jvj }为viv_ivi 到vjv_jvj 的一条路径 * 联通：若从顶点u至v有路径，则称顶点u，v是联通的 * 如果无向图中任意一对顶点都是连通的，则称此图为连通图 * 如果有向图中任意一对顶点都是互相连通的，则称此图为强连通图 树 * 树：一个不存在回路无相连通图 * 树是一种特殊的图 * 树是一种非线性的数据结构，是由n(n≥0)n(n\ge 0)n(n≥0)个节点组成的有限集合 当n==0n==0n==0时，称为空树；如果n>0n>0n>0，树有且只有一个根节点 * 树的前驱与后继：除根节点没有前驱外，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点 * 节点的后继称为节点的的孩子，节点的之家前驱称为节点的父亲，有同一个父节点的不同节点互称兄弟 * 结点拥有的子树的数量叫做节点的度 树中节点的层次：树中根节点为第一层，根节点的孩子为第二层，以此类推…… 树中节点最大层次乘坐是的高度。 注意：有些题中根节点是第0层 树的存储 父亲表示法： 孩子表示法 特殊的树 二叉树（BT） 度数最大为2的树，即二叉树的节点最多有两个子节点，每个子节点分别被称为左孩子节点、右孩子节点， 每个子树分别被称为左子树、右子树 满二叉树：一棵深度为kkk且有2k+12^{k+1}2k+1个节点的二叉树 完全二叉树：若二叉树的高度为kkk，则共有kkk层，除第kkk层外，其他各层(1(1(1到(k−1))(k-1))(k−1))的节点数都达到最大个数， 且kkk层缺少的节点是从左到右并连续的，则称其为完全二叉树 二叉搜索树（BST） 二叉搜索树具有以下性质： * 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。 * 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。 * 任意结点的左、右子树也分别为二叉搜索树。