提示：第一次打开latex会炸，请刷新

备考

由于之前的实在是太卡了，因此把它独立出来

5G

第五代移动通信技术（英语：5th generation mobile networks或5th generation wireless systems、5th-Generation，简称5G或5G技术）是最新一代蜂窝移动通信技术，也是继4G（LTE-A、WiMax）、3G（UMTS、LTE）和2G（GSM）系统之后的延伸。5G的性能目标是高数据速率、减少延迟、节省能源、降低成本、提高系统容量和大规模设备连接。Release-15中的5G规范的第一阶段是为了适应早期的商业部署。Release-16的第二阶段将于2020年4月完成，作为IMT-2020技术的候选提交给国际电信联盟（ITU） [1] 。ITU IMT-2020规范要求速度高达20 Gbit/s，可以实现宽信道带宽和大容量MIMO。

运算符

相同优先级中，按结合性进行结合。大多数运算符结合性是从左到右，只有三个优先级是从右至左结合的，它们是单目运算符、条件运算符、赋值运算符。

P,NP等

名称	描述
P	确定多项式时间 $O(n^c),c$ 为常数
NP	不确定多项式时间，但可以多项式时间验证
PH	多项式层级，如果一个问题开始是NP，但是随后会增加额外的复杂性，那么该问题就属于PH。
PSAPCE	多项式空间（Polynomial Space）包含了所有可以通过合理内存来解决的问题
BQP	能用量子计算机解决的问题，例如确定整数的素因子
EXPTIME	指数型时间，包括了上面所有
BPP	有界误差概率多项式时间，但是该类问题允许算法在某些步骤包含随机因素。BPP中的算法只需给出概率趋近于1的正确答案。

几个关系

$P\in{NP},NP\in PH$

计算机科学家们已经证明，BQP包含在PSPACE中，且BQP包含P。但是他们不知道BQP是否包含在NP中，但是他们相信这两类是不可比的：存在NP中的问题但不是BQP，反之亦然。

$\text{EXP(EXPTIME)}\neq \text{P}$

图灵奖项目
P=NP,或者P≠PH
P和PSPACE不同，或者P和PSPACE相同（似乎和P=NP等价？）
BQP是否包含在NP中(目前默认不等于)
BPP=P是否成立(后果是所有能随机化的都可以去随机化)

容易遗忘的

哈密顿路是每个点一次，欧拉路是每个边一次

考古

ENIAC 埃尼阿克

ENIAC是继ABC（阿塔纳索夫-贝瑞计算机）之后的第二台电子计算机和第一台通用计算机。

计算机应用

计算，数据储存处理，通信，辅助工作等

第一个程序员

Ada（女），也有为此命名的语言

奖

图灵奖（华人唯一获得者姚期智），菲尔兹奖（数学），诺贝尔奖（物化生和平经济文学），香农奖（香农奖是通信理论领域最高奖）

2008年，阿里坎提出了极化码理论，破解了香农信息论领域尘封近60年的难题，也成为世界上第一种可以被理论证明的、逼近香农信道容量极限的编码方案。2016年11月19日，在美国内华达州里诺的3GPP RAN1#87会议上，国际移动通信标准化组织3GPP确定了Polar码作为5G eMBB（增强移动宽带）场景的控制信道编码方案。至此，5G eMBB场景的信道编码技术方案完全确定，其中Polar码作为控制信道的编码方案。

他在2018年获得香农奖（Claude E.ShannonAward）

计算机组成

冯诺依曼架构

特点：

(1)计算机处理的数据和指令一律用二进制数表示
(2)顺序执行程序
计算机运行过程中，把要执行的程序和处理的数据首先存入主存储器（内存），计算机执行程序时，将自动地并按顺序从主存储器中取出指令一条一条地执行，这一概念称作顺序执行程序。
(3)计算机硬件由运算器、控制器、存储器、输入设备（键盘，鼠标，麦克风）和输出设备（显示器，打印机，绘图仪等）五大部分组成

CPU包括运算器和控制器

硬件相关

字长：32位和64位，即cpu一次能处理多少位的数据。

外频 × 倍频＝内频

摩尔定律：18月翻倍

$1024B=1KB=1.024KiB$

系统/软件

系统：windows,dos,unix,linux,macos,android,ios,鸿蒙

语言

机器语言，汇编语言，高级语言

机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合

通过汇编过程转换成机器指令。特定的汇编语言和特定的机器语言指令集是一一对应的，不同平台之间不可直接移植。(汇编语言由高级语言编译而来)

高级编程语言作为一种通用的编程语言，它的语言结构和计算机本身的硬件以及指令系统无关，它的可阅读性更强，能够方便的表达程序的功能，更好的描述使用的算法。 [1]

编译型语言 C、C++、Delphi

解释型语言 Java、JavaScript、VBScript、Perl、Python、Ruby、BASIC，MATLAB(?)

进制

进制	基数	基数个数	权	进数规律
十进制	0、1、2、3、4、5、6、7、8、9	10	10i	逢十进一
二进制	0、1	2	2i	逢二进一
八进制	0、1、2、3、4、5、6、7	8	8i	逢八进一
十六进制	0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F	16	16i	逢十六进一

转换方法（建议）

被转换的数十进制下为 $x$ , 设权为 $k$ , 找到满足 $k^i\leq x$ 最大的 $i$ ，则 $i$ 从大到小枚举到 $0$ ,若 $x-k^i \geq 0$ 则 $x-=k^i$ 并设 $i$ 位为 $i$

转化成十进制，则从右向左每次权*2 乘此位数字即可

小数转换，可能永远除不尽，因此只需保留合适精度即可

表示负数：

原码：用第一个表示符号，后面的表示绝对值

反码：原码除了第一位后取反

补码：反码+1

补码的意义：化减为加

编码

文字: ASCLL(8bit),GBK(16bit),utf-8(24bit)

图片: 黑白（01），24位彩色（24bit，RGB）

声音文件

NOI

NOI : 1984,CCF

NOIP: 1995 (2019 咕)

可带:文具，衣服，水，证件

2020以后只能使用 c++

逻辑运算符

c++	数学符号
!	$\neg$
&&	∧
\|\|	∨
^(不算逻辑运算)	$\oplus$

优先级：非，与，或

复杂度

首先说

符号	意义
$ O(f(n)) $	给出了算法运行时间的上界,也就是最坏情况下的时间复杂度
$\Theta(f(n))$ `\Theta`	给出了算法运行时间的上界和下界,这里Θ(f(n))是渐近的确界,另外,并非所有的算法都有Θ(f(n)).
$\Omega(f(n))$ `\Omega`	给出了算法运行时间的下界,也就是最好情况下的时间复杂度

主定理

$a$ 为递推的子问题数量,是常数

$\frac{n}{b}$ 为子问题规模, $b$ 是常数

$f(n)$ 为递推以外进行的工作

实际上如果与 $\log$ 有关，不妨套一下 $\log n^{0.5}=0.5\log n=\log(\sqrt{n})$

有奇效

$T(n)=2(\frac{n}{2})+O(\sqrt{n})$ 复杂度为 $\Theta(n\sqrt{n}) $

排序

只有基于比较的排序才能说稳不稳定

排序	特点	复杂度	缺点
计数排序	不基于比较	$O(a+n)$	只能处理值域不大的
选择排序		$O(n^2)$	不稳定
冒泡排序	稳定	$O(n^2)$
插入排序	稳定	$O(n^2)$
归并排序	稳定	$O(n\log n)$	需要辅助空间
快速排序		$O(n\log n)$	不稳定，可以被卡成 $O(n^2)$
堆排序		$O(n\log n)$	不稳定
桶排序		$O(a+n)$	只能处理值域不大的
希尔排序	不稳定	$\Omega(n\log n)$ , $O(n^2)$
基数排序		$O(n\log _dS)$	需要额外空间

说明

对选择排序不稳定的说明：例如5 5 1 第一个 5 会和 1 换成 1 5 5

归并排序比较次数最小为 $2n-1$ (两个排好序长度为 $n$ 的数组归并)

~~咕一下快排~~

#include<iostream>
using namespace std;
int n,a[1000001];
void qsort(int l,int r)//应用二分思想
{
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//查找左半部分比中间数大的数
        while(a[j]>mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件（左小右大）的数
        {
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l<j) qsort(l,j);//递归搜索左半部分
    if(i<r) qsort(i,r);//递归搜索右半部分
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

贪心

需要证明正确性

哈夫曼编码

让一棵树的信息熵最小的编码吧（

貌似是香农提出然后自己算法锅了然后哈夫曼写是第一个写对了求一棵二叉树最小信息熵的做法吧（（

树的带权路径长度最小的编码，如果搞不懂可以用信息熵来水吧

查找相关

名称	复杂度	特点
二分	$O(\log n)$	需要数组有序
顺序查找	$O(n)$	效率低，但啥都能干
查找序列最大值	$O(n)$	$n-1$ 次比较

递推，递归分治

递推：即从小到大，例如求斐波那契数列

分治：把一个大问题拆分成小问题然后递归解决

栈，队列，链表

栈：先进后出，合法的出栈序列一共有卡特兰数种

队列：先进后出

链表：每个元素只知道前面的一个和后面的一个是哪个元素

插入删除请手模，实现方式可以指针或者数组

链表分单链表和双链表，单链表只有后继，双链表有前驱和后继

循环单链表，循环双链表：顾名思义

图论基础

树

$n$ 个点 $n-1$ 条边

有几个等价的性质：

A.G是联通且无环的

B.G是联通且具有n-1条边

C.G有n-1条边且无环

D.G无环且对任意一条 $u,v$ 恰好有一条 $u \to v$ 的路径

一棵树也算森林

二叉树

定义	解释
高度	树的层数
节点
叶子
满二叉树	每个节点有两个或者没有儿子
完全二叉树	高度为 $h$ 并且有 $2^h-1$ 个节点

遍历

方式
前序遍历	根左右
中序遍历	左根右
后序遍历	左右根

应用

表达式树：

方式
中序表达式
后序表达式
前序表达式

顾名思义了（

性质嘛，能打括号先打括号，然后括号内是一棵子树，按照中序遍历建图，得到的三个遍历分别是中序后续前序

注意区别

前缀表达式反过来基本上就是后缀表达式，但是减的时候前缀表达式是栈中第一个减第二个，后缀表达式是第二个减第一个

图

估计就考这几个

1.度-和公式（ $\sum d(v)=2*|E|$ ）

2.若无向图存在 $\delta(G)=k$ ,则存在长度至少为 $k+1$ 的环, $\delta(G)$ 表示度最小的点的度

3.存图的方式为邻接表和邻接矩阵（用了二叉树的 $\text{vector}$ 也算邻接表）

4.cayley公式， $n$ 个不同的顶点的最小生成树个数为 $n^{n-2}$

5.遍历方式 $\text{dfs,bfs}$ 这东西基本都会

6.完全图，边数为 $\frac{n*(n-1)}{2}$ ,记做 $K_n$ ,应该不会考可平面（ $\text{peterson}$ 估计也不会）

7.生成树 prim $O(n^2)$ ，Kruskal $ O(m \log m)$

8.一笔画问题：偶图（无向图），入度等与出度（有向图），或者两个点度为奇数（无向图，此时不能回到起点，不是欧拉图），大概是分解成二分图来说明。不用管混合图的欧拉回路（因为要用网络瘤），

9. $\text{dijkstra} ~O((m+n)\log n)$

卡特兰数

$h(n)=\frac{C(2n,n)}{(n+1)}$

可以写成这种等价的性质

$h(n)=C_{2n}^n - C_{2n}^{n-1} $

$h(n)$ 的意义
$1,2,3,4,5...n$ 的合法的出栈序列
合法的括号匹配序列
凸多边形三角划分的方案数
$n$ 个节点组成的二叉搜索树的个数这个下标从 $0$ 开始
$n$ 个 $1$ 和 $n $个 $−1$ 构成的，任意前缀和不小于$ 0$ 的序列个数
$(0,0)$ 到 $(n,n)$ 的方案数
有一个长度为 $2m$ 的 01序列，其中1,0各 $m$ 个，要求对于任意的整数$ k \in [1,2m]$，数列的前 $$ 个n数中，1的个数不少于0。

显然后面三个是等价的

斐波那契数

递规求复杂度 $O(F(n))$

$\varphi$

1.积性函数

2.与 $n$ 互质的数的和是 $\frac {n\times \varphi(n)}{2}$ 因为互质的数成对出现且对称轴 $\times 2n=n$

3.不互质的情况下，若 $x^2|n$ 那么 $\varphi(n)=\varphi(x)\times x$ 否则为 $\varphi(n)=\varphi(x)\times (x-1)$ s