初赛复习
较为笼统而简洁的概括。
考试只要细心，不会的猜，就能过线。
IT发展历史
第一台计算机：ENIAC，1946年
应用：计算，数据储存处理，通信，辅助工作等
第一个程序员：Ada（女），有为此命名的程序语言
图灵奖（计算机），菲尔兹奖（数学），诺贝尔奖（物化生经济文学和平）
ACM（美国计算机学会）IEEE（电气电子工程师学会）CCF（懂得都懂）
图灵奖由ACM设立，获得图灵奖的华人学者只有姚期智一人，名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵，是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
计算机组成
冯诺依曼结构：
输入设备：将信息输入进计算机的是输入设备
输出设备：将计算机的信息输出给人的是输出设备
特例：触摸屏既是输入设备又是输出设备
CPU字长：32位/64位 （CPU一次能并行处理的二进制位数，一定是8的倍数）
位（Bit）：一个01
字节（Byte）：八个01
1PiB=1024TiB, 1TiB=1024GiB, 1GiB=1024KiB, 1KiB=1024Byte, 1Byte=8Bit
1Mib=1024Kib, 1Kib=1024bit=128Byte
KB,MB,GB由于Windows的广泛使用导致了普遍的混淆
实际是 1MB=1000KB,1KB=1000Byte ，MacOS以该单位计算
也就是说这个sb的Windows用的是KiB,MiB，标的是KB,MB。
所以基本上出题的时候出了KB还是按1024算，但是比较专业的出题人都会避免这个问题。
小例子：
int a[10000005];所占空间为 $(10^7+5)\times 4 /1024 /1024 \approx 38.15\textrm{ MB}$
读取速度：寄存器 > Cache（高速缓存） > RAM > ROM
内存：RAM（随机存储器）+ ROM + 其他，断电会丢失数据
CPU、GPU等固件上装配的ROM（只读存储器）所存储的数据无法被改写或删除，也不会因电源关闭而丢失
摩尔定律：18个月翻倍（很快就要失效了）
软件系统
操作系统：Windows, DOS, UNIX, Linux, MacOS, Android, IOS 等
应用软件：浏览器、办公软件、游戏等等
机器语言、汇编语言、高级语言
编码
ASCII编码（英文）、GBK编码（早期中文，2字节）、UTF-8（新&常用，目前3字节）
图片：黑白（01），24位彩色（RGB）
文件系统扩展名：
图片：jpg(jpeg), gif, png, tiff
文档：txt, docx, pdf
声音：mp3/视频：avi, rm, mp4
可执行文件（的后缀名）：exe(Windows), 无(Linux)
NOI系列
NOI：1984年
NOIP：1995 - 2019，2020 - 至今
可以带文具（不可草稿纸），水，衣服，证件
2022年之后只能用C++了（Pascal在2022年之后不再支持）
程序设计
C++的编译器是 g++，C的编译器是 gcc，评测环境详见 link
编译：代码->可执行文件（机器码）：C/C++, Pascal
解释：一行一行运行：Python, JavaScript, PHP, BASIC
特例：Java不太好定义是编译执行的还是解释执行
时间复杂度：数据规模增长和运行时间增长的趋势
基本算法
复杂度计算
就讲个不常见的栈空间计算。
递归栈会记录行号&局部变量
栈层数=递归最大深度
对于下面这种（来自洛谷初赛模拟题）
int f(int x)
{
if(x <= 2) return 1;
int ans = f(x-1) + f(x-2);
ans %= 10000;
return ans;
}
// 调用f(12345) ，内存限制128MB显然不会爆栈空间，因为每次存的东西很少（就几个int），并且栈层数也就12345
所以这个肯定是超时。
排序算法
排序稳定性：元素相等时的相对顺序不改变，则排序算法具有稳定性。
注意经常考的不稳定排序有：快速排序、希尔排序、堆排序、（直接）选择排序。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | yes |
| 直接选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | no |
| 直接插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | yes |
| 快速排序 | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(n \log n)$ | no |
| 堆排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | no |
| 希尔排序 | $O(n \log n$) | $O(ns)$ | $O(n)$ | $O(1)$ | no |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | yes |
| 计数排序 | $O(n + k)$ | $O(n + k)$ | $O(n+k)$ | $O(n+k)$ | yes |
| 基数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | yes |
贪心
正确性相对来说比较难判断，考场上可以选择打表找规律（或者凭直觉）
二分
二分答案要求答案在一定范围内具有“单调性”。
时间复杂度 $O(\log N)$ ，$N$ 表示二分的范围大小
递归&分治
递归的思想在于把原问题拆解成若干性质相同的子问题
与递归分治有关的时间复杂度分析：主定理
简单数据结构
好的我们来讲一讲树套树
栈
出栈序列方案数：卡特兰数 $C_n = \dfrac{1}{n+1} \dbinom{2n}{n}$
队列
队列：先进先出
链表
单向链表 o->o->o->o
双向链表 o-o-o-o
树
一种说法是：任意两个结点连通（无向图）且有唯一一条路径
二叉树
$n$ 个结点 $n-1$ 条边的连通图
每个结点的至多有两个子结点
满二叉树第 $i(i\ge 1)$ 层的结点个数为 $2^{i-1}$
$k(k\ge 1)$ 层的二叉树有 $2^{k}-1$ 个结点（证明显然）
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
表达式树
建表达式树的方法
给定中缀表达式（就是1+1=2这种）
例： a+b*c+d
先套好括号 (a+(b*c))+d
递归处理 a+(b*c) ，d 即可（虽然d没啥好递归的）
不难发现它的中序遍历就是中缀表达式。
有关前缀表达式和后缀表达式，也可以用表达式树来理解
前缀表达式就是 +a+*bcd，前序遍历，从右往左用栈模拟可以计算结果。
后缀表达式就是 abc*d++，后序遍历，从左往右用栈模拟可以计算结果。
前缀表达式一定是符号在最前面，后缀表达式相反。
图
好像有不少概念，到时候整理一个比较全的
这里写几个重点的：
完全图：两两都有连边的无向图
结点的度数：
- 有向图：入度（入边数量）+出度（出边数量）
- 无向图：与其相连的边的数量
重边：两个相同结点存在多条边，且方向相同（无向图）
自环：起点和终点相同的边与这个结点构成的环
简单图：无重边无自环
DAG（有向无环图）：显然。
组合数学
这个有的好讲了，随表挑几个，其他可以看这个 小蓝书16.1
第二类斯特林数 $S(n,k)$ 或 $\left\{\begin{array}{l}n \\k\end{array}\right\}$ ，边界为：$\left\{\begin{array}{l}n \\0\end{array}\right\} = [n=0]$ 。
将 $n$ 个两两不同的元素划分为 $k$ 个无区别的非空子集的方案数。
换个说法，$n$ 个不同的球放到 $m$ 个相同的盒子，不可以有空盒子的方案数。
注意，如果是 $n$ 个相同的球，那就是插板法的问题了，所以不同的球是第二类斯特林数的关键。
第一类斯特林数 $s(n,k)$ 或 $\left[\begin{array}{l}n \\k\end{array}\right]$ ，边界为：$\left[\begin{array}{l}n \\0\end{array}\right] = [n=0]$ 。
将 $n$ 个两两不同的元素划分为 $k$ 个互不区分的非空轮换的方案数。
换个说法，$n$ 个不同的数恰好划分为 $k$ 个圆排列的方案数
参考文献：
[1] https://blog.csdn.net/pange1991/article/details/85460755
[2] https://zh.wikipedia.org/wiki/%E5%8D%83%E5%AD%97%E8%8A%82
