给大伙表演一个原地退役。
信息学历史
计算机组成
字长：$32$ 位和 $64$ 位。
主频：$2.4\text{GHz}$ 。
内存：$8\text{GB}$ 。
位（$\text{Bit}$）：一个 $01$ 。
字节（$\text{Byte}$）：八个 $01$ 。
内存换算
$\text{1KB=1024Byte}$
$\text{1MB=1024KB}$
$\text{1GB=1024MB}$
$\text{1TB=1024GB}$
摩尔定律
$18$ 个月翻倍。其核心内容为：集成电路上可以容纳的晶体管数目在大约每经过 $18$ 个月到 $24$ 个月便会增加一倍。换言之，处理器的性能大约每两年翻一倍，同时价格下降为之前的一半。
软件系统
操作系统：$\text{Windows,DOS,UNIX,Linux,MaxOS,Android,iOS,}$ 鸿蒙（华为）。
应用软件：浏览器，办公软件，游戏等。
软件由机器语言，汇编语言，高级语言编写。
编码
文字，图片，声音等都会转化成 $01$ 串编码。
编码有：$\text{ASCII}$ 码，$\text{GBK}$ 码（$\text{2 byte}$），$\text{utf-8}$ 码（$\text{3 byte}$ ）等。
图片文件格式：$\text{jpg,png,jpeg,tiff,raw,bmp,gif}$ 等。
视频文件格式：$\text{wmv,mp4,m4v,avi,flv,mkv,dat}$ 等。
声音文件格式：$\text{wav,mp3,midi,wma,cda}$ 等。
NOI 系列
$\text{NOI}$ 开始于 $1984$ ，由中国计算机学会（$\text{CCF}$）举办。
$\text{NOIp}$ 生于 $1995$ ，死于 $2019$ ，复活于 $2020$ 。
在 $2022$ 后，$\text{NOI}$ 仅支持 C++ 。
考场仅能携带文具（无纸张），衣物，证件。
程序设计
所谓编译，就是把代码变成可执行文件（机器码），使用 C++ ，Pascal 等媒介。
解释性语言指的是一行一行的运行，如 Python ，JavaScript ，PHP ，BASIC 。
两者的区别在于，编译不允许局部错误，解释允许局部错误。
时间复杂度：数据规模增长和运行时间增长的趋势。
算法
排序
排序中的稳定指的是对于相同的数而言，其相对排名在排序后不变，则称为稳定。
计数排序
不基于比较，时间复杂度 $\mathcal O(a+n)$ ，仅能求出最大值。
$a$ 是选票数，$n$ 是候选人数。
选择排序
不稳定，时间复杂度 $\mathcal O(n^2)$ 。
冒泡排序
稳定，时间复杂度 $\mathcal O(n^2)$ 。
插入排序
稳定，时间复杂度 $\mathcal O(n^2)$ 。
归并排序
稳定，时间复杂度 $\mathcal O(n\log n)$ ，需要额外辅助空间。
快速排序
不稳定，$\Omega(n\log n)-\mathcal O(n^2)$ 。
堆排序
不稳定，时间复杂度 $\mathcal O(n\log n)$ 。
贪心
需要证明的可能不正确算法。
二分
在有序中折半查找，时间复杂度 $\mathcal O(\lceil\log_2 n\rceil)$ 。
递推递归
递推是从小到大顺推。
递归是从大到小逆推后反推回去。
使用示例：斐波那契，杨辉三角，动态规划等。
分治
大问题拆成小问题，递归解决。
归并排序和快速排序都用到了分治策略。
主定理
有一种奇妙的东西叫做主定理，（另话：关于时间复杂度的计算，$\text{Sukwants}$ 写了三篇较详细的文章，可以去看看）可以计算递归式的时间复杂度，形如：
有一个奇妙的公式，和做法，可以硬背。
这里的 $T(n)$ 是时间复杂度函数。
首先表明定义：
- $n$ 为求得序列的第几位，称为问题规模大小；
- $a$ 为原问题的子问题个数；
- $\frac{n}{b}$ 为子问题大小，这里假设每个子问题大小相同；
- $f(n)$ 为合并代价，即合并时间。
用通俗的话来讲：首先考虑 $aT(\frac{n}{b})$ 的时间，有公式 $\mathcal O(\log_ba\times n)$ ，然后考虑 $f(n)$ 的时间复杂度（假设为 $\mathcal O(t)$），这里分为三种情况：
- 如果 $\mathcal O(n^{\log_ba})>\mathcal O(t)$ ，则 $T(n)=\mathcal O(n^{\log_ba})$ ；
- 如果 $\mathcal O(n^{\log_ba})<\mathcal O(t)$ ，则 $T(n)=\mathcal O(t)$ ；
- 如果 $\mathcal O(n^{\log_ba})=\mathcal O(t)$ ，则 $T(n)=\mathcal O(n\log t)=\mathcal O(n\log\log_ba)$。
严格而言，上述三种情况其实是：
- 若函数 $n^{\log_ba}$ 更大，则 $T(n)=\Theta(n^{\log_ba})$ ；
- 若函数 $f(n)$ 更大，且满足 $af(\frac{n}{b})\leq cf(n)$ ，则 $T(n)=\Theta(f(n))$ ；
- 若两函数相等，则 $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$ 。
我也不知道为什么，背就完了。
举几个例子，可能就有所理解了。
二分：$T(n)=T(\frac{n}{2})+\Theta(1)$
得到 $a=1,b=2,f(n)=1$ ，则 $\mathcal O(n^{\log_ba})=0=\Theta(1)$ ，则时间复杂度为 $\mathcal O(\log n)$ 。
归并：$T(n)=2T(\frac{n}{2})+\Theta(n)$
得到 $a=2,b=2,f(n)=n$ ，则 $\mathcal O(n^{\log_ba})=n=\Theta(n)$ ，则时间复杂度为 $\mathcal O(n\log n)$ 。
二叉树遍历：$T(n)=2T(\frac{n}{2})+\mathcal O(1)$
得到 $a=2,b=2,f(n)=1$ ，则 $\mathcal O(n^{\log_ba})=n>1=\mathcal O(n)$ ，则时间复杂度为 $\mathcal O(n)$ 。
需要注意的是，$\log n$ 并不属于多项式范畴，所以严格来讲，$\mathcal O(n\log n)$ 和 $\mathcal O(n)$ 是同级的，所以，对于下面的式子：
$T(n)=2T(\frac{n}{2})+n\log n$
有 $n^{\log _ba=1}=n$ 和 $f(n)=n\log n$ ，两者同级，所以时间复杂度为 $\mathcal O(n\log^2 n)$ 。
数据结构
处理数据的骨架。
线性表
栈
$\text{FILO}$ 式数据结构。（$\text{First Input ,Last Output}$ ，先进后出）
常用于深度优先搜索（$\text{dfs}$）。
队列
$\text{FIFO}$ 式数据结构。（$\text{First Input ,First Output}$ ，先进先出）
常用于宽度优先搜索（$\text{bfs}$，也称作广度优先搜索）
链表
每一个数都只有一个指针指向自己的下一位，从何由指针组成一条完整的链。
插入删除不需要移动元素，不许事先估计存储空间，所需空间与线性表长度成正比，但不支持随机访问。（因为内存不连续）
树
$n$ 个结点，$n-1$ 条边，所有结点连通且没有环的图。
森林：树的集合。
二叉树
每一个结点至多有 $2$ 个子结点的有根树。
一棵深度为 $i$ 的二叉树每一层数量至多为 $2^{i-1}$ ，一共结点至多为 $2^i-1$ 。
满（完美）二叉树（结点为 $2^i-1$ 的二叉树），完全二叉树为 $i-1$ 层都满的二叉树，完全线段树就是一种完全二叉树。
二叉树有 $3$ 种遍历方式：前序遍历，中序遍历，后序遍历。
前序遍历：根结点 $\to$ 左子树 $\to$ 右子树。
中序遍历：左子树 $\to$ 根结点 $\to$ 右子树。
后序遍历：左子树 $\to$ 右子树 $\to$ 根结点。
其中，前序遍历扩展到普通树型结构，并区分轻重儿子，就是树链剖分的 $dfn$ 序。
后序遍历的最后一个就是整棵树的根结点，在中序遍历里根结点左端的点在结点的左子树，根结点右端的点在结点右子树。
通过中序遍历和后序遍历推出前序遍历，就是用分治的思想，拆分区间。
表达式树
用树型结构表达一个算式。一般而言，表达式树的中序遍历就是我们常见的形式。
图
分为有向图和无向图。结点和边可能带权。
有两个集合 $V,E$ 表示顶点和边，边连接结点。
每个节点有一个参数表示进入的边数和出去的边数，称为度数。
重边：几条性质相同的边（连接结点一致，方向一致）。
自环：一条连接了两个相同结点的边。
简单图：无重边，无自环的图。
完全图：指任意两个结点都存在边的图，有 $\frac{n(n-1)}{2}$ 条边。（这里指无向图）
图的存储
一般有 $3$ 种方式：邻接矩阵，邻接表，链式前向星。
邻接矩阵空间复杂度 $\mathcal O(n^2)$ ，一般用于稠密图。
邻接表空间复杂度 $\mathcal O(m)$ 需要动态申请，一般用 std::vector 实现。
链式前向星用类似于链表的结构组成，和邻接表类似，不过不需要动态申请内存。
图论算法
单源最短路径算法：$\text{Dijkstra,SPFA}$ ，时间复杂度分别为 $\mathcal O(n\log n),\mathcal O(kn)$ 。
多源最短路径算法：$\text{Floyd,Johnson}$ ，时间复杂度分别为 $\mathcal O(n^3),\mathcal O(nm\log m)$
最小生成树：$\text{Prim,Kruskal}$ ，时间复杂度 $\mathcal O(n^2),\mathcal O(m\log m)$ 。
欧拉回路：一笔画问题，只能最多 $2$ 个奇数度的结点。
数论
进制
$k$ 进制转 $10$ 进制：
$(\overline{a_1a_2\dots a_m})_k=a_m\times k^0+a_{m-1}\times k^1+a_{m-2}\times k^2+\dots a_{1}\times k^{m-1}$
$10$ 进制转 $k $ 进制：
将这个数除以 $k$ 直到比 $k$ 小，把每一次得到的余数从小位到大位组合，就是 $k$ 进制下的答案。这个方法被称为短除法。
这里仅仅讨论非负整数。