入门天花板

目录 树： 定义： 度（树有几个直系“儿子”）： 表示法： 双亲表示法（父亲表示法） 孩子表示法 二叉树： 定义： 满二叉树： 完全二叉树： 储存： 顺序存储法（完全二叉树）： 链式储存法： 二叉树的遍历： 先序遍历（根左右）： 以根(A)为分界，分成左右两部分(B,C)。先分左边,根(B)分两部分(D,E),再分右边,根(C)分两部分(F,G)。 中序遍历（左根右） 后序遍历（左右根） 总结： 目录

目录 FLOYD-WARSHALL（弗洛伊德算法）： 核心参考代码： 关系： 距离>1的是间接朋友，距离<1的没有关系，默认值为无穷大 背包问题： 01背包（最基础的背包问题）： 01背包特点： 01背包优化： 完全背包公式: 多重背包: 目录

DAY1 上午 第一课 算法入门 PART 1 算法的定义 PART 2 时间复杂度 PART 3 空间复杂度 PART 4 素数问题 1） 埃筛 原理：将所有不大于 n\sqrt{n}n  的所有质数的倍数剔除，剩下的自然数就是质数； 模板： 2） 线性筛 原理：每个非质数只被其最小的质因子对应的最大整数因子剔除 唯一分解定理历史 唯一分解定理数学解释 模板： DAY1 下午 第二课 STL模板 PART 1 VECTOR 常用成员函数： 函数名 作用 时间复杂度 val.push_back(data) 对val向后插入data O(1) val.pop_back(data) 删除尾数据 O(1) val.size() val内元素个数 O(1) val.clear() 清空val O(N) val.begin() 起始迭代器 / val.end() 末尾迭代器 / val.empty() 判空 / PART 2 SET 常用成员函数： 函数名 作用 时间复杂度 val.insert(data) 对val插入data O(log(N)) val.erase(it) 1.删除一个it迭代器所指的位置 O(1) val.erase(it) 2.删除值为it的数据 O(log(N)) val.erase(first,last) 3.删除迭代器于{last,first}的数据 O(last-first) val.size() val内元素个数 O(1) val.clear() 清空val O(N) val.begin() 起始迭代器 / val.end() 末尾迭代器 / val.find(data) 在val中寻找data O(log(N)) 模板 PART 3 MAP 常用成员函数： 函数名 作用 时间复杂度 mp.erase(it) 1.删除一个it迭代器所指的位置 O(1) mp.erase(it) 2.删除键为it的数据 O(log(N)) mp.erase(first,last) 3.删除迭代器于{last,first}的数据 O(last-first) mp.size() 键的个数 O(1) mp.clear() 清空 O(N) mp.begin() 起始迭代器 / mp.end() 末尾迭代器 / DAY2 上午 第三课课 前缀和与差分 PART 1 前缀和与区间和 PART 2 差分与区间修改 DAY2 下午 第四课 递归与递推 PART 1 递归 PART 2 递推 PART 3 例题 （1）平行线分割平面 （2）错排问题 DAY3 上午 第五课 贪心算法 PART 1 概念 PART 2 例题 活动排序 DAY3 下午 第六课 二分 PART 1 二分搜索 查找X PART 2 LOWER_BOUND AND UPPER_BOUND SORT 样例代码 DAY4 归并，快排和高精度 PART 1 归并排序 样例代码 PART 2 快速排序 PART 3 高精度算法 背景 加法 减法 乘法 ####除法 DAY5 上午 第九课 栈和队列 PART 1 栈 实验性代码[1] Part 2 队列 实验性代码 Part 3 前后中缀表达式 长度不够喽，第二部分在这里 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 实验性代码指通过代码可视化等手段来更好的发现问题，完成纠错等环节，在后面的笔记中还会有很多 ↩︎

上半部分跳转 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY5 下午 第十课 深度优先搜索 模板 DAY6 下午 第十二课 广度优先搜索 实验性代码 DAY7 上午 第十三课 树与二叉树 PART 1 背景 PART 2 树的存储 实验性代码（孩子表示法） PART 3 二叉树 二叉树的五大性质： 【性质 1】在二叉树的第 i 层上最多有 2^i − 1 个结点（i >= 1）。第 1 层最多 1 个结点，第 2 层最多 2 个结点，第 3 层最多 4 个结点…… 【性质 2】深度为 k 的二叉树至多有 2^k − 1 个结点（k >= 1） 【性质 3】任意一棵二叉树，若其叶子结点 (度为 0 结点) 的数量为 n0，度为 2 的结点数量为 n2，则：n0 与 n2 一定满足：n0 = n2 + 1 。 【性质 4】具有 n (n ≥ 0) 个结点的完全二叉树的深度为 ⌊log2⁡(n)⌋ + 1。⌊ ⌋ 表示下取整。 【性质 5】    若将一棵有 n 个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1，2，…，n，则： 1. 若结点编号 i = 1 ，则结点 i 为根，无父结点； 2. 若 i > 1 ，则 i 的父结点编号为 i / 2； 3. 针对编号为 i 的结点：        3.1 其左孩子编号为 2 * i (2 * i ≤ n) ；        3.2 其右孩子编号为 2 * i + 1 (2 * i + 1 ≤ n)； 二叉树的存储 二叉树的遍历 DAY7 下午 第十四课 图论 PART 1 图的定义与概念 PART 2 图的存储 邻接矩阵 样例代码 邻接表 PART 3 DIJKSTRA 最短路 实验性代码 DAY 8 上午 第15课 FLOYD最短路 例题 过关道具 记忆化搜索 最后一课放不下了，点击跳转第三部分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完结撒花 date 8.20

MARKDOWN 标题语法 要创建标题，请在单词或短语前面添加井号 (#) 。# 的数量代表了标题的级别。例如，添加三个 # 表示创建一个三级标题 (<h3>) (例如：### My Header)。 Markdown 语法 HTML语法 # 一级标题 <h1>一级标题</h1> ## 二级标题 <h2>二级标题</h2> ### 三级标题 <h3>三级标题</h3> #### 四级标题 <h4>四级标题</h4> ##### 五级标题 <h5>五级标题</h5> ###### 六级标题 <h6>六级标题</h6> 效果： 一级标题 二级标题 三级标题 四级标题 五级标题 六级标题 可选语法 还可以在文本下方添加任意数量的 == 号来标识一级标题，或者 -- 号来标识二级标题。 Markdown 语法 最佳实践 不同的 Markdown 应用程序处理 # 和标题之间的空格方式并不一致。为了兼容考虑，请用一个空格在 # 和标题之间进行分隔。 √请这样做 ×请不要这样做 # DO this #DON't do this

定义一个类： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 根据数组递归创建线段树： 使用以下方式构建一个线段树： 例如： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 查询区间和 : 使用以下方式查询区间和： 例如： 注意：0≤左边界≤右边界≤数组长度−10 ≤左边界≤右边界≤数组长度 - 10≤左边界≤右边界≤数组长度−1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 查询最小值 [1]: 使用以下方式查询最小值： 例如： 注意：0≤左边界≤右边界≤数组长度−10 ≤左边界≤右边界≤数组长度 - 10≤左边界≤右边界≤数组长度−1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 查询最大值 [2]: 使用以下方式查询最大值： 例如： 注意：0≤左边界≤右边界≤数组长度−10 ≤左边界≤右边界≤数组长度 - 10≤左边界≤右边界≤数组长度−1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 线段树的创建实例： 先输入元素个数N，然后输入N个元素。 例如： 线段树的查询实例： 先输入查询次数Q，后面Q行每次输入两个数L和R。 例如： 注意：0≤L≤R≤N−10 ≤L≤R≤N - 10≤L≤R≤N−1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 线段树实例： 几组测试数据： * 1 * 2 * 3 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 作者太蠢了，这个模块的代码有BUG ↩︎ 2. 作者太蠢了，这个模块的代码也有BUG ↩︎

众所周知，我们在ACGO上是没法用用户名搜人的，但是可以通过这个直接访问个人主页 首先，进入一个团队界面（必须有管理员，没有可以自建）： 然后，点击添加成员： 填入你想搜索的人的用户名： 找到你想要访问主页的用户 复制他后面的ID 最后，打开一个人的主页（随便一个人） 修改链接栏最后的数字为你复制的ID 按enter就可以访问了！

题解：

题解：

题解：

题解：

1.介绍 最简单的最短路径算法，时间复杂度为O(N^3) 2.核心代码

树与二叉树： 树：树是一种非线性的结构数据，是由n个节点组成的有限集合。 如果n==0时，称为空树，如果n>0，树有且仅有一个特定的节点——根节点。 树的度：节点拥有的子树的数量为节点的度，度为0的节点为叶子节点，度不为 0的节点为分支节点，树的度定义为树的所有节点中的最大值 树的前驱和后驱：除根节点没有前驱外，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点。节点的直接后继称为节点的孩子，节点的直接前驱为孩子的父亲。有同一个双亲的不同节点互称兄弟。 树中节点的层次：树中根节点为第1层，根的孩子为第2层，以此类推。树中节点的最大层次称为深度或高度。注意：部分题目中根的节点为第0层 除根节点没有父节点外，其余节点有且仅有一个父节点，n个节点的数，有且仅有n-1条边，数中任意两个节点之间有且仅有一条简单路径（路径上的节点都不相同的路径） 双亲表示法：从上到下，从左到右依次给每个点编号，记录的方式可以简单表示为：tree[i] = j 表示编号为i的树节点的父亲是j。 下标： 1 2 3 4 5 6 7 8 9 父节点下标： 0 1 1 2 3 3 4 4 4 孩子表示法：即每个节点存储自己孩子的位置信息。根据结构，可以选择使用vector进行存储。 核心代码： vector<int> tree[N]; tree[i].push_back(idx); 表示i节点是idx节点的双亲 下标 1 2 3 4 孩子下标： 2/3 4 5/6 7/8/9 二叉树：二叉树是一种度数最大为2的树形结构，即二叉树的每个节点最多有两个子节点，每个节点的子节点严格区分左节点和右节点，它的两颗子树称为左子树和右子树。 性质1： 在二叉树的第i层上最多右2的i-1次方个节点（i>=1）。 性质2： 深度为k的二叉树至多2的k次方-1个节点（k>=1）。 性质3： 任意一颗二叉树，若其叶子节子（度为1节点）的数量为n，度为2的节点数量为n2，则：与n2一定满足：n0=n2+1 性质4： 具有n个节点的完全二叉树的深度为[log2(n)]+1.[]表示下取整。 性质5： 若将一颗有n个节点的完全二叉树自上而下，同一层自左向右连续给节点编号1,2…，n，则： 1. 若节点编号i=1，则节点i为根，无父节点； 2. 若i>1，则i的父节点编号为i/2; 3. 针对编号i的节点： 3.1其左孩子编号为2i； 3.2其右孩子编号为2i+1； 满二叉树：指某一二叉树“子孙满堂”，即除叶子节点外，其他节点的度均为2，且每一层的节点总数最大值，这种特殊的状态的二叉树，称为满二叉树（即二叉树深k层共2的k次方-1个节点） 完全二叉树：若某一二叉树深k层，除第k层外，其他层的节点总数达到最大值，即第i（i<k）层节点点数为2的i-1次方。且第k层节点点数小于等于2的k-1次方并靠左侧连续，这种特殊状态的二叉树，称为完全二叉树。 二叉树的存储： 1. 顺序存储法：当二叉树节点较少，呈现完全二叉树时，以二叉树性质5为基础，用顺序数组来模拟二叉树。 核心代码： 2. 链式存储法：当二叉树节点较多，且并非具有完全二叉树时，为了避免可能在使用顺序存储时，导致的内存堆栈溢出则使用链式存储法 核心代码： 1. 先序遍历：根，左，右的深度优先搜索； 2. 中序遍历：左，根，右的深度优先搜索； 3. 后序遍历：左，右，根的深度优先搜索；