2026/4/18/CQY笔记(LCS+模拟练习)
算法基础核心知识点课堂复习笔记
一、最长上升子序列（LIS）
1. 核心定义
- 全称：Longest Increasing Sequence，最长递增子序列
- 定义：对于一个长度为n的数组，选出一个子序列（元素相对顺序不变，不要求连续），满足子序列中元素严格递增，这个子序列的最大长度即为LIS长度。
- 补充：非严格递增场景只需把判断条件从
>改为>=即可。
2. 基础DP解法（O(n²)）
状态设计
dp[i]：表示以数组第i个元素为结尾的最长上升子序列的长度。
状态转移方程
dp[i] = 1; // 初始值：每个元素自身就是长度为1的子序列
for (int j = 1; j < i; j++) {
if (a[i] > a[j]) { // 满足递增条件
dp[i] = max(dp[i], dp[j] + 1);
}
}
最终答案
整个数组的LIS长度 = max(dp[1], dp[2], ..., dp[n])
3. 优化解法（贪心+二分，O(nlogn)）
- 适用场景：n ≤ 1e5的大数据场景，O(n²)解法会超时
- 核心思路：维护
low数组，low[k]表示长度为k的上升子序列的最小结尾元素；遍历数组时用二分更新low数组，最终low数组的有效长度即为LIS长度。 - 复习重点：该优化是排列LCS问题的核心优化基础，必须掌握。
二、最长公共子序列（LCS）
1. 核心定义
- 全称：Longest Common Subsequence，最长公共子序列
- 定义：给定两个序列s1、s2，选出一个同时是s1和s2的子序列（元素相对顺序不变，不要求连续），这个子序列的最大长度即为LCS长度。
- 排列补充定义：长度为n的排列指数组中1~n每个数字恰好出现一次，顺序任意。
2. 基础DP解法（O(n*m)）
状态设计
dp[i][j]：s1的前i个字符/元素 与 s2的前j个字符/元素 的最长公共子序列长度
- 注：i范围0~n（n=s1.size()），j范围0~m（m=s2.size()）；i=0表示s1前0个元素（空序列），j=0同理。
状态转移方程
分两种核心情况：
-
当s1[i] == s2[j]时
dp[i][j] = dp[i-1][j-1] + 1;- 逻辑：当前两个元素相等，必然可以加入公共子序列，因此在两个序列都去掉当前元素的LCS长度基础上+1。
-
当s1[i] != s2[j]时
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);- 逻辑：当前两个元素不相等，无法同时加入公共子序列，因此取「去掉s1第i个元素的LCS长度」和「去掉s2第j个元素的LCS长度」中的最大值。
边界条件
dp[i][0] = 0; // 任意序列和空序列的LCS长度都是0
dp[0][j] = 0;
- 初始值说明：LCS求最大值，边界初始为0，转移过程数值非递减，无需额外赋极小值。
最终答案
两个完整序列的LCS长度 = dp[n][m]（n为s1长度，m为s2长度）
3. 特殊场景优化：两个排列的LCS问题
题目限定条件
- 给定两个长度为n的排列P1、P2，其中P2是严格递增排列
P2 = [1,2,3,...,n] - 数据范围：n ≤ 1e4（基础O(n²)DP会超时，必须优化）
优化核心思路
将排列的LCS问题转化为LIS问题，时间复杂度降至O(nlogn)
- 建立映射：对P1中的每个元素，记录其在P1中的位置，即
pos[x] = 元素x在P1中的下标 - 构建新数组：遍历P2，将每个元素x替换为
pos[x]，得到新数组arr - 求解：arr的LIS长度，即为P1和P2的LCS长度
- 原理：P2是递增的，因此公共子序列在P2中必然递增，对应到arr中就是位置递增，即LIS。
4. 易错点&复习重点
- 下标问题：建议i、j从1开始，避免i-1越界，务必区分数组0起始和1起始的差异。
- 概念混淆：LCS是子序列（不要求连续），不要和最长公共子串（要求连续）的DP方程混淆。
- 空间优化：基础DP可优化为一维数组，因为dp[i][j]仅和上一行、当前行前一个元素有关。
- 大数据场景：n≥1e3时优先考虑优化解法，避免O(n²)超时。
三、最短编辑距离（Edit Distance）
1. 核心定义
- 定义：给定两个字符串a和b，通过「删除、插入、替换」三种操作，将字符串a修改为字符串b，所需的最少操作次数，即为最短编辑距离。
- 补充：插入和删除是对称操作，删除a的一个字符等价于给b插入一个字符。
2. DP解法核心框架
状态设计
dp[i][j]：把字符串a的前i个字符，修改为和字符串b的前j个字符完全一致，所需的最少操作次数
- 注：i范围0~n（n=a.size()），j范围0~m（m=b.size()）
状态转移方程
分两种核心情况：
-
当a[i] == b[j]时
dp[i][j] = dp[i-1][j-1];- 逻辑：当前两个字符已经相等，无需任何操作，直接继承两个字符串都去掉当前字符的最小操作次数。
-
当a[i] != b[j]时 有三种合法操作，取操作次数的最小值：
dp[i][j] = min( dp[i-1][j] + 1, // 操作1：删除a的第i个字符 dp[i][j-1] + 1, // 操作2：给a插入一个字符（等价于删除b的第j个字符） dp[i-1][j-1] + 1 // 操作3：将a的第i个字符替换为b的第j个字符 );- 操作1详解：删除a[i]后，a的前i-1个字符需要匹配b的前j个字符，操作次数为dp[i-1][j] + 1。
- 操作2详解：给a插入和b[j]相等的字符后，a的前i个字符需要匹配b的前j-1个字符，操作次数为dp[i][j-1] + 1。
- 操作3详解：替换a[i]为b[j]后，两个字符相等，只需继承dp[i-1][j-1] + 1。
边界条件
dp[0][0] = 0; // 空串修改为空串，操作次数为0
dp[i][0] = i; // a的前i个字符修改为空串，需要i次删除操作
dp[0][j] = j; // 空串修改为b的前j个字符，需要j次插入操作
- 初始值要求：因为求最小值，dp数组需要先初始化为一个极大值（如1e9），再给边界赋值，避免最小值被错误初始值覆盖。
最终答案
将a完整修改为b的最少操作次数 = dp[n][m]（n为a长度，m为b长度）
3. 核心正确性证明
问题：为什么当a[i] == b[j]时，dp[i][j] = dp[i-1][j-1] 一定是最优的？
证明过程（最优子结构+反证法）
- 最优子结构前提：最短编辑距离问题满足最优子结构——即dp[i][j]的最优解，必然包含其子问题dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]的最优解。
- 当a[i] == b[j]时，我们有两种选择：
- 选择1：不操作a[i]和b[j]，此时dp[i][j] = dp[i-1][j-1]
- 选择2：对a[i]或b[j]进行操作（删除/插入/替换），此时操作次数至少为dp[][] + 1，必然大于等于选择1的结果。
- 反证法：假设存在一种操作方式，使得dp[i][j] < dp[i-1][j-1]，那么意味着我们可以用更少的操作次数完成匹配，这与dp[i-1][j-1]是子问题的最优解矛盾。
- 结论：当a[i] == b[j]时，不进行任何操作，直接取dp[i-1][j-1]，一定是当前状态的最优解。
4. 易错点&复习重点
- 初始值问题：求最小值必须先给dp数组赋极大值，再设置边界条件，否则会出现最小值为0的错误。
- 下标越界：i和j从1开始遍历，避免i-1或j-1为负数。
- 操作混淆：务必区分三种操作对应的状态转移，不要混淆dp[i-1][j]和dp[i][j-1]的含义。
- 空间优化：可优化为一维数组，需注意遍历顺序和临时变量保存。
四、环形数组经典模板（新猴王问题）
1. 问题描述
n只猴子围成一个环形，每只猴子有初始生命值，从第1只猴子开始循环报数，报到m的猴子生命值-1；若生命值变为0，则该猴子被淘汰，剩余猴子继续报数，直到只剩1只猴子，即为新猴王。
- 核心考点：环形数组的模拟方法，是约瑟夫环问题的通用变种模板。
2. 代码模板（带逐行注释）
#include <iostream>
using namespace std;
int main() {
int n, m, a[30];
// 输入猴子数量n
cin >> n;
// 输入每只猴子的初始状态，转换为生命值a[i]
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] = 2 - a[i]; // a[i]表示猴子的剩余生命值
}
// 输入报数上限m
cin >> m;
// 核心变量定义
int p = 0; // p：当前指向的猴子位置（环形数组下标）
int bs = 0; // bs：当前已经报的数字
int sy = n; // sy：当前剩余的猴子数量
// 循环淘汰，直到只剩1只猴子
while (sy > 1) {
p++; // 移动到下一只猴子
if (p == n + 1) p = 1; // 环形处理：到末尾后回到开头
if (a[p] > 0) { // 只有存活的猴子才能参与报数
bs++; // 报数+1
if (bs == m) { // 报到指定数字m
a[p]--; // 生命值-1
if (a[p] == 0) sy--; // 生命值归零，猴子淘汰，剩余数量-1
bs = 0; // 报数重置，从下一个猴子重新开始
}
}
}
// 输出剩余的猴王编号
for (int i = 1; i <= n; i++) {
if (a[i] > 0) {
cout << i << endl;
break;
}
}
return 0;
}
3. 环形数组核心处理技巧
- 下标循环法：数组下标从1到n，当
p == n+1时直接置为1，实现环形遍历，无需复杂取模，适合新手理解。 - 取模优化法：
p = (p % n) + 1，可替代if判断，实现同样的环形效果，适合代码精简场景。 - 存活判断：遍历过程中必须判断当前猴子是否存活，只有存活的猴子才能参与报数，避免淘汰的猴子占用报数位置。
4. 易错点&复习重点
- 下标起始：猴子编号从1开始，避免从0开始导致编号输出错误。
- 报数重置：只有报到m的时候才重置报数器bs，不要在其他位置错误重置。
- 剩余数量更新：只有当猴子生命值归零的时候，才减少剩余数量sy，不要每次减生命值都更新。
- 环形边界：务必处理p的越界问题，避免数组下标越界崩溃。
五、日期差值计算问题
1. 问题描述
给定两个合法的日期（年-月-日），计算两个日期之间相差的天数，核心考点是闰年判断、月份天数处理、跨年月计算。
2. 核心前置知识
闰年判断规则
闰年2月有29天，平年2月有28天，闰年判断公式：
bool isLeap(int year) {
// 能被4整除但不能被100整除，或者能被400整除的年份是闰年
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
月份天数表
| 月份 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 天数 | 31 | 28/29 | 31 | 30 | 31 | 30 | 31 | 30 | 31 | 30 | 31 | |
3. 解法一：逐日模拟法
核心思路
从较早的日期开始，一天天向后累加，直到到达较晚的日期，累计的总天数即为两个日期的差值。
代码模板（带注释）
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 闰年判断
bool isLeap(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
// 获取当月的最大天数
int getMaxDay(int year, int month) {
if (month == 2) {
return isLeap(year) ? 29 : 28;
}
// 大月31天，小月30天
int bigMonth[] = {1,3,5,7,8,10,12};
for (int m : bigMonth) {
if (month == m) return 31;
}
return 30;
}
int main() {
string s1, s2;
cin >> s1 >> s2;
// 解析日期，这里假设输入格式为yyyy-mm-dd，可根据输入格式调整
int y1, m1, d1, y2, m2, d2;
sscanf(s1.c_str(), "%d-%d-%d", &y1, &m1, &d1);
sscanf(s2.c_str(), "%d-%d-%d", &y2, &m2, &d2);
// 保证日期1是较早的日期，避免反向计算
if (y1 > y2 || (y1 == y2 && m1 > m2) || (y1 == y2 && m1 == m2 && d1 > d2)) {
swap(y1, y2);
swap(m1, m2);
swap(d1, d2);
}
int ans = 0;
// 逐日循环，直到两个日期相等
while (!(y1 == y2 && m1 == m2 && d1 == d2)) {
ans++;
d1++; // 天数+1
int maxDay = getMaxDay(y1, m1);
// 当月天数超限，进入下一个月
if (d1 > maxDay) {
d1 = 1;
m1++;
// 月份超限，进入下一年
if (m1 > 12) {
m1 = 1;
y1++;
}
}
}
cout << ans << endl;
return 0;
}
4. 解法二：前缀总天数差值法
核心思路
- 定义函数
calcTotalDays(year, month, day)：计算从固定起始年到当前日期的总天数。 - 两个日期的差值 =
abs(calcTotalDays(y1,m1,d1) - calcTotalDays(y2,m2,d2))
- 优势：无需循环模拟，计算效率极高，适合大范围日期差值计算。
核心代码片段
// 计算从0年到当前日期的总天数
int calcTotalDays(int y, int m, int d) {
int days = 0;
// 累加所有完整年份的天数
for (int i = 0; i < y; i++) {
days += isLeap(i) ? 366 : 365;
}
// 累加当年完整月份的天数
for (int i = 1; i < m; i++) {
days += getMaxDay(y, i);
}
// 累加当月天数
days += d;
return days;
}
// 主函数中计算差值
int day1 = calcTotalDays(y1, m1, d1);
int day2 = calcTotalDays(y2, m2, d2);
int ans = abs(day1 - day2);
5. 易错点&复习重点
- 闰年判断：必须严格遵循闰年规则，不要遗漏「能被100整除但不能被400整除的年份不是闰年」的条件。
- 日期大小：计算前必须先判断两个日期的先后，保证从较早的日期向较晚的日期计算，避免出现负数。
- 月份天数：大月小月不要记错，2月必须单独处理闰年情况。
- 跨年月处理：月份超过12时必须重置为1并给年份+1，不要遗漏年份进位。
六、经典算法小题解析
小题1：辗转相除法商的累加和
题目描述
给定两个正整数a和b，使用辗转相除法计算最大公约数（gcd）的过程中，累计每一步的商的和，输出最终的累加结果。
代码模板&解析
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a, b, ans = 0;
cin >> a >> b;
// 辗转相除循环，直到余数为0
while (b > 0) {
if (a > b) swap(a, b); // 保证a <= b，方便计算商
ans += b / a; // 累加当前步骤的商
b = b % a; // 更新b为余数，进入下一轮辗转相除
}
cout << ans << endl;
return 0;
}
核心逻辑
- 辗转相除法核心：
gcd(a,b) = gcd(b, a%b)，直到余数为0，此时的a即为最大公约数。 - 本题在每一步计算时，累加商
b/a，最终得到商的总和。
小题2：吃苹果问题（天数与最后一个苹果计算）
题目描述
有n个苹果，每天的吃苹果规则：将苹果每3个分为一组，每组吃掉1个；若最后剩余不足3个，有剩余则也吃掉1个。问：吃完所有苹果总共需要多少天？最后一个苹果是在第几天被吃掉的？
代码模板&解析
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt = 0; // cnt：总共吃了多少天
int first = 0; // first：最后一个苹果被吃掉的天数
while (n > 0) {
cnt++; // 进入新的一天
// 当剩余苹果数模3余1，且还没记录最后一个苹果的天数时
if (n % 3 == 1 && first == 0) {
first = cnt; // 最后一个苹果会在当天被吃掉
}
// 计算当天吃掉的苹果数：ceil(n/3) = n/3 + (n%3>0)
int eat = n / 3 + (n % 3 > 0);
n -= eat; // 更新剩余苹果数
}
cout << "总天数：" << cnt << "，最后一个苹果被吃掉的天数：" << first << endl;
return 0;
}
核心逻辑
- 每天吃掉的苹果数：向上取整
n/3，即n/3 + (n%3>0)。 - 最后一个苹果的判定：当剩余苹果数
n%3==1时，当天只会吃掉1个苹果，也就是最后一个，因此记录当前天数。
七、DP问题通用复习要点
-
核心四步走
- 明确状态定义：必须清晰说明dp[i][j]的含义，不能模糊。
- 推导状态转移方程：分情况讨论，明确每个转移的逻辑。
- 设置边界条件：根据状态定义确定初始值，最大值问题初始赋极小值，最小值问题初始赋极大值。
- 确定最终答案：明确dp数组中哪个位置是最终的结果。
-
易错点通用规避
- 下标越界：优先从1开始遍历，避免i-1为负数。
- 初始值错误：根据求最大/最小值，正确设置初始值，避免结果被覆盖。
- 状态转移逻辑错误：务必验证每个转移的场景是否合法，不要遗漏情况。
-
优化方向
- 时间优化：O(n²)优先考虑贪心、二分、单调队列等优化。
- 空间优化：二维DP优先考虑滚动数组、一维数组优化，降低空间复杂度。