Topic 1-4#

红黑树：根是黑的；叶子 (NIL) 是黑的；红节点的子节点必黑（不连续红）；从任一节点到其后代叶子的所有路径包含相同数目的黑节点

Topic7#

P/NP 概念类：

• P：多项式时间内能解决。欧拉回路
• NP：多项式时间内能验证这个解是否正确
• 约化：如果问题 A 可以在多项式时间内约化为问题 B，那么如果能解决 B，就一定能解决 A。B 的难度大于等于 A 的难度。记为 $A\leq_{p}B$。
  • 约化链：3-SAT（子语句是否为真）< 团问题 (无向图 G 中是否有完全子图 k) < 顶点覆盖（G 中是否有顶点子集，每个端点在子集中） < 哈密顿回路 < 旅行商问题 TSP
• NP-Hard：如果所有 NP 问题能在多项式时间内归约到 NP-Hard 问题。NP-Hard 不一定属于 NP
• NPC 问题：既是 NP 也是 NP-Hard。

近似算法

• 近似比：解的代价 C 与最优解的代价 C*的比值
• 常见近似算法：
  • 顶点覆盖：2-近似算法。任选一条边 (u, v)，将 u, v 都加入覆盖集 C，图中删去 u, v 相关联的所有边，重复直到没有边。该 C 是最优解 C 的至多两倍
  • 旅行商问题，满足三角不等式：2-近似算法。找到最小生成树，先序遍历，按先序遍历，直接跳到新点。证明：MST 权重 $\leq$ 最优 TSP 权重 $\leq$ 2 MST 权重（一去一回）
  • 子集覆盖问题：从子集 S 选出最少的集合，能覆盖全集的元素 U。贪心算法：每次选择能覆盖剩余元素个数最多的子集。近似比 $\ln n$。
• 近似方案：PO（多项式时间能找到最优解） ⊆ FPTAS （n 与误差倒数的多项式）⊆ PTAS（n 的误差倒数指数次方的多项式） ⊆ APX（常数近似） ⊆ log-APX ⊆ NPO

0/1 背包问题：伪多项式时间算法 $O(nW)$ W 为背包容量。多项式时间：运行时间是输入的比特位数 $O(\log W)$ 的多项式函数。伪多项式时间：是输入的数值的多项式函数

0-1 背包问题#

物体不可分时。物体可分：使用贪心

1. 状态定义：dp[i][w]：在容量为 w 的情况下，在只能从前 i 个物品选择中，能选到的最大价值
2. 状态转移：走到 i 物品时，若不拿 i 物品，则价值为 dp[i-1][w]。若拿走 i 物品，且背包装得下，则价值为 dp[i-1][w-w_i] + v_i。因此 $dp[i][w]=max(dp[i-1][w],dp[i-1][w-w_i]+v_i)$
3. 算法执行流程：填表法。初始化 0，外层循环遍历 0 到 i，内层循环遍历 0 到 w。若 w < w_i，则装不下， dp[i][w] = dp[i-1][w]。否则用上面式子取最大值。

最大子数和: Kadane 算法#

求解数组中最大连续子数组的和的最大值

1. 初始化：dp[i] 当前位置结束的位置和，maxSoFar 整个数组的和
2. 状态转移： dp[i] = max(nums[i], dp[i] + nums[i]) ：当前位置结束的和 = 前面数组与当前元素 + 从当前元素开始的和
3. maxSoFar = max(maxSoFar, dp[i])：全局最大和 时间复杂度：O (n)

1
def maxSubArray(nums):
2
   maxEndingHere = nums[0]
3
   maxSoFar = nums[0]
4
   for i in range(1, len(nums)):
5
       maxEndingHere = max(nums[i], maxEndingHere + nums[i])
6
       maxSoFar = max(maxSoFar, maxEndingHere)
7
   return maxSoFar
8
# 示例
9
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
10
print("最大子数组和为:", maxSubArray(nums)) # 输出: 6

LIS：最长递增子序列#

• 想法：最大递增序列 = max 以 i 结尾的最大递增序列。后者可以用 dp 表简单给出

1. 状态定义：dp[i] 表示以 i 结尾的最长递增子序列长度
2. 状态转移：对于 i，遍历 j = 0 到 i-1。若 a[i] > a[j]，则 dp[i] = 1 + max(dp[j])。

1
def lengthOfLIS(nums):
2
   if not nums:
3
       return 0
4
   dp = [1] * len(nums)
5
   for i in range(len(nums)):
6
       for j in range(i):
7
           if nums[i] > nums[j]:  # 这个条件可以变掉
8
               dp[i] = max(dp[i], dp[j] + 1)
9
   return max(dp)

1
import bisect
2
def lengthOfLIS(nums):
3
    tails = []
4
    for num in nums:
5
        idx = bisect.bisect_left(tails, num)  # bisect_left 寻找第一个 >= num 的位置
6
        if idx == len(tails):  # 如果位置等于当前长度，说明 num 比 tails 所有元素都大
7
            tails.append(num)
8
        else:   # 否则，替换掉该位置的元素，让该长度的子序列结尾更小
9
            tails[idx] = num
10

11
    return len(tails)

LCS：最长公共子序列#

给定 X 和 Y，找出共同的最长子序列

1. 状态定义：c[i,j] 表示 X 的前 i 个字符与 Y 的前 j 个字符最长公共子序列的长度
2. 状态转移：
   1. 若 x[i] == y [i] ：两字符相等，c[i,j] = c[i-1,j-1] + 1
   2. 若不等于，说明不能作为公共结尾。抛弃 x 的末尾和 y 的末尾看看。c[i,j] = max(c[i-1,j], c[i,j-1] ) 取最大值。若某一项为 0 则为 0（边界条件）

矩阵链乘法#

区间 DP：大区间的解是小区间合并出来的。初始化区间=1，先枚举区间长度 len，再枚举起点 i，最后计算终点 j。在区间内枚举分割点 k<len，寻找最优位置

矩阵链乘法：

1. 状态定义：m[i,j] 从 A_i 到 A_j 所需最少乘法数
2. 状态转移：$m[i,j]=min_{i\leq k<j}(m[i,k]+m[k+1,j]+p_{i}p_{j}p_{k})$. 其中 m[i,i] = 0。

最优搜索二叉树：有关键字 e1, e2… En 及其出现的概率 p1 p2 pn，构造二叉树使之查找效率最高。最优树的子树也是最优树，具有最优子结构

1. 状态定义：e[i,j] 表示 i 到 j 的最优搜索代价
2. 状态转移：$e[i,j]=min_{i\leq k<j}(e[i,k-1]+e[k+1,i]+w(i,j))$，w(i,j) 表示子树内所有概率的和。当选取根节点接入子树时，会使所有节点深度都加 1.

下面是习题课记的一些东西

状态转移和树与图#

一个公司有 n 个员工，每个员工（除了老板）都有一个直属上司。现在要举办一个晚宴，晚宴邀请到第 i 个员工会增加快乐值 vi，但是如果一个员工的直属上司来参加了，那么这个员工就无论如何也不肯来参加。问总的快乐值最大能够是多少。要求时间复杂度 O (n)。

上司舞伴问题：在图上的状态转移方程

最长链问题/最长链技术问题：求有向无环图中顶点数最多的路径长度和路径树？ 解：先用拓朴排序，然后计算 f[u] ：到达 u 最长链的长度

方案数：再用 g[u] 数组旧仍以一个点到 u 的最长链的条数，状态转移方程：

给定一张 n 个点 m 条边的有向图（不一定是 DAG）。每个点有权值。求一条路径，使路径经过的点权值之和最大。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。要求时间复杂度 O (n + m)。

强连通分量：如果经过强连通分量的一个点，则可以遍历强连通分量的任何点

贪心算法#

0/1 背包问题，要求设计一个近似比为 1/ 2 的贪心算法。要求时间复杂度为 O (n log n)。 每个物品有体积 $v_{i}$，价值 $w_{i}$，按价值密度从大到小排序物品，

分治#

给定平面上 n 个点，要求输出距离最短的两个点，时间复杂度 O （n lg n）

1. 预处理：按 x 坐标对所有点排序，得到数组 Px
2. 分治：用中位 x 将平面分为两半。递归计算左半边最小值 $\delta_{l}$ 和右半边 $\delta_{r}$，最小值记为 $\delta$
3. 跨越中线的最近点对：只考虑距离中线小于等于 $\delta$ 的点，组成集合 S，将 S 按 y 轴排序。对于 S 中每个点，只和前后 k 个点进行比较。可证明 k 是常数

1
solve(r,l):
2
  solve(r,mid)
3
  solve(mid,l)