不会的练习题前面加 *。
阅读计划：（Y 阅读，T 练习）
2 月：数学基础（Y, T），分治策略（Y + T），中位数（Y + T），动态规划（Y + T），贪心（Y + T）
3 月：摊还分析（Y, T），不相交集合的数据结构（Y, T）
4 月：基本图算法（Y, T），最小生成树（Y, T），单源最短路（Y, T）
5 月：线性规划（Y, T），数论（Y, T）
0.数学基础
A.求和
-
级数： \(\sum_{i = 1}^{+ \infty} a_i\) 称作一个无穷级数，而 \(\sum_{i = 1}^n\) 称作一个有限级数。当 \(\lim_{n \to +\infty} {\sum_{i = 1}^{n} a_i}\) 存在时，该级数收敛，否则该级数发散。无穷级数的求和不能改变顺序。
-
无穷递减级数： 其中 \(a_i = x^i\)，此时有 \(\sum_{i = 1}^n a_i = \sum_{i = 1}^n x^i = \frac{x^n - 1}{x - 1}\)。同时，当 \(|x| \le 1\) 时 \(\sum_{i = 1}^{+\infty} x^i\) 收敛，且等于 \(\frac{1}{1 - x}\)。
-
调和级数： 其中 \(a_i = \frac{1}{i}\)，且 \(\sum_{i = 1}^n \frac{1}{i} = \ln n + O(1)\)。\(\sum_{i = 1}^{+\infty} \frac{1}{i}\) 不收敛。
还有一些常见的级数：
\(\sum_{i = 1}^n i x^i = \frac{x}{(1-x)^2}\)
\(\sum_{i = 1}^n Fib_x x^i = \frac{1}{x^2 - 3x + 1}\)
求法都是微分后乘上一些 \(x, x^2\) 之类的。（即错位相减）
求 准确和 技巧：
-
裂项相减：eg. \(\sum_{i = 1}^n \frac{1}{k(k + 1)}\)。
-
乘积化求和：\(\log(\prod a_i) = \sum \log(a_i)\)。
-
利用已知级数配凑
求 和上界 技巧：
-
数学归纳法：
与常用的数学归纳法不同，我们不需要为了使用归纳法而去猜出和的上界，而是猜出和的上界的 数量级 即可。
e.g.：求 \(\sum_{i = 1}^n 3^i\) 的上界。
猜测该和式的上街为 \(O(3^n)\)，设一个常数 \(c\) 但不必写出准确值，并且尝试说明 \(\sum_{i = 1}^n 3^i \le c3^n\)。当 \(n = 1\) 时，只需要 \(c \ge 1\) 即可。设已经有 \(\sum_{i = 1}^{n - 1} \le c3^{n - 1}\)，则：\(\sum_{i = 1}^n \le c3^{n - 1} + 3^n = (1 + \frac{c}{3}) 3^n\)。当 \(c \ge 1 + \frac{c}{3}\) 时成立，于是取任意 \(c \ge \frac{3}{2}\) 即可。
-
无穷递减级数拟合：
有的时候我们可以证明出级数相邻两项的比值小于某个小于 \(1\) 的常数，因此我们可以将该级数的上界看作一个无穷递减级数。
e.g. 求 \(\sum_{i = 1}^{+\infty} \frac{k}{3^k}\) 的上界。
注意到当 \(i \ge 1\) 时，有 \(\frac{(k + 1)3^k}{k3^{k + 1}} \le \frac{2}{3}\)，因此我们可以将其上界看作 \(\frac{1}{3} \sum_{i = 0}^{+\infty} (\frac{2}{3})^i = 1\)。
注意： 一定要存在一个 确切 的常数，比如 \(\sum_{i =1}^{+\infty} \frac{1}{i}\) 邻项比值 \(\frac{i}{i + 1}\) 虽然 \(< 1\)，但是并不存在确切的 \(< 1\) 的常数 \(c\) 满足 \(\frac{i}{i + 1} < c\)。
-
分割求和：
将级数分为若干部分求和，并分别求得上界以提高精度。
e.g. 求 \(\sum_{i = 1}^n \frac{1}{i}\) 的上界。
考虑将原式分为 \(\log n + 1\) 段，分别为 \([\frac{1}{2^i}, \frac{1}{2^{i + 1}})\)，将每一段的数均看作 \(\frac{1}{2^i}\)。于是有 \(\sum_{i = 1}^n \frac{1}{i} \le \sum_{i = 1}^{\log n + 1} \frac{1}{2^i} 2^i = \log n + 1\)。
A. 1 - 2
证明：\(\sum_{i = 1}^n \frac{1}{2i - 1} = \ln(\sqrt n) + 1\)。
A. 1 - 3
证明：\(\sum_{i = 1}^{+\infty} k^2 x^k = \frac{x(1 + x)}{(1 - x)^3}\)。
于是有 \(S = \frac{x(x + 1)}{(1 - x)^3}\)。
A. 1 - 4
证明：\(\sum_{i = 0}^{+\infty} \frac{k - 1}{2^k} = 0\)。
证该式即证 \(S = \sum_{i = 1}^{+\infty}{\frac{i}{2^{i + 1}}} = 1\)。
A. 2 - 1
证明： \(\sum_{i = 1}^n \frac{1}{i^2}\) 有常数上界。
B.离散数学
定义大多是图论内容。
B - 1
*d.
证明：图 \(G = (V, E)，|E| = O(|V|)\)，则该图的着色数为 \(O(\sqrt |V|)\)。
考虑如下引理：
一张图的着色数 \(> k\)，当且仅当存在一个导出子图，满足该子图的最小度数 \(\ge k\)。
Proof:
若没有子图的最小度数 \(\ge k\)，则考虑每次删去一个度数 \(< k\) 的点，必然可以删空整张图。按删去顺序的逆序染色，每次找到当前点已经染色的邻域点的 \(\mathrm {mex}\) 并将该点染成该颜色。
利用引理，当色数大于 \(O(\sqrt |V|)\) 时，边数必然要大于 \(O(|V|)\)，因此着色数最多为 \(O(\sqrt |V|)\)。
B - 2
*b.
证明：一个有 \(6\) 个点的无向图中至少有 \(3\) 个点是互相有边相连或者互相没有边相连的。
将原图中的边染成红色，不在原图中的边连接上并染成蓝色。原问题可以转述为图中有一个蓝色三元环或红色三元环。选择一个点，剩余 \(5\) 个点中必然有 \(3\) 个点同色，不妨设为蓝色，则 \(3\) 个点中有 \(2\) 个点连红边就构成了红色三元环，否则三个点之间构成蓝色三元环。
*c.
证明：一张无向图顶点集合 \(V\) 可以分为两个集合 \(V_1, V_2\)，满足 \(u \in V_x, \sum_{v \in V_{3 - x}} E_{u, v} \ge \frac{1}{2} \sum_{v \in V} E_{u, v}\)，其中 \(E_{u, v}\) 是 \(u, v\) 是否有连边。
极端原理。
考虑最大割的划分 \(C = (V_1, V_2)\) 产生的 \(V_1, V_2\) 之间的连边数量 \(T = \sum_{u \in V_1, v \in V_2} E_{u, v}\)。考虑存在一个点 \(u \in V_1\) 违反条件，即 \(u\) 满足 \(\sum_{v \in V_2} E_{u, v} \le \frac{1}{2} \deg_u\)，那么将 \(u\) 移动到 \(V_2\)，\(T\) 的变化量为 \(\deg_u - 2\sum_{v \in V_2} E_{u, v}\)，该值为正数，与 \(T\) 最大的假设矛盾，证毕。
d.
证明：一张无向图 \(G = (V, E)\) 存在哈密顿回路的一个充分条件为：\(\forall u \in V,\deg_u \ge \frac{1}{2} |V|\)。
反证法。设走了 \(x_1, x_2 ..., x_k\) 后 \(x_k\) 的邻居都被走过了，则由于 \(\deg_u \ge \frac{1}{2} |V|\)，于是由鸽巢原理得 \(x_{1...k}\) 中至少存在两个点 \(x_i, x_{i + 1}\) 均为 \(x_k\) 的邻居。将 \(x_k\) 插在中间即可。证毕。