二叉树
对于任意一棵二叉树，满足度数为 \(2\) 的节点数是度数为叶子数量减 \(1\)。
一棵度数为 \(k\) 的树，设度数为 \(1,2,3\dots\) 的节点数分别为 \(w_1,w_2,w_3\dots\) 该树节点数为 \(\sum\limits_{i-1}^k w_i\times i + 1\)。原理：一棵树的节点数量 \(n\) 等于所有儿子数量 \(+1\)，即只有 root 不能作为儿子。且儿子的统计显然不会重复。
例1：一棵度数为 \(3\) 的树 \(T\) 有 \(3\) 个度数为 \(1\) 的节点，\(2\) 个度数为 \(2\) 的节点，\(3\) 个度数为 \(3\) 的节点，求叶子数量。
题目给的度数挺全，可以求出 \(n=3\times 1+2\times 2+3\times 3+1=17\)。
然后叶子即为 \(n-(3+2+3)=9\)。
例2：一棵二叉树有 \(2024\) 个节点，且拥有一个孩子的节点多于叶子，则拥有两个孩子的节点至多有多少个。
显然我们要依据题目限制列不等式求解。本题限制为“拥有一个孩子的节点多于叶子”。设有两个儿子的节点个数为 \(a\)，则叶子个数为 \(a+1\)。显然满足如下关系。
\[2024-a-(a+1)>a+1 \]解得 \(a<674\)。即 \(a\) 最大取 \(673\)。
二叉树前序，中序，后序遍历问题。
-
概念
- 前序:左中右
- 中序:中左右
- 后序:左右中
-
前序，中序，后序确定二叉树问题。
方法：中序定根，前序后序定左右。因此，给定中序，再给前序或后序是可以确定一棵唯一的二叉树的看，仅给定前序和后序是非法的。
数学相关
对数换底公式：\(\log_b^N=\dfrac{\log_a^N}{\log_a^b}\)。
例如，\(\log N=\dfrac{\log_2^N}{\log 2}\)。（\(\log\) 默认以 \(10\) 为底。）这是以 \(10\) 为底的 \(\log\) 和以 \(2\) 为底的 \(\log\) 转化。常考于倍增上界问题。
进制转换。
常考的有二进制，十进制，十六进制，八进制。
\(n\) 进制转十进制：考虑进制意义。例如，十进制数 \(114514=1\times 10^5+1\times 10^4+4\times 10^3+5\times 10^2+1\times 10^1+4\times 10^0\)。
十进制转 \(n\) 进制：不断除以 \(n\)，直到商为 \(0\)，倒序取余数。
对于小数部分，不断将小数部分乘 \(n\)，正序取整数，直到小数部分为 \(0\)。
特殊的，二进制转十六进制:从右往左取，每四位二进制转换成十进制，再转换成对应的六进制（如十进制下 \(11\) 为十六进制下 B）。
理论
紧急插播一张图片。
CPU 访问速度排序：寄存器 > 高速缓存（cache）> 内存 > 外存
WAN （Wide Area Network）:广域网（外网），是连接了多个 LAN 或者其他网络的大型计算机网络。
LAN：局域网。
BIOS 全称是 计算机基本输入输出系统。装在 ROM 上。不可修改。
用来全面管理计算机硬件和软件资源的软件是操作系统。
在操作系统中，“中断”指硬件或软件发送信号来打断当前执行的程序，以响应事件或进行任务调度。
计算机内部用来传送，存储，加工处理的数据或指令是以二进制进行，但不一定是机器码。
最早的 CPU 是由 Intel 发明的。
注意一些进制的前缀，0x 是十六进制，0 是八进制。0b是二进制。然后就能写一些奇怪的东西：
\(1+01\) 是十进制的 \(1\) + 八进制的 \(1\)，答案是 \(2\)。
\(0x10+01\) 是十六进制转十进制的 \(16\) + 八进制转十进制的 \(1\) = \(17\)。
需要注意的是，计算机输出是在十进制意义下的。
计算机系统内最小信息单位是 Bit。满足 \(8\) Bit = \(1\) Byte。
RAM 是易失性存储器，断电后数据会丢失。而 ROM 是只读性存储器，数据是永久的，不可修改。
四进制数转 \(16\) 进制。四进制的相邻两位可以转换成十六进制。
将 unsigned x 的高 \(16\) 位和低 \(16\) 位交换：(x<<16)|(x>>16)。
x<<16 是 \(x\) 的高十六位，其余位置是 \(0\)，x>>16 是 \(x\) 的低 \(16\) 位，其余位置是 \(0\)。位运算相关内容需要再看。
bmp 格式图片占用空间规则：
- 24 位，32 位的 bmp 文件不包含调色板，而调色板需要 \(4\times 2^n\) Byte。
若不包含文件头。bmp 文件大小 = width * height * n/8 （\(n\) 为位数，\(8\) 为位深。）
因此，\(2560\times 1440\) 的 \(32\) 位彩色照片，采用 bmp 格式存储，占用的空间大小为 \(2560\times 1440\times 32\div 8\div 1024\div 1024=14.1 \operatorname{Mib}\)。
Linux 命令相关
-
mkdir创建文件夹。 -
touch创建文件。 -
ls显示目录。 -
mv移动或重命名文件夹和目录。 -
cat连接一个或多个 <文件> 并输出到标准输出。 -
vi是编辑命令，会调出 vim，more是分页显示，cat是普通显示，ls是显示文件和文件夹。
gdb 里面不进入函数的单步执行语句是 next 或 n，进入函数的单步执行语句是 step 或 s，breakpoint 或 b 是设置断点，continue 或 c 是继续执行语句。
real 算上了用户交互时间，user + sys 是程序实际执行时间。
显然 real 不一定等于 user + sys
基础 ds
双向链表删除，查找一个元素是 \(O(n)\) 的。但插入，删除一个元素是 \(O(1)\) 的。
单向链表：只能一个方向遍历
双向链表：既可以倒着扫，也可以正着扫。
循环链表：最后一个节点指向第一个节点。
链表不必事先估计空间，插入删除不需要移动元素，所需空间与线性表长度成正比。
还有一个考法是链表操作。例如
选 A。
按照题意模拟即可。不能选 B，会覆盖原来 head 的值。
一般的，我们认为链表不支持随机访问。
注意到栈要求 “先进后出”，而队列要求“先进先出”。二者恰好相反。我们可以用两个 stack 模拟队列，具体的，开两个stack \(s_1,s_2\)，每次入队时，将元素压入 \(s_1\)，出队时将 \(s_1\) 内所有元素弹出并压入 \(s_2\)。按要求弹出 \(s_2\) 内元素即可。
需要注意的是，\(s_2\) 为空时，方可从 \(s_1\) 中新压入元素。这是因为原 \(s_2\) 中元素优先级全部比新元素高。若提前压入会破坏优先级。
这玩意复杂度是很劣的，入队复杂度 \(O(1)\)，但出队复杂度为 \(O(n)\)。
链表问题。
分为单向链表和双向链表，为了节约空间，还有循环链表。
- 定义
例：
struct Node
{
int val;
Node *pre;
Node *nxt;
};
上述代码定义了一个双向链表。\(val\) 存储了当前节点元素值，指针 pre 和 nxt 分别指向前驱和后继的 地址。
单向链表的定义仅需在此基础上删除前驱即可。
循环链表：尾节点的 nxt 指向链头。是一种单向链表，从任意一个节点出发均可遍历所有节点。
链表的遍历是 \(O(n)\) 的，但可很方便进行删除节点，添加节点操作，一般不支持随机访问。
考点：链表基本操作（插入，删除）
例：双向链表有一个两个指针域，llink 和 rlink。分别指向前驱和后继。现有指针 p 指向链表中的一个节点，q 指向一待插入节点。要求在 p 前插入 q，写出正确操作。
Solution
p->link->rlink=ql;q->rlink=p;q->link=p->link;p->link=q;
在纸上画出链表示意图即可解题。还会考察链表的删除，很简单。
邻接表存图法指
constexpr int N = 1000010;
vector <int> Edge[N];
int u,v;
cin>>u>>v;
Edge[u].push_back(v);
Edge[v].push_back(u);
当然拿链表写也是可以的。
而邻接矩阵一般指
constexpr int N = 1010;
int m[N][N];
int u,v,w;
cin>>u>>v>>w;
m[u][v] = w,m[v][u] = w;
而这样的
constexpr int N = 1000010;
struct Node
{
int u,v,w;
};
vector <Node> Edge;
int u,v,w;
cin>>u>>v>>w;
Edge.push_back({u,v,w});
即 kruskal 给边排序时存边方式，既不是邻接表也不是邻接矩阵。同理，用结构体也是一样的。
哈夫曼树
这是一种字符串编码方式。该编码方式保证了 任意字符编码不是另一个编码的前缀，即不会产生歧义，且所有字符的编码拼起来后长度最小。
具体的，我们将所有字符的 出现频率 扔到一个大根堆里，每次取出堆里最小的两个元素 \(u,v\)，将二者与新节点连边，且新节点点权为 \(u+v\)，最后将 \(u+v\) 扔回大根堆。
哈夫曼树是一棵二叉树，且不存在儿子个数为 \(1\) 的节点。原因显然，除了叶子，每个节点都是由两个节点“合并”得到的。
常考形式包括但不限于给定每个字符及其出现频率，求哈夫曼编码；利用哈夫曼树解决问题。甚至阅读程序/完善程序可能出哈夫曼树板子或相关内容，若不了解哈夫曼树模拟会很困难，几乎不可做。
例题： 现有一份仅包含 \(1000\) 个英文小写字母的文件，使用哈夫曼编码方式对英文小写字母进行不定长二进制编码，发现字母 e 的编码长度为 \(1\)。那么在这份文件中，e 至少出现几次？
A. 39 B. 334 C. 500 D. 501
e 的哈夫曼编码长度为 \(1\) 表明 e 是最后合并的。即 e “直属” root。哈夫曼树构造的本质是若干棵哈夫曼树的不断合并（初始化每个字符独立成树）。设最后有三棵哈夫曼树，其中一棵是 e。e 的点权显然比另外两棵哈夫曼树要大（或三个点权都相等）。而点权即为出现次数，另外两棵哈夫曼树的点权分别为下面字符的出现次数和，三棵树权值和显然 = \(1000\)。
接下来看选项，A 显然不合法，\(39\times 3<1000\)。对于 B，\(334\times 3=1002\)，是可以的。C,D 选项显然也是可以的。所以答案为 C。
图论
简单题：一个连通的简单无向图，共有 \(28\) 条边，至少有几个顶点。
Solution
让点最少，就让边最多。完全图的边是最多的。
回顾知识：完全图指每个节点都往其他的点连边。有向完全图的边数是 \(n\times(n-1)\)，无向完全图的边数是 \(\dfrac{n\times(n-1)}{2}\)。本题中讨论的是无向图。
列出方程：\(\dfrac{n\times(n-1)}{2}=28\)
\(n=8\)。
无向图中的环最少包含一个顶点（自环），也可以两个或者更多。只要一个路径的第一个顶点和最后一个顶点相同，就称为环。
有向图的环也至少包含一个顶点（自环），可以两个或更多。
有向图中，若任意两个点之间存在一条边，不一定是强连通图。无向图就对了。
Claim:有向图中所有顶点入度和出度总和是图的边数两倍。
Proof:
对于 \(\forall\) 边 \((u,v)\)，设方向为 \(u\) 到 \(v\)，则该边对 \(u\) 贡献一个出度，对 \(v\) 贡献一个入度。即每一条边会贡献两次。
神秘语法
函数传参问题。
void qwq(int *a[]); //传递一个指针数组，每个指针指向二维数组每一行的起始。
void qwq(int **a); //传递一个指向指针的指针。外层指针指向“指向二维数组各行起始”的指针数组的首元素。与上面等价。
void qwq(int a[][3]); // 这是可行的
void qwq(int a[][]);void qwq(int a[3][]) // 都是不行的 必须规定列长度
char s[];
char *t = s;
while(~scanf("%s",t)) t += strlen(t);
这个东西可以拼接字符串。
高度为 \(n\) 的满二叉树有 \(2^0+2^1+2^2+\dots +2^{n-1}=2^n-1\) 个节点。
dfs 时注意回溯，记得消除影响全。
遇到一些比较难的组合数学，大分类讨论的选择题，放弃。不差那两分。不要在防 ak 题上浪费时间。
标签：log,哈夫曼,int,NOTES,times,链表,节点 From： https://www.cnblogs.com/SXqwq/p/18402553