LAST UPD:2023/09/09
内容非常杂乱，算是初赛前的总结吧qwq
排序算法比较
-
插入排序，冒泡排序，选择排序 ： \(O(n^2)\)
-
其他非线性排序的时间复杂度为 \(O(n)\)
-
线性排序的时间复杂度为 \(O(n)\) 。
稳定性比较：
插入，冒泡，二叉树，归并以及其他的线性排序是稳定的。反之，选择，希尔，快速，堆排序是不稳定的。例子需要记忆。
汉字存储
一级汉字按照拼音排序，二级汉字按照部首排序。
一般使用数字化点阵字模存储，具体地，每个字节有 8 个二进制位，因此， \(x\times x\) 个二进制位存储的，每 8 个二进制位占用一个字节，所以需要字节数为 \(x\times x \div 8\)。
关于存储单位
从小到大依次是：B,KB,MB,GB,TB,PB。换算关系为 1024。
计算机常识
首位程序员：Ada Lovelace
首台计算机：ENIAC，冯诺依曼设计。
RAM：读写存储器，当电源电压去除时，数据会丢失。
ROM：只读存储器。其存储的信息在制造的时候就存入的。当断电后，数据不会丢失。BIOS就是固化在主板上ROM的一个程序。
内存储器：包括RAM,ROM和高速缓冲存储器Cache三种。
CPU能访问到的最大内存取决于地址总线。地址总线很小但是内存很大毫无意义。
字长：指计算机能处理的二进制代码的位数。目前常有的有16，32，64位字长的计算机。
计算机系统总线上传送的信号有：数据信号，控制信号，地址信号。CPU内部的寄存器比外部的高速缓存储器Cache要快很多。
微型计算机仍属于超大鬼母集成电路。图灵是英国人。冯诺依曼是美国人。
Tree 的基本定义以及前缀，中缀，后缀遍历
先序遍历 类似于DFS
-
访问根节点
-
先序遍历左子树
-
先序遍历右子树
中序遍历
-
中序遍历左子树
-
访问根节点
-
中序遍历右子树
后序遍历
-
后序遍历左子树
-
后序遍历右子树
-
访问根节点
利用上述我们可以处理前缀表达式，中缀表达式，后缀表达式。直接建树处理即可。
组合数学
最基础的排列组合公式
S 初赛近几年数学的最常见考法，非常简单。
卡特兰数
卡特兰数是这样的一种数列：
上述递推关系的解为：
这个公式可以推导，见卡特兰数学习笔记
插板法
插板法（Stars and bars）是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。
接下来我们会通过几个问题来进一步理解插板法。
Q1:正整数和的数目
现有 \(n\) 个完全相同的元素，要求分成 \(k\) 组，保证每一组都不为空，共有几种分发？
考虑在 \(n\) 个 元素，两两构成的 \(n-1\) 个空隙中插入 \(k-1\) 个板子。
答案显然为 \(C_{k-1}^{n-1}\)
Q2:非负整数和的数目
在 Q1 的基础上，我们规定每组可以为空。求有几种分发。
我们显然无法直接插板，不妨先“借” \(k\) 个数，使得每组都有数字，最后再减去“借”的 \(k\) 个数即可。这样就形成了“每组可以为空”。
答案为 \(C_{k-1}^{n+k-1}\)
同时满足：
定理：组合恒等式
这就是插板法的公式。
Q3:不相邻的排列
在 Q1 的基础上，要求每组数不得少于 \(a_i\) 个。
借鉴 Q2 的处理方法，我们先 “借” \(\sum a_i\) 个元素，以确保每组数的和都符合题意。也就是令：
\(x_i\) 即为每组内有多少个数。
得到方程：
套用插板法公式即可解决问题。
二项式定理
先给出公式：