常识&参考资料

二进制

\(n\) 进制转 \(10\) 进制，第 \(i\) 位的值乘上其位权 \(2^{n-1}\)
\(10\) 进制转 \(n\) 进制，除 \(n\) 取余，逆序相加
比较恶心的是小数部分
\(n\) 进制转 \(10\) 进制，第 \(i\) 位的值，依然乘上其位权 \(2^{n-1}\)，只不过现在变成了 \(\displaystyle n^{-1},n^{-2},n^{-3},\cdots\)，见 2021csp-jT7
\(10\) 进制转 \(n\) 进制，乘 \(n\) 取整，见 NOIP2008tgT7

树上问题

二叉树有个性质：叶子节点的个数比度数为 2 的节点多 1

三种遍历顺序

前序、中序、后序，前中后指的是“根”

前序遍历：“根”左右
中序遍历：左“根”右
后序遍历：左右“根”

已知【前序遍历和中序遍历】求【后序遍历】

已知：前序遍历为 FBACDEGH，中序遍历为 ABDCEFGH，求后序遍历
解：
前序遍历中，第一个是根节点：F
中序遍历中，找根节点，隔开：ABDCE，F，GH
明确子树的节点个数：5、2
前序遍历中，根据节点个数，区分子树：

左：BACDE
右：GH

递归到子问题，程序实现如下：

int A[10005];  // 前序遍历 
int B[10005];  // 中序遍历
void work(
	int L, int R,
	int l, int r
) {
	/* 
	A[L]~A[R] 前序遍历
	B[l]~B[r] 中序遍历 
	*/
	if (L>R)  return;  // 边界：空树 
	int root = A[L];
	// TODO : 搜索，使 B[k]=root
	int sizel = (k-1)-l+1;
	int sizer = r-(k+1)+1;
	// 递归左子树 
	work(L+1, L+sizel, l, k-1);
	// 递归右子树
	work(l+sizel+1, R, k+1, r);
	// 输出：左、右、根，即后序遍历 
	cout << root << endl; 
	return;
}

已知【前序遍历和后序遍历】求【中序遍历】

已知：前序遍历 FBACDEGH，后序遍历 ADECBHGF，求有多少树满足条件？
分析：根节点绝对固定，无用，删除。当删去根节点后的剩余部分只有一个元素时，它作为刚刚删去的根节点的左右孩子对遍历结果无影响，产生 2 种情况，其余都只有 1 种情况
解：
对于整棵树，根节点：F，没用，删除根节点：

前序遍历：BACDEGH
后序遍历：ADECBHG

剩下前序遍历中，第一个必是左子树的根节点，后序遍历中，根据 B 划分，确定子树节点数，再根据节点数切割前序遍历

前序遍历：BACDE，GH
后序遍历：ADECB，HG

该步划分唯一，方案数 = 左右子树情况数的乘积
递归到子问题：二层左子树
删除根节点：B

前序遍历：ACDE
后序遍历：ADEC

根据 A 划分后序遍历，确定子树节点数，根据节点数切割前序遍历

前序遍历：A，CDE
后序遍历：A，DEC

该步划分唯一
二层左子树的左子树唯一，看右子树
删除根节点：C
根据 A 划分后序遍历，确定子树节点数，根据节点数切割前序遍历

前序遍历：D，E
后序遍历：D，E

该步划分唯一
递归到子问题：二层右子树
删除根节点：G
此时只剩 H，位置不确定，产生了 2 种方案

前缀、中缀、后缀表达式

三种表达式的转换
运算符作根节点，左右是运算结果，形成表达式树
然后按照三种方式遍历就行了

图上问题

强联通：有向图上，点两两之间可以互相到达
弱连通：有向图转换为无向图后联通
非连通无向图最大边数 \(C_n^2\)
最短路
欧拉路：遍历所有边
- 充要条件：有且只有两个奇点
欧拉回路：遍历所有边并回到起点
- 充要条件：没有奇点
- csp2022-s1T9：\(n\) 个点全排列，\(n\) 个点都可以作为起点，并且可以向左或向右走，所以方案数为 \(\displaystyle\frac{P_n^n}{2n}=\frac{(n-1)!}{2}\)
哈密尔顿路：遍历所有点

排序相关

基于比较的排序：冒泡、选择、插入、快排、归并、堆排
其他排序：桶排序、计数排序（按值域开桶）、基数排序（按照十进制位比较）
稳定性：相同元素排序后相对顺序不变，跳着交换的排序都是不稳定的

基于比较的排序比较

算法	平均时间	最坏时间	额外空间	稳定性
冒泡	\(O(n^2)\)	\(O(n^2)\)	×	√
选择	\(O(n^2)\)	\(O(n^2)\)	×	×
插入	\(O(n^2)\)	\(O(n^2)\)	×	√
快排	\(O(n\log n)\)	\(O(n^2)\)	×	×
归并	\(O(n\log n)\)	\(O(n\log n)\)	√	√
堆排	\(O(n\log n)\)	\(O(n\log n)\)	×	×

排列组合

排列组合的计算

被卡西欧宠坏了
\(P_n^m=\displaystyle\frac{n!}{(n-m)!}\)
\(C_n^m=\displaystyle\frac{n!}{m!(n-m)!}\)

常见计数方法

特殊优先、插空法、隔板法
线性丢番图方程 \(\displaystyle\sum_{i=1}^n{x_i}=m\ (x_i,n,m\in Z,\ n<m)\)

正整数解的个数（隔板法）：\(C_{m-1}^{n-1}\)
非负整数解的个数（转换+隔板法）：\(C_{n+m-1}^{n-1}\)

特殊数列

第一类斯特林数

合法括号序列方案数、栈的输出方案数、\(n\) 节点二叉树形态数
\(H_n=\begin{cases}\displaystyle\sum_{i=1}^n{H_{i-1}H_{n-i}}&n\geq2,n\in N^+\\1&n=1\end{cases}\)

第二类卡特兰数

\(n\) 个互不相同的元素划分为 \(k\) 个非空集合的方案数
\(S(n, k) = S(n-1, k-1) + k\times S(n-1, k)\)

时间复杂度分析

具体知识点看大佬的知乎，下面列几道做过的题

2021 csp-s1 T12

不加记忆化计算斐波那契数列的时间复杂度是指数级的。
递归树叶子结点的计算结果是 \(1\)，该函数可以抽象为：递归到叶子节点返回，回溯过程中不断进行 \(1+1+1+\cdots\) 的过程。
而【算法的用时】和【过程中 \(1\) 的个数】直接相关，故可以通过计算【递归树叶子结点的数量】来推算复杂度。
一种分析方法是，对于递归树，从根节点开始，每个节点都会向下延伸两个子节点，一共 \(n\) 层，所以叶子节点的数量可以估算为 \(O(2^n)\)。
另一种分析方法是，叶子结点的数量是 \(F_n\)，而斐波那切数列的增长是指数级的，所以复杂度可以估算为 \(O(2^n)\)。
（这种分析方法得到的结果应该为 \(O(F_n)\)，更精确，但答案只有 \(O(2^n)\)，这两者在数量级上一样，所以可选）

答案为 C。

2021 csp-s1 T17

作为一道阅读程序题，在分析复杂度的时候往往会被一堆看不懂的东西唬住。
读懂程序含义能帮助理解一堆抽象的变量名，还有不明所以的加法重构。
这题的特殊性在于，solve1() 和 solve2() 可以立刻猜想是两个功能一致但实现不同的函数。
进一步确认，两个程序需要传入相同的参数 (h,m)，都取了 h 和 m 的中点 j，都进行了递归，到这里已经可以基本验证猜想了。
所以这里重构的加法应该和 44~52 行的一些运算对应，结果应该是一样的。
当然读不懂也问题不大，只需要关注运算的数量级就行了，几步不明所以的加法只需要知道它是 \(O(1)\) 就可以直接略过。

接下来来到分析复杂度的重点，对【递归函数】的处理。
对 solve1() 来说，它和 2021 csp-s1 T12 一样，是一个【从叶子节点回溯，不断做加法】的过程，可以抽象为 \(Node() + Node() + Node() + \cdots\)，而每步加法只需要 \(O(1)\)，因此复杂度的数量级【和叶子结点的数量一致】，即 \(O(n)\)，选 B。

对 solve2() 来说就有所不同，它在回溯时还扫描了区间 [h,m]，【不能】简单抽象为不断累积的过程。
这里有两种考虑方法。
第一种是从结果上考虑，也就是【它到底扫描了哪些东西】。递归树根节点的那一次访问扫描了区间 [1,n]，向下递归出来的两个子区间各自扫描了区间 [1,n/2] 和 [(n/2)+1,1]，还是相当于扫描了区间 [1,n]，因此递归树每一层，都相当于对区间 [1,n] 进行了一次扫描，而区间长度每次都除以 2，因此这棵递归树一共有 \(O(\log n)\) 层，时间复杂度 \(O(n\log n)\)。
第二种是写出它的【用时函数表达式】，和上一种方法的分析一样，每一层花 \(O(n)\) 先扫描了一遍区间 [1,n]，然后递归为两个子区间，各自的规模是 \(\displaystyle\frac{n}{2}\)，所以有 \(T(n)=n+2T(\displaystyle\frac{n}{2})\)。然后代一下主定理的公式就行了，选 C。~~（然鹅主定理背不下来）~~

2020 csp-s1 T7

考察基本算法的时间复杂度。
深度优先遍历的过程中，每个节点被访问到之后，会通过与其相连的【边】看看子节点是否被访问过，这一过程可以视作【边】被访问了一次。
由于 vis[] 数组的记录，每个【节点】只会被访问一次。
综上，每条【边】和每个【点】都会被访问一次，所以时间复杂度是 \(O(n+e)\)
注意平时在表示线性复杂度时常常用 \(O(n)\) 指代，而这里 \(n\) 有特殊含义，而且有 \(O(n+e)\) 这个更为精确的选项，故答案为 A。

2020 csp-s1 T14

考察基本算法的时间复杂度。
Dijkstra 算法的流程为，从未确定 \(s\rightarrow u\) 最短路的点集 \({u}\) 中选取 dis[u] 最小的那一个，然后对其所有出边进行一次松弛操作。
每个【点】都要被选中一次，复杂度 \(O(n)\)。而每次选点的过程在朴素 Dijkstra 的实现中采用遍历求解，复杂度 \(O(n)\)。然后通过【出边】进行松弛，所有边加起来，复杂度 \(O(m)\)。
故总时间复杂度为 \(O(m+n^2)\)，而 \(m\leq C^2_n\)，故 \(O(m)=O(n^2)\)，总时间复杂度可以直接表示为 \(O(n^2)\)，选 B。

2020 csp-s1 T17

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

读懂程序后分析 swap() 的执行次数会更方便。
这段程序是快速排序的改版，用于找到序列中第 \(k\) 大的数。
采用分治法，由于快排每次会将序列分为两端，左边比指定的数 \(x\) 小，右边比指定的数大。
通过左区间长度可以推算出第 \(k\) 大的数与 \(x\) 的相对大小，然后递归到左右子区间中的一个求解。

本题中还会出现针对【随机数】的【平均复杂度】和【最坏复杂度】的概念，对于初赛来说，只需要进行复杂度的【估算】，因此可以不用管“平均”具体是谁和谁平均，每次选的随机数不要太极端就可以。而最坏复杂度可以无脑选最坏情况进行计算。

第三题，当 d[i] 递增的时候，每一轮的 swap() 只会做一次，此时时间复杂度就等于递归层数，这样估算的结果是 \(O(\log n)\)。
但官方答案是 \(O(\log^2 n)\)，估计还要进行一番严格推导，总之选一个小于 \(O(n)\) 的就行了。

第四题，当 d[i] 递减时，相当于第一轮的 swap() 每遇到一对 (a,b) 都会做一次，\(x\) 恰好取到中点时会做 \(\displaystyle\frac n2\) 次。
举例 7 6 5 4 3 2 1，取 d[x]=2，第一轮的变化过程为：
6 7 5 4 3 2 1
6 1 5 4 3 2 7
6 1 5 4 3 2 7
此时可以发现，第一轮做完之后数组处于乱序状态。
接着进到左右子区间中的一个后，最坏情况是依然递减，此时会操作 \(\displaystyle\frac n4\) 次。
所以操作次数可以估算为 \(\displaystyle\frac n2+\frac n4 + \cdots=2n\)，故时间复杂度为 \(O(n)\)。