初赛复习

较为笼统而简洁的概括。

考试只要细心，不会的猜，就能过线。

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\texttt{ MB }\)

寄存器 > Cache（高速缓存） > RAM > ROM

内存：RAM（随机存储器）+ ROM + 其他，断电会丢失数据

CPU、GPU等固件上装配的ROM（只读存储器）所存储的数据无法被改写或删除，也不会因电源关闭而丢失

摩尔定律：18个月翻倍（很快就要失效了）

软件系统

操作系统Windows,DOS,UNIX,Linux,MacOS,Android,IOS等

应用软件：浏览器、办公软件、游戏等等

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

编码

ASCII编码（英文），BGK编码（早期中文，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/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

树

一种说法是：任意两个结点连通（无向图）且有唯一一条路径

二叉树

\(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没啥好递归的）

不难发现它的中序遍历就是中缀表达式。

图

好像有不少概念，到时候整理一个比较全的

这里写几个重点的：

完全图：两两都有连边的无向图

结点的度数：

• 有向图：入度（入边数量）+出度（出边数量）
• 无向图：与其相连的边的数量

重边：两个相同结点存在多条边，且方向相同（无向图）

自环：起点和终点相同的边与这个结点构成的环

简单图：无重边无自环

DAG（有向无环图）：显然。

组合数学

第二类斯特林数 \(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\) 个相同的球，那就是插板法的问题了，所以不同的球是第二类斯特林数的关键。

\[ \left\{\begin{array}{l} n \\ k \end{array}\right\}=\left\{\begin{array}{l} n-1 \\ k-1 \end{array}\right\}+k\left\{\begin{array}{c} n-1 \\ k \end{array}\right\} \] 第一类斯特林数 \(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\) 个圆排列的方案数 \[ \left[\begin{array}{l} n \\ k \end{array}\right]=\left[\begin{array}{l} n-1 \\ k-1 \end{array}\right]+(n-1)\left[\begin{array}{c} n-1 \\ k \end{array}\right] \]

---

参考文献：

[1] https://blog.csdn.net/pange1991/article/details/85460755

[2] https://zh.wikipedia.org/wiki/%E5%8D%83%E5%AD%97%E8%8A%82