1. 七级新增知识框架

• 三角函数、对数函数、指数函数。
• 二维 DP、DP 最值优化、区间 DP、LIS、LCS、滚动数组优化。
• 图的定义、BFS/DFS 遍历。
• Flood Fill。
• 哈希表及应用。

2. <cmath> 常用函数

函数	含义	典型说明
sin(x)	正弦	x 使用弧度
cos(x)	余弦
tan(x)	正切	注意定义域
asin(x)	反正弦	返回弧度
acos(x)	反余弦	acos(-1.0) 可得到 $\pi$
atan(x)	反正切	返回弧度
log(x)	自然对数	$\ln x$
log10(x)	常用对数	$\log_{10}x$
log2(x)	以 2 为底对数	$\log_2x$
exp(x)	指数函数	$e^x$
pow(a,b)	幂	$a^b$，浮点计算
floor(x)	向下取整	不大于 x 的最大整数
ceil(x)	向上取整	不小于 x 的最小整数
round(x)	四舍五入到最近整数值	返回浮点类型族结果

角度与弧度

$\text{radian}=\text{degree}\times\frac{\pi}{180}$

$\text{degree}=\text{radian}\times\frac{180}{\pi}$

const double PI = acos(-1.0);

3. 二维 DP

状态通常写为 dp[i][j]，必须明确两个维度分别代表什么。

一般复杂度：若有 $n\times m$ 个状态，每个状态 $O(1)$ 转移，则时间 $O(nm)$、空间 $O(nm)$。

4. 最长公共子序列 LCS

定义：两个序列中，保持原相对顺序但不要求连续的最长公共子序列。

状态：dp[i][j] 表示 A 前 i 个元素与 B 前 j 个元素的 LCS 长度。

转移：

• 若 $A[i-1] == B[j-1]$：$dp[i][j]=dp[i-1][j-1]+1$。
• 否则：$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$。

时间复杂度：$O(nm)$。

5. 最长上升子序列 LIS

基础 DP

状态：dp[i] 表示以第 i 个元素结尾的 LIS 长度。

$dp[i]=1+\max\{dp[j]\mid j<i, a_j<a_i\}$。

朴素时间：$O(n^2)$。

【辅助补充】二分优化

维护 tail[len]：长度为 len 的上升子序列可能的最小末尾值，通过二分可将时间降到 $O(n\log n)$。

6. 区间 DP

状态常写：dp[l][r] 表示区间 [l,r] 的答案。

关键顺序：先算短区间，再算长区间。

for (int len = 1; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        // 计算 dp[l][r]
    }
}

7. 滚动数组优化

若当前状态只依赖上一层，可把 $O(nm)$ 空间压到 $O(m)$。

核心不是“少开一维数组”，而是判断哪些旧状态在覆盖前还需要使用。

0/1 背包为什么倒序

倒序保证 dp[j-w] 仍是“上一件物品处理完”的状态；正序会在同一轮重复使用当前物品。

8. 图的基本概念

图 $G=(V,E)$：

• $V$：顶点集合。
• $E$：边集合。

分类	含义
无向图	边无方向
有向图	边有方向
有权图	边带权值
无权图	边无权或视为统一权重

有向图中：入度 = 指向该点的边数；出度 = 从该点发出的边数。

9. 图的存储

存储方式	空间	判断任意边	遍历某点邻边	适合
邻接矩阵	$O(V^2)$	$O(1)$	$O(V)$	稠密图/点少
邻接表	$O(V+E)$	通常需查邻接表	与度数相关	稀疏图/点边较大

10. 图的 DFS / BFS

采用邻接表时，一次完整 DFS/BFS 时间一般为 $O(V+E)$。

图 DFS

void dfs(int u) {
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v]) dfs(v);
}

图 BFS

queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) {
        if (!vis[v]) {
            vis[v] = true;
            q.push(v);
        }
    }
}

11. Flood Fill 泛洪算法

本质：从一个格子出发，用 DFS/BFS 找到所有连通、满足条件的格子，并统一标记。

四方向数组：

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

检查顺序：

1. 新坐标是否越界。
2. 是否满足可走/同色等条件。
3. 是否已访问。
4. 标记后入队/递归，避免重复进入。

12. 哈希表

哈希表用哈希函数将键映射到存储位置。

C++ 常用：

容器	用途	平均查找/插入/删除
unordered_set<T>	只存唯一键	期望 $O(1)$
unordered_map<K,V>	键值对

常用操作：

unordered_map<string, int> cnt;
cnt["abc"]++;
if (cnt.find("abc") != cnt.end()) { }
cnt.erase("abc");

注意：哈希表平均 $O(1)$，最坏情况可以退化，不应写成“绝对 $O(1)$”。

13. 七级必背易错点

1. sin/cos/tan 输入是弧度。
2. log(x) 是自然对数，不是以 10 为底。
3. LCS 是“子序列”，不要求连续；“子串”要求连续。
4. LIS 的 dp[i] 通常表示“以 i 结尾”，不是“前 i 个的全局答案”。
5. 区间 DP 要按区间长度递增。
6. 滚动数组覆盖顺序必须与依赖关系匹配。
7. 邻接矩阵和邻接表复杂度不同。
8. Flood Fill 要及时标记访问状态。

14. 七级背诵清单

• [ ] 三角/对数/指数函数及弧度换算。
• [ ] 二维 DP、LCS、LIS、区间 DP 状态定义。
• [ ] 滚动数组为什么能省空间。
• [ ] 图的度、邻接矩阵/邻接表。
• [ ] 图 DFS/BFS $O(V+E)$（邻接表）。
• [ ] Flood Fill 四步骤。
• [ ] unordered_map/unordered_set 的平均复杂度与常用操作。