**C++ 标准模板库 (STL, Standard Template Library)**：包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).

前缀树基本知识前缀树又叫字典树(trie)，每个样本从头结点开始，根据前缀数据构建一个大树，没有路则新建结点，已经有路则复用结点，字符放在边上 使用场景： 需要根据前缀信息来查询优点：根据前缀信息选择书上的分支，节省大量的时间缺点：比较浪费空间，与总字符数量和字符种类（一个结点的路有很多条）有关 类描述实现前缀树 123456789101112131415161718192021222324252

用空间代替重复计算 例题描述 对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为： 修改一个字符（如把“a”替换为“b”） 删除一个字符（如把“traveling”变为“travelng”） 比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作

知识框架 树的基本概念树的属性在任意一棵非空树中应满足:1)有且仅有一个特定的称为根的结点。2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集$T_1,T_2,\dots ,T_m$，其中每个集合本身又是一棵树，并且称为根的子树。 结点的度：一个结点的孩子的个数 树的度：树中结点的最大度数 分支结点：又称非终端结点，即度>0的结点 叶（子）结点：又称终端结点，即度为0

I/O系统基本概念（统考大纲删除）输入/输出系统I/O控制方式外部设备I/O接口I/O接口的功能 进行地址译码和设备选择：CPU 送来选择外设的地址码后，接口必须对地址进行译码以产生设备选择信息，使主机能和指定外设交换信息。 实现主机和外设的通信联络控制：解决主机与外设时序配合问题，协调不同工作速度的外设和主机之间交换信息，以保证整个计算机系统能统

小红的red计数题目描述：    小红拿到了一个字符串。她有若干次询问，每次询问：若翻转第 l 个字符到第 r 个字符对应的区间，该字符串有多少“red”子序列。子序列指按照原顺序取若干字符（可以不连续）形成的新字符串。每次询问后小红并不会真正翻转区间。 输入描述：    第一行输入两个整数 n 和 q，代表字符串长度

求最大公约数欧几里得算法（辗转相除法）1234//若较大的数字为a，则O((loga)^3)public static long gcd(long a, long b){ return b == 0 ? a : gcd(b, a % b);;} 证明：gcd(a, b) = gcd(b, a % b) 设a % b = r,即gcd(a, b) &

算法思想next数组不含当前，前面字符串的前后缀最大匹配长度（不为整体），0下表的next为-1a abaabsaabaaa-1 0 1 aab“” “” √ 长度0a b × 长度1aa ab× 长度2 可补终止位置的next值 程序实现123456789101112131415161718192021222324252627282930313233343536373839//时间复

串的定义与实现字符串简称串，由零个或多个字符组成的有限序列 定长顺序存储采用一组连续的存储单元来存储串值的字符序列 12345typedef struct{ char ch[MAXSIZE]; int length;} SString; 堆分配存储12345typedef struct{ char *ch; int length;}

知识框架 随机变量及其分布函数的概念、性质及应用随机变量    其值会随机而定的变量，一般用大写字母表示 分布函数    设$X$是随机变量，$x$是任意实数，称$F(x)=P(X\leq x)(x\in R)$为随机变量X的分布函数，或称$X$服从F(x)分布，记为$X\sim F(x)$。 性质（充要条件