由于帖主作为你 GO 最区的区,连 DFS 、树和图都忘光了,导致很多题目都不会,所以帖主发布了一个复习笔记
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
搜索优化:剪枝
* 将一些中途发现已经不可能的情况直接跳过
看题
P2089
看我炒鸡打卤
你姑没有这道题手写一下题目咪
题目描述
你将得到一个正整数 nnn ,请列出把正整数 nnn 划分为 kkk 个正整数的每一种方法
输入格式
输入共 1 行:第 1 行,2 个正整数 n,kn,kn,k
输出格式
输出为若干行:每行为空格隔开的若干个正整数,为一种 nnn 划为 kkk 个数的方法,每组数按从小到大的顺序输出。若两种方法中前 kkk 个数相同,则第 kkk 个数更小的排在前面
数据范围不知道
似乎对了?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
搜索优化:记忆化搜索
* 将一些多次出现的内容储存起来
* 避免重复计算造成的时间浪费
依旧手写题目:
给出自然数 nnn ,要求按如下方式构造数列
1.只有一个数字 nnn 的数列是一个合法的数列
2.在一个合法的数列末尾加入一个自然数,但是这个自然数不能超过该数列最后一项的一半,可以得到一个新的合法数列
请你求出,一共有多少个合法数列两个合法数列 a,ba,ba,b 不同当且仅当两数列长度不同或存在一个正整数 i≤∣a∣i \le |a|i≤∣a∣ ,使得 ai≠bia_i≠b_iai =bi
输入格式
输入一个整数,表示 nnn
输出格式
输出一个整数,表示合法是数列个数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树的基本概念(不是我咋还要写这个,我还是太区了)
* 结点:每个元素
* 边:结点之间的关系
* 父结点:直接位于某节点上方、作为其前件的节点,就是该节点的父结点
* 子结点:直接位于某节点下方、作为其后件的节点,就是该节点的子结点
* 祖先:父结点的父结点的……
* 兄弟结点:同一个父结点的结点
* 根结点:没有父结点的结点
* 叶结点:没有子结点的结点
* 子树:树中某个结点,加上它的所有后代结点共同构成的树结构,该结点就是这棵子树的根结点
* 结点的度:结点拥有子结点的数量
* 叶结点:度为 000 的结点
* 分支结点:度不为 000 的结点
* 树的度:所有结点中度的最大值
* 层次:根结点为第一层,其余结点的层次为父结点的层次+1
* 树的高度/深度:结点的最大层次
* 森林:若干棵互不相交的树
二叉树的定义
* 度为 222 的树,即每个结点最多有两个子结点
看题
不是怎么今天网课上的课你姑都没题目
有一个 nnn 个结点(n≤106n \le 10^6n≤106)的二叉树。给出每个结点的两个子结点编号(均不超过 nnn ),建立一棵二叉树(根结点编号为 111 ),如果是叶子结点,则输入 0 0
建好这棵二叉树后,求出它的深度
输入格式
第一行一个整数 nnn ,表示结点数
之后 nnn 行,第 iii 行两个整数 li,ril_i,r_ili ,ri ,分别表示结点 iii 的左右子结点编号。若 li=0l_i=0li =0 则表示没有左子结点,ri=0r_i=0ri =0 同理
输出格式
一个整数,表示这棵二叉树的深度
树的遍历(怎么这个我也要写,我实在是太区了)
先序遍历:根左右
中序遍历:左根右 中序遍历的二叉树实际上可以看作 二叉树.zip
后序遍历:左右根
层次遍历:从根结点往下开始遍历每一次,顺序为从左到右
如下图
该二叉树各个遍历:
先序遍历:ABDECF
中序遍历:DBEACF
后序遍历:DEBFCA
层次遍历:ABCDEF
代码实现即为 DFS 一个一个遍历,懒得写了
图(怎么这个我还要写,我真的实在是太区了)
* 点和边连起来的就叫做图,是一种复杂的非线性数据结构
* 定义为:graph=(V,E)graph=(V,E)graph=(V,E)
VVV 是一个非空有限集合,代表顶点(结点),EEE 代表边的集合
* 结点的入度:有向图中以这个结点为终点的有向边的数量
* 结点的出度:为起点
* 结点的度:入度数量+出度数量
* 权值:边的属性,可以理解为长度、费用等
* 连通:两个结点可以通过若干条边到达
* 回路/环:起点和终点相同的路径
* 简单图:没有重边和自环的图
* 连通图:所有结点都连通的无向图
* 强连通图:所有结点都连通的有向图
* 完全图:边数最大的简单有向/无向图
有向图:n×(n−1)n \times (n-1)n×(n−1) 条边
无向图:n×(n−1)÷2n \times (n-1) \div 2n×(n−1)÷2 条边
(nnn 为点的数量)
图的存储
二维数组邻接矩阵存储
定义 int g[n+15][n+15] ,其中 g[i][j] 表示从点 i 到点 j 的边的权值
g[i][j]={1或权值vi到vj之间有边0或∞vi到vj之间无边g[i][j]= \begin{cases} 1 或权值 &v_i 到 v_j 之间有边 \\0或 \infty &v_i 到 v_j 之间无边\end{cases}g[i][j]={1或权值0或∞ vi 到vj 之间有边vi 到vj 之间无边
邻接表
用 vector 存储图
看题
懒得打字了凑合着看吧