基于
kotori-luogu-backup.json生成 错题 6 题 + 重点题 16 题（P1433 重叠）= 共 21 道
P1433、P3811、P1095、P1140、P2761、P1080
P3143、P4147、P4391、P8306、P1605、P1731、P1588、P1162、P1433、P1113、P1833、P2196、P1020、P1044、P2622、P1031
| 主题 | 题数 | 题号 |
|---|---|---|
| DP（动态规划） | 8 | P1140、P1095、P3811、P1020、P1044、P1833、P1113、P2196 |
| DFS / 搜索剪枝 | 3 | P1731、P1605、P1433 |
| BFS / Flood Fill | 2 | P1162、P1588 |
| 字符串（KMP/Trie） | 2 | P4391、P8306 |
| 贪心 + 分治 | 2 | P3143、P1031 |
| 状压 DP | 1 | P2622 |
| 单调栈 | 1 | P4147 |
| 贪心 + 高精度 | 1 | P1080 |
| 图论 + DP | 1 | P2761 |
核心结论：DP 类题目占了近一半，且错题中 3/6 是 DP。DP 是当前最薄弱也最值得攻克的区域。
类型：双序列 DP / 序列对齐（LCS 变体）
核心思路：
- 状态：f[i][j] = 字符串 a 前 i 位与字符串 b 前 j 位对齐时的最大得分
- 转移：三种最后一步
- a[i] 对 b[j]：f[i-1][j-1] + tab[a[i]][b[j]]
- a[i] 对空位 -：f[i-1][j] + tab[a[i]][-]
- 空位 - 对 b[j]：f[i][j-1] + tab[-][b[j]]
易错提醒（你的两次错都在这里）：
1. 初始化不统一：必须填满整行 f[0][j]（a 为空，b 用 j 个 - 补全）和整列 f[i][0]（b 为空，a 用 i 个 - 补全），不能只设 f[0][1] 和 f[1][0]
2. 状态转移含义混淆：
- f[i-1][j] 意思是 a 前 i-1 位 vs b 前 j 位已对齐，现在新增 a[i] 配 -
- f[i][j-1] 意思是 a 前 i 位 vs b 前 j-1 位已对齐，现在新增 - 配 b[j]
3. 不可达态要设成 -∞（你笔记里写的 -2e8），不能用 0，否则会和有效得分混淆
关键词：序列 DP、对齐、罚分表、- 补位
类型：批量线性递推（不是逐个快速幂）
你的错误：用快速幂对 1~n 每个数单独求 → O(n log p)，超时
正确思路：线性递推 DP
$$\text{inv}[i] = -\lfloor p/i \rfloor \cdot \text{inv}[p \bmod i] \bmod p$$
- 复杂度 O(n)
- 推导：从 p = ⌊p/i⌋·i + (p mod i) 出发模 p
易错提醒：
1. 看到"求 1~n 所有数的逆元"这种批量词眼，要立刻想到线性递推
2. 实现中负数取模要 +p 防止结果为负
关键词：批量、1~n、线性递推
类型：双决策状态机 DP
你笔记为空，必须补：
核心思路：
- 每秒只能做一件事：闪烁（消耗 10 魔法，前进 60 米）或跑步（前进 17 米）或休息（恢复 4 魔法）
- 状态：f[t] = t 秒能到达的最远距离；同时需要追踪剩余魔法
- 实现：循环 t，每秒分两阶段——先决定是否能闪烁、再决定是否前进或休息
易错提醒： 1. 贪心陷阱：不能简单"魔法够就闪烁"，要考虑魔法不够时是该跑还是该等 2. 注意提前终止：到达 T 或距离 ≥ M 即可输出 3. 两阶段判断顺序不能反
关键词：守望者、双策略、时间循环
类型：状压最短路（Dijkstra on bit-mask states）
你笔记为空，必须补：
核心思路：
- 把 bug 集合压缩成二进制状态 s（每位表示某 bug 是否存在）
- 每个补丁是状态转移边：需要满足"必须含某些 bug、不能含某些 bug"，作用是"修掉某些 bug、新增某些 bug"
- 跑 Dijkstra：从全 1 状态（所有 bug 存在）到全 0 状态
易错提醒：
1. 状态数最多 2^n，n ≤ 20，注意空间
2. 补丁的前置/作用条件用两个位掩码表示（"必须含的位"和"不能含的位"），判断时用位与
3. 不可达要输出 0（视题目而定）
关键词：状压最短路、bug 位掩码、补丁建图
类型：贪心排序 + 高精度运算
你笔记为空，必须补：
核心思路：
- 排序贪心：按 a[i] * b[i] 升序排
- 证明：交换相邻两人不变优时，可推出此排序
- 答案：最大的 (前缀积 / b[i])，用高精度
易错提醒（结合你思考空间 #11、#12 的高精度坑）：
1. 比较器：BigInt::operator< 必须从最高位（数组末尾）开始比较，相等返回 false
2. operator< 必须加 const 修饰
3. 高精度除法要清空构造函数残留的 0
4. 排序键是乘积，不是 a 或 b 单独——很多人栽在这里
关键词：贪心、相邻交换、高精度除法
类型：状压 DP / 旅行商问题
核心思路：
- 状态：f[s][i] = 已经吃了集合 s 中的奶酪、当前在第 i 块奶酪的最短路径
- 转移：f[s | (1<<j)][j] = min(f[s][i] + dis(i,j))
- 答案：min(f[(1<<n)-1][i]) for all i
易错提醒：
1. 距离用 double，比较时小心精度
2. 起点是原点 (0,0)，要单独处理第 0 步
3. n ≤ 15，状态 2^n * n 不大，但常数要控制
关键词：TSP、状压 DP、欧几里得距离
类型：DFS + 多重剪枝（你笔记里写了完整的十节心法）
核心思路：
- 按层决策 (r, h)，dfs 参数：剩余层数 m、剩余体积 n、半径上界 r、高度上界 h、当前面积 s
- 终止：m == 0 && n == 0
四大剪枝：
1. 体积下界：minV[m] = Σi³，若 n < minV[m] 剪
2. 面积下界：minS[m] = 2Σi²，若 s + minS[m] ≥ ans 剪
3. 单位代价：剩余面积 ≥ 2n/r，若 s + 2n/r ≥ ans 剪
4. 枚举范围收缩：从源头限制 r、h 上界
易错提醒：
1. DFS 参数传"上界"而非"当前值"，循环在内部枚举
2. 只有最底层加底面积 r²，其他层只加侧面积 2rh
3. 终止条件看状态语义："还剩多少"→ 到 0；"做到第几"→ 到 n
关键词：按层决策、未来代价下界、剪枝
类型：DFS 计数 + visited 自管理
核心思路：从起点出发数到终点的路径数
易错提醒（你的核心心得）： - visited 管理模式："当前点只处理自己，子节点留给进入子节点层次时他自己处理" - 顺序：进入 → 标记自己 → 拓展周围（不标记子节点）→ 拓展完成 → 撤销自己标记 - 全程不去动子节点的 visited 状态
代码片段（你的版本）：
void dfs(int x, int y) {
if (x == fx && y == fy) { ans++; return; }
visited[x][y] = true;
for (拓展四个方向) {
if (合法 && !visited[nx][ny]) dfs(nx, ny);
}
visited[x][y] = false; // 回溯
}
关键词：DFS 回溯、visited 数组、路径计数
类型：边界 Flood Fill
核心思路： - 从边界的 0 出发 BFS，把所有连通的 0 染成"外部" - 剩下的 0 就是被 1 围起来的"内部"
易错提醒： 1. 从边界开始（而不是从内部找），这样能区分内外 2. 注意题目要求把"内部 0"染成 2，外部 0 还原 3. 四方向 BFS 即可，不需要八方向
关键词：flood fill、边界 BFS、内外区分
类型：一维数轴 BFS / 状态空间搜索
核心思路：
- 每个位置三种转移：x-1、x+1、2*x
- 用 BFS 求最少步数
易错提醒：
1. 范围要够大（一般开到 2*max 防止 2*x 越界）
2. visited 要标记访问过的位置
3. 不要忘了起点 == 终点的边界情况
关键词：一维 BFS、状态转移图
类型：枚举分界点 + 前后缀预处理
核心思路（你笔记的精华）：
1. 排序后用双指针/二分找每个位置 i 能选的最长合法长度 lenv[i]
2. 后缀最优：best[i] = max(best[i+1], lenv[i]) —— 要么不选 i，要么选 i
3. 枚举分界点 k：ans = max(lenv[i] + best[next_pos])
易错提醒（你笔记的关键洞见）：
- 看到"分为两不相交部分"立刻想到枚举分界点+分治
- best 数组的含义："从位置 i 开始的最优解"——要么从 i 开始选，要么跳过 i
关键词：双指针、后缀最大、分界枚举
类型：二维问题压缩为一维 + 单调栈
核心思路（你笔记的精华）： - 二维压缩为一维：对每一行预处理"以该格为底，向上能延伸多高"，得到柱状图 - 对每个柱状图跑单调栈求最大矩形面积
易错提醒：
1. 单调栈实现要注意"左边第一个更小"和"右边第一个更小"的处理
2. 注意题目可能要求矩形面积乘 3（最大子矩阵的"价值"）
3. 高度数组累加：当前格是 F 则 h[j]++，否则 h[j] = 0
关键词：柱状图、单调栈、二维降维
类型：KMP next 数组应用
核心思路（你笔记的精华）：
- 对于长度为 n 的字符串 s，最小周期候选 = n - next[n]
- 当 n % p == 0 时，s 是 p 的完整周期重复
- 原理：1~p 与 n-p+1~n 这段由 KMP 失配数组的性质保证相同
易错提醒：
1. 本题只需输出 n - next[n]（无需判断 n%p == 0，因为题目保证答案存在）
2. KMP 的 next 数组下标从 1 开始时 next[1] = 0
关键词：KMP、最小循环节、n - next[n]
类型：Trie 模板 + 前缀经过次数
核心思路（你笔记的精华）：
- cnt[p] 记录的是经过该节点的字符串数量，而不是在该节点结束的字符串个数
- 这样查询"以某字符串为前缀的数量"时，沿着 Trie 走到末位读 cnt 即可
易错提醒： 1. 多测要 memset，复杂度算清楚 2. 节点编号从 1 开始 3. 注意大小写字母 + 数字的字符映射
关键词：Trie、前缀计数、cnt[p] 语义
类型：拓扑排序 + 树形/DAG DP
核心思路（你笔记的精华）：
- 任务有明确前置 → 拓扑排序
- 同层任务可并行（木桶效应）→ 用 max 更新
- f[u] = u 自身耗时 + max(f[v] for v 是 u 的前置)
易错提醒：
1. 答案是所有 f[u] 的最大值，不是最后一个节点
2. 入度为 0 的节点是起点，初始 f[u] = time[u]
3. 注意拓扑序遍历，前驱要先算完
关键词：拓扑排序、max 更新、木桶效应
类型：01 + 完全 + 多重背包混合
核心思路： - 时间转分钟当作背包容量 - 不同种类樱花对应三种背包：限定次数（多重）、无限次（完全）、一次（01） - 多重背包用二进制拆分优化
易错提醒：
1. 完全背包正序，01 背包倒序，多重拆完后按 01 处理（倒序）
2. 时间计算：可能跨过 0 点，注意取模
3. 注意 T = 0 表示无限次（即完全背包）
关键词：混合背包、二进制拆分、时间转分钟
类型：有向无环图最长路径
核心思路：
- f[i] = 从节点 i 出发能挖到的最大地雷数
- 转移：f[i] = w[i] + max(f[j]) for j 是 i 能到达的节点
- 倒序计算（因为依赖后面）
易错提醒：
1. 记录路径：用 nxt[i] 数组记下转移到哪个 j，输出时回溯打印
2. 注意答案路径需要从 max(f[i]) 的起点开始追
3. 输出格式：节点编号用 - 或空格连接（按题目要求）
关键词：DAG DP、路径记录、回溯输出
类型：最长不上升子序列 + Dilworth 定理
核心思路（你笔记的精华）： - 第一问：最长不上升子序列长度 - 第二问：最少分组数——根据 Dilworth 定理 = 最长严格上升子序列长度 - 大白话：序列里"互相排斥"（满足不能同组规则）的元素最多有几个，就最少需要几组
易错提醒（你笔记的关键洞见）：
1. 同长度元素的处理：若两元素长度相同，按重量降序排，防止 LIS 误判为"递增"
2. 不上升 vs 不下降 vs 严格上升 vs 严格下降 容易混，做之前先用 1~2 个例子手算
3. n 大时必须用 O(n log n) 优化（q[len] 维护长度为 len 的子序列结尾最小值，二分插入）
O(n log n) LIS 核心代码：
int len = 0;
for (int i = 1; i <= n; i++) {
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q[mid] < a[i]) l = mid; else r = mid - 1;
}
q[r + 1] = a[i];
len = max(len, r + 1);
}
<，不下降用 <=关键词：LIS、Dilworth 定理、不上升 / 严格上升
类型：栈出栈序列计数
核心思路：
- 方法一：卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$
- 方法二：DP，f[i][j] = 已入栈 i 个、栈中还有 j 个 时的方案数（你思考空间 #8 里详细推过）
- push：f[i+1][j+1] += f[i][j]
- pop：f[i][j-1] += f[i][j]
易错提醒：
1. 起点 f[0][0] = 1
2. 答案是 f[n][0]
3. DP 转移如果用"推式"（同层 j → j-1），j 要倒序
关键词：卡特兰数、栈序列、二维 DP
类型：状压 + BFS / Dijkstra
核心思路：
- 状态：每盏灯的开关用二进制位表示，共 2^n 个状态
- 每个开关是状态转移：枚举每位检查"开/关/翻"
- BFS 求从初始状态（全 1）到全 0 的最少步数
位运算四件套（你笔记的精华）：
查询：if ((s >> j) & 1)
打开：s |= (1 << j);
关闭：s &= ~(1 << j);
翻转：s ^= (1 << j);
易错提醒：
1. 同一开关对不同灯的作用不同（开/关/不影响），实现时要分情况
2. 状态空间最大 2^n，n ≤ 10 不会爆
3. BFS 每条边权为 1，无需 Dijkstra
关键词：状压、位运算、BFS 最少步数
类型：贪心 / 前缀和
核心思路：
- 算出平均值 avg，每堆减去 avg 得到差值数组 b
- 从左到右扫，若 b[i-1] != 0 则需要一次移动，并把 b[i-1] 累加到 b[i]
易错提醒（你笔记的关键）：
// ✅ 正确
for (int i = 1; i <= n; i++) {
if (b[i - 1] != 0) {
cnt++;
b[i] += b[i - 1];
}
}
// ❌ 错误（判断的是 b[i] 而非 b[i-1]）
if (b[i] != 0) { ... }
判断对象必须是前一个位置是否需要移动，而非当前位置。
关键词：贪心、前缀累加、差值传递
你已经写过 8 条 DP 元笔记（建模、初始化、循环顺序、数组建立、排列vs组合…），但仍在 P1140 上栽。
修复方案（强制 4 步流程）：
1. ✍️ 用完整中文写状态定义（不能只写"表示最优值"）
2. ✍️ 画依赖箭头（f[A] ← f[B]）
3. ✍️ 推导初始化（"空"状态是真的吗？）
4. ✍️ 决定循环方向（看箭头起点先算完）
operator< 必须 constfalse< 得大根堆）建议：整理一份标准 BigInt 模板，永远不再手写。
cin >> 和 getline 混用残留换行符。
口诀：空白无意义用 cin >>；整行有意义用 getline；类型混合先读 string token；行内再分析用 stringstream。
| 优先级 | 任务 |
|---|---|
| 🔴 高 | 补完 P1433、P1095、P1080、P2761 的错因记录到错题本 |
| 🔴 高 | P1140 重做一遍，严格按"完整中文定义状态"流程走 |
| 🟡 中 | 把高精度 BigInt 整理成可复用模板，加入个人 snippets |
| 🟡 中 | DP 类题做之前先动笔再动键盘——这是效率最大瓶颈 |
| 🟡 中 | P3811 重做，体会"批量"关键词对应线性递推 |
| 🟢 低 | 状压、KMP、Trie 你已经摸到门道了，二刷时直接看自己的 starNotes |
按以下顺序二刷，每题做完再看本文档对应分析：
生成时间：基于 kotori-luogu-backup.json，作者：Kotori + Claude Opus 4.7