题解：

题解：

题解：

题解：

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. 后序遍历：左，右，根的深度优先搜索；

X02 C3 广深 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1,树的深度：树中节点的最大层数即树的高度或深度 2,节点的度，一个节点拥有的子树数 3,叶子节点:度为0的节点 满二叉树：所有层的节点数都达到最大 完全二叉树：除最后一层不满外，其余层的都达到该层的最大节点数，最后如果不满，该层所有节点都全部靠左排 二叉树三种遍历方式： 前序遍历：先遍历根节点，再遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，再遍历根节点，最后遍历右节点 后序遍历：先遍历左节点，再遍历右节点，最后遍历根节点 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.n个节点的二叉树一共有(2n)!/ (n!* (n+1)!) 种 2.n层二叉树的第n层最多为2^(n-1)个 3.二叉树节点计算公式N=n0+n1+n2,度为0的叶子节点比度为2的节点数多一个。N=1n1+2n2+1 4.对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1 5.具有n个节点的完全二叉树的深度为log2(n)+1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下午写的连通图+广搜的T2091 题解带注释详解

不会很难 传送门 手写 贴代码

由@意大利西兰花上课 手打，@意大利西兰花上课 手打，@意大利西兰花上课 手打 树的定义 树的度：结点拥有的子树的数量为结点的度，度为0的结点为叶子结点，度不为0的结点为分支节点，树的度定义为树的所有结点中度的最大值。 注意：n个结点的树，有且只有n-1条边 二叉树 二叉树是一种度数最大为2的树形结构，即二叉树的每个结点，每个结点的字结点严格区分左结点和右结点，它的两棵子树成为左子树、右子树。 完全二叉树 若某一二叉树深k层外，其他层的结点总数达到最大值，即第i（i<k）层结点为2的i-1。且第k层结点树小于第2的k-1并靠左侧连续，这种特殊形态的二叉树，称之为完全二叉树。 性质： —性质1： 在二叉树的第i层上最多有2的i-1个结点（i>=1）。第1层最多1个结点，第二层最多两个结点，第3层最多4个结点… —性质2： 深度为k的二叉树至多有(2的k) -1个结点（k>=1) —性质3： 任意一颗二叉树，若其叶子结点的数量为n的0，度为2的结点数量为n的2，则：n的0与n的2一定满足n的0=n的2+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)

第13课 PPT： 1）树的基本概念，以及遍历的方式 【了解】 （1）定义 （2）基本术语 【概念掌握】 结点，度，一棵树的度 双亲，孩子 子孙，祖宗 分支节点（内部结点，非终端结点），叶子节点（终端结点） 深度，高度，层次 有序树，无序树

传送门 似乎不能AC

加密算法： 解密算法： 使用说明： * 将需要加密的TXT文件名改为INPUT.TXT，运行程序，密钥为4位，加密完成后会在生成另一个TXT文件ENCRYPTED_OUTPUT.TXT为加密后的文件。 * 将需要解密的TXT文件名改为ENCRYPTED_OUTPUT.TXT，运行程序，密钥为4位（务必与加密的密钥相同！），加密完成后会在生成另一个TXT文件DECRYPTED_OUTPUT.TXT为解密后的文件。 * 密钥可以包含：数字，字母，英文字符（如：1AS2 、3M!1、432@等等）

刷题是一种出路，枚举是一种思想。 打表是一种勇气，搜索是一种信仰 剪枝是一种精神，骗分是一种日常 爆零是一种宿命，WA是一种绝望 TLE是一种痛苦，RE是一种放弃 UKE是一种无奈，AC是一种原谅 AK是一种幻想，弃赛是一种颓废 吊打是一种必然，进队是一种奢望 数学上来先打表，ＤＰ一般看规律 组合数学靠运气，计算几何瞎暴力 图论强行套模板，数论只会ＧＣＤ 递归递推伤不起，搜索茫然ＴＬＥ 分治做得像枚举，暴力枚举数第一 数据结构干瞪眼，怒刷水题找信心 涨姿势也不容易，考试一来全懵逼 暴力出奇迹，骗分过样例。 数学先打表，ＤＰ看运气。 穷举ＴＬＥ，递推ＵＫＥ。 模拟ＭＬＥ，贪心还ＣＥ。 想要骗到分，就要有方法。 图论背模板，数论背公式。 动规背方程，高精背代码。 如果都没背，干脆输样例。 北冥有鱼，其名为鲲，鲲之大，__int128存不下。 化而为鸟，其名为鹏，鹏之大，压位高精会爆炸。