笔试强训第 02 周：选择题精讲与编程题一题多解

先说个实话，很多同学把这一周的讲义翻出来，第一时间会盯着封面上的"选择题"三个字找半天——结果翻了几页才发现，所谓"选择题"，是对应那批让你在一个工程里反复取舍的"方案选择题"：这里该用双指针还是动规？这个岛该怎么数？这堆木棍该先排序还是直接爆搜？与其说是选 A 还是选 B，不如说每道题都在逼你"选对算法思路"。

所以别被标题骗了，第 02 周的本质，是一整周纯粹的 OJ 实战编程题。从 Day07 到 Day12，六天、十八道题，覆盖了五大看家本领：字符串处理、搜索与枚举、数论与贪心、动态规划、链表。这一周没有一句废话，全是"手把手怎么能写对、怎么别踩坑"的干货。

我的拆解方式沿用老规矩——每道题都按固定节奏来：题干 → 思路 → 完整可运行代码（逐行注释） → 运行结果 → 详解答案。而且要跟你们说清楚一件事：讲义里给的都是"标准答案代码"，我会在关键题上额外补一两种"不同打法"（也就是一题多解），再把每一种的时空复杂度给你标出来。因为笔试出题人最喜欢问的就是"这题还有没有别的写法""这个优化亏在哪"。你别只会背答案，得会拿捏思路。

为了让你看到真实运行效果，我把这十八道题的代码全部在本地 g++ 15.2（C++17） 上编译运行验证过，下面标的"运行结果"都是实打实跑出来的真数据，不是抄来的。你照着敲，能跑出一样的结果。

先给你一份本周的"作战地图"，心里有个数：

表格里"入门、中等、进阶"是我按掌握的难度排的，做的时候你会发现：入门题看着简单，但坑往往藏在边界；进阶题看着唬人，一旦思路通了也就一行熟练的事儿。别被标签劝退，往下走。

字符串处理（模拟、双指针、哈希）

字符串题是笔试的"亲儿子"，十个卷子里八个有它。这一周一口气塞进来四道：连续最长数字串、添加逗号、倒置字符串、删除公共字符。四道题的教训很统一：模拟题的坑不在算法，在"边界"——什么时候该跳、什么时候该补、越界了会不会崩，全靠细心。

一、在字符串中找出连续最长的数字串（模拟 + 双指针）

题干（题号 10055169）：

读入一个字符串，输出其中最长的连续数字子串。如果有多个长度相同的，输出第一次出现的那一个。如果字符串里一个数字都没有，则输出空行。

例如输入 abcd12345ed125ss123456789，最长连续数字段是 123456789，输出它。

思路：

这是个"扫一眼就知道"的题，但扫法有两种：

• 朴素想法：从左往右，遇到数字就往后数连续数字的长度，跟当前纪录比较保留最长的。这其实一言以蔽之就是"双指针"——一个 i 起头，一个 j 探路。
• 暗藏的优化：扫完一段连续数字后，i 可以直接跳到 j，不用回到 i+1 再查。因为这段纯数字内部不可能"生出更长"的新串，只有在这段之后才可能有更长的。

还有几个必须处理好的点：

1. 要求"第一次出现"：所以比较时用严格大于（>），遇到相同长度不更新，保的就是最早的那段。
2. 一个数字都没有：要输出空行，所以提前用 begin = -1 做标记。
3. substr 的起点：找到了 begin 和 len，用 s.substr(begin, len) 一锤定音。

完整可运行代码：

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;                       // 读入字符串（不含空格）
 
    int begin = -1, len = 0;        // begin 记录最长数字串起点，len 记录其长度
    for (int i = 0; i < (int)s.size(); i++)
    {
        // 发现一个数字，用双指针 big 这一段连续数字
        if (s[i] >= '0' && s[i] <= '9')
        {
            int j = i;              // j 从 i 开始向后探
            // 只要还是数字，j 就继续走
            while (j < (int)s.size() && s[j] >= '0' && s[j] <= '9')
                j++;
 
            // 只更新纪录的前提：严格大于现有 len（保证取第一次出现）
            if (j - i > len)
            {
                begin = i;
                len  = j - i;       // 这段长度 = j - i
            }
 
            i = j;                  // 关键优化：跳过整个数字段，避免重复扫描
        }
    }
 
    // 一个数字都没有：输出空行
    if (begin == -1)
        cout << "" << endl;
    else
        cout << s.substr(begin, len) << endl;
 
    return 0;
}

运行结果（本地实测）：

# 输入
abcd12345ed125ss123456789
# 输出
123456789

再测一条"零数字"的，输入 dfegdf，程序输出了一个空行（屏幕上看起来是一行空白的 endl），说明边界处理到位。

复杂度分析：每个字符最多被 i 和 j 各碰一次，整体 O(n)；只用常数级变量，空间 O(1)。

详解答案与易错点：

• 为什么 i = j 不会漏答案？ 你想，ijk 中间这段全是数字，任何以中间元素开头的子串严格短于整段，绝无可能打破纪录。真正可能"更长"的新串只能从这段数字之后重新起头。所以 i = j 安全。如果你图省事写 i++，那就退化成每个字符都重扫一遍，虽然结果对但白浪费时间——笔试里手写这样的小优化，观感分直接拉开。
• substr(begin, len) 的语义：从下标 begin 开始取 len 个字符。因为我们已经保证 begin + len <= n，不会越界。
• 没有数字时：直接输出 "" 加 endl 就是空行，别忘了，这是题目的显式要求，容易漏。

顺手给个解法二（动态规划思路），看完你会更理解"双指针"到底在省什么。用一个 f[i] 表示"到下标 i 为止的连续数字长度"，遇到数字 f[i] = f[i-1] + 1，否则为 0；最后找全局最大的 f[i]，倒推出起点 i - f[i] + 1：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
 
    int n = (int)s.size();
    vector<int> f(n, 0);            // f[i]：以 i 结尾的连续数字个数
    for (int i = 0; i < n; i++)
        if (s[i] >= '0' && s[i] <= '9')
            f[i] = (i > 0 ? f[i-1] : 0) + 1;
 
    int best = 0, idx = -1;         // best 最长长度，idx 其末尾下标
    for (int i = 0; i < n; i++)
        if (f[i] > best) { best = f[i]; idx = i; }
 
    if (idx == -1)                  // 没有数字
        cout << "" << endl;
    else
        cout << s.substr(idx - best + 1, best) << endl;
    return 0;
}

实测输入 abcd12345ed125，两种写法都输出 12345；输入 dfegdf 都输出空行。双指针在"原串原地跳"上更省记忆，DP 视角在让你看到"区间信息可以递推"，两者殊途同归。

二、添加逗号（模拟）

题干（题号 144140）：

读入一个不含小数点的长整数（用字符串表示），从个位开始从右往左每三位加一个英文逗号，输出结果。最后三位不加逗号。例如 999999999 → 999,999,999。

思路：

常见想当然的做法是从右往左数，但那样还得翻来覆去地处理字符串拼接。其实可以"正向扫描、倒着数剩余位数"：眼前这个字符后面还剩多少个字符，我就知道该不该在它后面补逗号。

从右边起每三位一段：假设字符串长度为 n，当前下标是 i，那么它右侧还有 n - i - 1 个字符。只要右侧剩余位数是 3 的倍数，就在当前字符之后加逗号——但最末尾一位（i == n-1）除外，因为它右边没有东西，不加逗号。

为什么这个规则对？我们把最右边视为"低位"，能整除 3 的位置天然就是每一小段的最后一个字符。唯一的坑是首段：比如 1234，n=4，i=0 时右侧剩 3 个（234）是 3 的倍数，所以在 1 后加逗号，输出 1,234，正确。再比如 123，n=3，i=0 时右侧剩 2 个，不是倍数，不加逗号，输出 123，正确。

完整可运行代码：

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
 
    string ret;                     // 存最终结果
    int n = (int)s.size();
 
    for (int i = 0; i < n; i++)
    {
        ret += s[i];                // 先把当前字符接进去
 
        // 右侧还剩 (n - i - 1) 个字符：是 3 的倍数 且 不是最后一个字符 => 补逗号
        if ((n - i - 1) % 3 == 0 && i != n - 1)
            ret += ',';
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本地实测）：

# 输入 999999999
999,999,999
# 输入 1234
1,234
# 输入 123
123

复杂度分析：单趟扫描，O(n) 时间、O(n) 空间（存结果串）。

详解答案与易错点：

• 条件里那个 i != n-1 最容易被删。如果去掉它，123 的 i=2 时右侧剩 0 个字符，「0 是 3 的倍数」成立，就会在最后面错误地加个逗号变成 123,。这是本题第一杀手级 bug。
• 为什么基数正好整除 3 要有"从右往左"的参照系：因为 (n-i-1)%3==0 的本质是"右边恰好能整段切完"。拿笔在纸上画 999999999（9 位），i=0 右侧 8 位、i=1 右侧 7、i=2 右侧 6→补逗号，正好卡在两个 999 之间。
• 如果你更习惯"从右往左三三一组再反转"，也可以。讲义答案给的正是那个思路：倒着走、每取三位补一个逗号、最后整体 reverse 回来。上面我给的"正向法"省掉了一次整体反转，两者都 AC。我实测反向法对 999999999、1234 输出也完全一致。

三、倒置字符串（字符串反转）

题干（题号 10055179）：

将一句话里的单词顺序倒过来，但每个单词内部的字母顺序保持不变，单词间可能有多个空格要保持原样。例如输入 I am a student，输出 student a am I。

思路：

这是经典"三步倒置"：先整体反转整串，再把每个单词局部反转一遍。道理很妙——整体反转后，单词顺序是反过来了，但每个单词本身也反了；只要再把每个单词内部翻转回来，就只留下"顺序倒置"这个效果。

分四小步：

1. getline 读整行（因为有空格，cin >> s 会中断）。
2. 对整个字符串 reverse。
3. 用双指针把每一个用空格分隔的"单词区间"再次 reverse。
4. 保留空格原样（找单词、翻单词、跳空格，循环往复）。

完整可运行代码：

#include <iostream>
#include <string>
#include <algorithm>   // reverse
using namespace std;
 
int main()
{
    string s;
    getline(cin, s);                // 读整行句子（注意不是 cin>>，它会被空格打断）
 
    reverse(s.begin(), s.end());    // 第一步：整体反转
 
    int left = 0, n = (int)s.size();
    while (left < n)               // 第二步：逐个单词再反转
    {
        int right = left;
        // 从 left 出发找到第一个空格，确定一个单词区间 [left, right)
        while (right < n && s[right] != ' ')
            right++;
 
        reverse(s.begin() + left, s.begin() + right);   // 反转这个单词内部
 
        // 跳过连续空格，准备处理下一个单词
        while (right < n && s[right] == ' ')
            right++;
 
        left = right;               // 移到下一个单词起点
    }
 
    cout << s << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
I am a student
# 输出
student a am I

单单词场景 nowcoder 原样输出 nowcoder（整体反转再局部反转，等于没动），符合预期。

复杂度分析：两次扫描均为 O(n)，空间 O(1)（原地反转）。

详解答案与易错点：

• getline vs cin >>：句子含空格，必须 getline(cin, s)。这是笔试里一句话题最典型的送分布尔选择题：用 cin >> 的人直接丢分。
• reverse(first, last) 是左闭右开区间：reverse(begin+left, begin+right) 反转的是 [left, right)，正好不含 right 所指的空格，天然正确、不用手动减一。很多同学手写循环时在这里掰扯半天，用 STL 直接避开陷阱。
• 多空格场景（比如 I am）：while (right<n && s[right]==' ') 能一次性跳过多个空格再定 left，这样空格数量被原样保留。若用"按空格切词再重新拼接"，反而会破坏多空格，反而不如这个做法严谨。讲义给的 Java 版用一个自写 Reverse 数组版是给背 Java 的看的，逻辑一致。

四、删除公共字符（哈希）

题干（题号 10055174）：

输入两个字符串 s 和 t（各占一行），从 s 中删除所有在 t 中出现过的字符，输出处理后的 s。例如 s = "They are students."，t = "aeiou"，删除元音后结果是 Thy r stdnts.。

思路：

要频繁判断"某个字符在不在 t 里"，最直接的办法是用一个字符哈希桶（布尔数组）：先扫描 t，把出现过的字符位置置 true；再扫描 s，凡是在桶里是 true 的一律跳过，其余照抄进结果串。

一个重要的坑：字符可能是英文、空格、标点甚至汉字，下标最大能到多少？ASCII 扩展码到 127，汉字用多个字节、单字节值也可能超过 127。稳妥起见把桶开成 300，给足余量。

完整可运行代码：

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s, t;
    getline(cin, s);        // 第一行：源串
    getline(cin, t);        // 第二行：要被删除的字符集合
 
    bool hash[300] = { 0 }; // 字符哈希桶，300 足够覆盖 ASCII 扩展与常见单字节
    for (char ch : t)       // 先把 t 里的字符都标记上
        hash[ch] = true;
 
    string ret;
    for (auto ch : s)       // 再扫 s，不在 t 里的留下
    {
        if (!hash[ch])
            ret += ch;
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
They are students.
aeiou
# 输出
Thy r stdnts.

复杂度分析：getline 两趟，O(|s|+|t|) 时间、O(1) 空间（桶固定大小）。

详解答案与易错点：

• 为什么不用"暴力判在不在"，比如 s.find(ch) 或双重 for 循环：双重循环是 O(|s|×|t|)，串一长就崩；find 内部也是线性扫描。哈希桶把"判断一个字符是否在集合里"压到 O(1)，是这道题唯一该背的套路。
• 桶开多大是个小考点：开 256 勉强够 ASCII，但为了稳我建议 300，讲义原始答案给的就是 bool hash[300]，说明出题人就默认有这种字符范围风险。你要是手滑开个 128，遇到扩展到汉字就内存越界或丢字符。
• 读入用 getline：因为第二行 t 可能是一串字符，也可能题目给的是多行输入，cin >> s; cin >> t; 在含空格时同样会断，所以讲义全用 getline。

搜索与枚举（floodfill 与暴力枚举）

这一块两道题，教你说清楚"怎么把一个区域内联通的每一个整体都找出来"（岛屿数量）和"怎么判断一组东西能否满足硬性条件"（拼三角）。前者是图上的 floodfill，后者是纯数学枚举，风格迥异但都是搜索思想。

五、岛屿数量（DFS / BFS 双解）

题干（题号 1024684，即牛客 NC109）：

给定 m×n 的二维字符网格，其中 '1' 表示陆地、'0' 表示海洋。四个方向（上下左右）相邻的 '1' 属于同一个岛屿。返回网格中岛屿的数量。

思路：

这是**floodfill（洪水填充）**类问题的教科书模板。核心思想一句话：每碰见一个没访问过的陆地，就把它所在的整块联通的陆地区域全部 "漆" 掉，岛屿计数加一，然后再去找下一块。

具体到实现，有两种主流姿势：

1. DFS（深搜）：递归地把当前格子标记为 '0'（就地改，省一张 visited 表），再对四个方向递归。
2. BFS（广搜）：用队列逐层扩展，同一个 visited 判定。

就地改成 '0' 是 DFS 版的一个巧妙点：因为网格上 '1' 只出现一次扫描窗口内，把它改 '0'，既避免了重复访问，又省下额外的 vis 数组。方向和越界检查用一个增量数组 dx[4] = {0,0,1,-1}、dy[4] = {1,-1,0,0} 统一管理。

完整可运行代码（DFS 版 + 驱动测试）：

#include <iostream>
#include <vector>
using namespace std;
 
class Solution {
public:
    int solve(vector<vector<char>>& grid)
    {
        int ret = 0;                                // 岛屿计数
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')              // 发现一个新岛屿
                {
                    ret++;
                    dfs(grid, i, j);                // 把这一整块陆地板成 '0'
                }
            }
        }
        return ret;
    }
 
private:
    int dx[4] = { 0, 1, -1, 0 };                    // 方向增量（右、下、上、左）
    int dy[4] = { 1, 0, 0, -1 };
 
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        grid[i][j] = '0';                           // 就地染色
        int m = grid.size(), n = grid[0].size();
        for (int k = 0; k < 4; k++)                 // 四连通
        {
            int x = i + dx[k], y = j + dy[k];
            // 越界检查 + 只对陆地递归
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
                dfs(grid, x, y);
        }
    }
};
 
// 下面 main 是为了方便本地跑验证，提交时只提交 Solution 即可
int main()
{
    vector<vector<char>> grid = {
        {'1','0','1'},
        {'1','1','0'},
        {'0','0','1'}
    };
    Solution c;
    cout << "DFS 岛屿数量 = " << c.solve(grid) << endl;
    return 0;
}

运行结果（本地实测）：

DFS 岛屿数量 = 3

（网格里有两块单点岛 (0,2)、(2,2)，加左上角一块 (0,0)-(1,0)-(1,1) 联通的，共 3 块。）

BFS 版本：把 DFS 的递归换成队列，逻辑等价的，我实测同一网格输出同样 3：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
class Solution {
public:
    int solve(vector<vector<char>>& grid)
    {
        int ret = 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));   // 独立访问标记
        int dx[4] = { 0, 0, 1, -1 };
        int dy[4] = { 1, -1, 0, 0 };
 
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    ret++;
                    queue<pair<int,int>> q;
                    q.push({i, j});
                    vis[i][j] = true;
                    while (!q.empty())
                    {
                        auto [x, y] = q.front(); q.pop();
                        for (int k = 0; k < 4; k++)
                        {
                            int nx = x + dx[k], ny = y + dy[k];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n
                                && grid[nx][ny] == '1' && !vis[nx][ny])
                            {
                                vis[nx][ny] = true;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};

复杂度分析：每个格子最多被访问常数次，时间 O(m×n)；DFS 递归栈最坏 O(m×n)，BFS 队列最坏 O(m×n)，空间都是 O(m×n)。

详解答案与易错点：

• DFS 就地改 '0' 和 BFS 用 vis，到底差在哪？ 就地改省空间但"污染"了输入网格；vis 版不污染输入但要一块 O(m×n) 的布尔表。笔试里通常两种都能过，能讲出这个差异就是加分项。牛客 NC109 的原始答案（讲义里的 Java 版）用的正是 vis[210][210] 写法，说明题干默认网格边长不超过 200 左右。
• 递归深度：当岛屿特别大、又游蛇状延伸时，DFS 可能递归几千层导致栈溢出。极端的笔试环境里，要能想到"深搜栈不够，换广搜或者自己维护栈"。这也是为什么我刻意把 BFS 也放进来。
• 方向别写重：上下左右四方向用增量数组原生铺开最不容易漏。八方向（含对角）的题则需要 8 组增量，注意区分题目要的是"四连通"还是"八连通"。

六、拼三角（枚举 / 数学判断）

题干（题号 1389509）：

有 6 根木棍，长度互不相同（也可能相同），问能否把它们分成两堆，每堆 3 根，各自都能拼成一个三角形（三角形两边之和大于第三边）。t 组输入，输出 Yes / No。

思路：

最暴力的枚举是 C(6,3) 枚举"哪三根算第一堆"，剩下的三根自然第二堆，然后分别判断是否构成三角形；只要任一分配可行就是 Yes。6 根挑选 3 根只有 20 种组合，暴力完全跑得动。

讲义给出的却是一版更聪明的数学判断：先对 6 根排序成 a[0]..a[5]，然后只要下面四组兄弟判断里有一组成立就输出 Yes：

a[0]+a[1]>a[2] 且 a[3]+a[4]>a[5]
a[0]+a[2]>a[3] 且 a[1]+a[4]>a[5]
a[0]+a[3]>a[4] 且 a[1]+a[2]>a[5]
a[0]+a[4]>a[5] 且 a[1]+a[2]>a[3]

这个结论怎么来的？排序后，最小两根 a[0]、a[1] 和最短的那根组三角形，而"第三根"到底是谁决定了整体方案。由于只取最紧的约束（最短的两条边一定出现在最短的三角形里），所以把 6 根排好序后只需要固定检查"最短两根 + 第三根"在 4 个可能的第三根位置上的配法定公平性即可。这是枚举思想的高级压榨版，笔试爱考这种"排序之后看规律"的题眼。

光看判断式容易晕，实际上由于搜索空间极小，我给你一版面向理解的暴力枚举写法（实测和数学法结论完全一致）:

完整可运行代码（数学判断法）：

#include <iostream>
#include <algorithm>
using namespace std;
 
int t;
int arr[6];                     // 6 根木棍长度
 
// 判断三条边能否构成三角形：任意两边之和 > 第三边
bool canTriangle(int a, int b, int c)
{
    return a + b > c && a + c > b && b + c > a;
}
 
int main()
{
    cin >> t;
    while (t--)
    {
        for (int i = 0; i < 6; i++) cin >> arr[i];
        sort(arr, arr + 6);     // 先排序
 
        if (canTriangle(arr[0], arr[1], arr[2]) && canTriangle(arr[3], arr[4], arr[5]) ||
            canTriangle(arr[0], arr[2], arr[3]) && canTriangle(arr[1], arr[4], arr[5]) ||
            canTriangle(arr[0], arr[3], arr[4]) && canTriangle(arr[1], arr[2], arr[5]) ||
            canTriangle(arr[0], arr[4], arr[5]) && canTriangle(arr[1], arr[2], arr[3]))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

我把讲义里那一长串"相加判断"封装成 canTriangle，可读性好很多，行为等价。

运行结果（本地实测）：

# 输入
2
1 2 3 4 5 6
4 4 4 4 4 4
# 输出
No
Yes

分析一下：1 2 3 4 5 6 无论怎么分，含 1 的那一堆最短板组合 1+2=3 恰好不"大于" 3，凑不出三角形，所以 No；4 4 4 4 4 4 随便砍成两堆等边三角形，Yes。

暴力枚举版（供对照理解）：

#include <iostream>
using namespace std;
 
int arr[6];
 
bool tri(int a, int b, int c)
{
    return a+b>c && a+c>b && b+c>a;
}
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        for (int i = 0; i < 6; i++) cin >> arr[i];
 
        bool ok = false;
        // 枚举第一堆的三种(i,j,k)，第二堆就是剩下三根
        for (int i = 0; i < 6 && !ok; i++)
            for (int j = i+1; j < 6 && !ok; j++)
                for (int k = j+1; k < 6 && !ok; k++)
                {
                    bool first = tri(arr[i], arr[j], arr[k]);
                    // 收集剩余三根
                    int rem[3], r = 0;
                    for (int u = 0; u < 6; u++)
                        if (u != i && u != j && u != k)
                            rem[r++] = arr[u];
                    bool second = tri(rem[0], rem[1], rem[2]);
                    if (first && second) ok = true;
                }
        cout << (ok ? "Yes" : "No") << endl;
    }
    return 0;
}

我实测这个暴力版，同样的两组输入同样输出 No / Yes，跟数学法一致。

复杂度分析：数学判断法排序 O(6 log 6)，常数级别的判断；暴力枚举 C(6,3)=20 次组合，也是常数。两者都 O(1)（对单组输入而言），数据规模是固定的 6，跑多久都是瞬间。

详解答案与易错点：

• 三角形判定记得是"两边之和 > 第三边"的严格大于，不是 >=。等边、若是 1 1 2 就不构成三角形，1+1=2 不满足 >。这个边界一错，样例直接翻车。
• 数学判断法为什么只要 4 组？ 因为排序后，最 "危险" 的三角形一定包含最短的两根 arr[0]、arr[1]，剩下那根只要从 arr[2..5] 里来回试；把 arr[0] 固定给第一堆，第二堆的最短两根就落到 arr[1] 加另一根上。四组判断覆盖了所有"最短两板与哪根组队"的可能。不会枚举也没关系，暴力版在这个数据范围同样 AC——但能讲清数学版的人，明显更懂排序带来的单调性。

数论与"性质判断"

两道题都非常"数学"：求最小公倍数，和判断 5 张牌能不能组成顺子。共同点是——想通了就是一个公式/一条性质的事，想不通就写递归写循环写到怀疑人生。

七、求最小公倍数（数学、最大公约数）

题干（题号 10055186，牛客 HJ108）：

给定正整数 A 和 B，求它们的最小公倍数（LCM）。

思路：

最小公倍数和最大公约数之间有一句百试百灵的公式：

lcm(A, B) = A / gcd(A, B) * B

而最大公约数用**辗转相除法（欧几里得算法）**一行递归搞定：gcd(a, b) = (b == 0) ? a : gcd(b, a % b)。这一行是数论题的基本功，背不下来也得会推导。

完整可运行代码：

#include <iostream>
using namespace std;
 
// 欧几里得：求最大公约数
int gcd(int a, int b)
{
    if (b == 0) return a;       // 余数为 0，a 就是公约数
    return gcd(b, a % b);       // 否则递归：gcd(a,b) == gcd(b, a%b)
}
 
int main()
{
    int a, b;
    cin >> a >> b;
 
    // 注意：先除再乘，防止 a*b 溢出 int
    long long lcm = (long long)a / gcd(a, b) * b;
 
    cout << lcm << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
5 7
# 输出
35

gcd(5,7)=1，lcm = 5/1 * 7 = 35。

复杂度分析：辗转相除的步数是对数级别，O(log(min(a,b))) 时间，空间受递归栈影响 O(log(...))（也可改迭代降到 O(1)）。

详解答案与易错点：

• 顺序 a/gcd*b 而不是 a*b/gcd：a*b 可能瞬间顶穿 int 上界。所以必须"先除再乘"，还要把结果用 long long 承接。讲义原答案直接写 a * b / gcd(a,b) 会溢出，我们这里做了修正，这也是加深你对笔试数值边界敏感度的好例子。若用 std::gcd（<numeric> 的 std::gcd），同样逻辑，我实测 lcm_std(5,7)=35 无误。
• gcd 递归终止条件 b == 0 返回 a 是关键，漏了就无限递归。迭代写法可以免掉递归栈，两个都认识为一个就好。

八、扑克牌顺子（排序 + 哈希/性质判断）

题干（题号 23252，牛客 JZ61）：

从若干扑克牌中随机抽 5 张，判断能不能组成顺子。大小王（记为 0）可以充当任意牌，用 0 来补缺。给定一个 vector<int>（numbers.size()>=5），值域 0~13（0 为大小王，1~13 为各点数），若能组成顺子返回 true，否则 false。若两张相同且非 0，则不能。

思路：

顺子要想成立，除去大小王（0）后的那些牌必须同时满足：

1. 不能出现重复的非 0 牌（没有对子，否则补不了）。
2. 最大点数减去最小点数 <= 4：因为 5 张牌里最多只能有 13-1=12 的 span，但真正关键的是"最大和最小之间空位不能超过 0 的数量"。当 0 能任意补时，等价于 max - min <= 4。

所以做法收敛成：扫描一遍，用哈希桶判重，同时记账 max 和 min，最后返回 maxVal - minVal <= 4。

完整可运行代码：

#include <iostream>
#include <vector>
using namespace std;
 
class Solution {
    bool hash[14] = { 0 };          // 点数为 1~13，桶开 14 格够用
public:
    bool IsContinuous(vector<int>& numbers)
    {
        int maxVal = 0, minVal = 14;
        for (auto x : numbers)
        {
            if (x)                  // 跳过大小王(0)
            {
                if (hash[x])        // 重复的非 0 牌 => 判负
                    return false;
                hash[x] = true;     // 标记出现
                maxVal = max(maxVal, x);
                minVal = min(minVal, x);
            }
        }
        return maxVal - minVal <= 4;
    }
};

运行结果（本地实测，用了一个驱动）：

{1,3,0,0,5}  -> 1   (true，缺的 2、4 由两个 0 补上)
{1,3,3,0,5}  -> 0   (false，重复 3)
{1,7,0,0,5}  -> 0   (false，差 6 > 4，两个 0 不够补)
{0,0,0,0,0}  -> 1   (true，五个王随便凑 1~5)

复杂度分析：一趟扫描，O(n)（这里 n=5 更是常数），空间 O(1) 的哈希桶。

详解答案与易错点：

• 坑一：0 不要参与判重、不要污染 max/min。把所有王都当成"通配符"，只用非零牌去算判重、极差。
• 坑二：为什么 max-min <= 4 就够，不用管"差了几张"？ 因为 0 的数量恰好等于 5 - 非零数量，min 和 max 之间的每一个空位都能被它补上。只要空位数不超过王的数量即可，而空位数 = (max-min) - (非零数量-1)，结合王数一推导，简化成 max-min <= 4。这是这道题真正的"题眼"。
• 坑三（全 0 情况）：{0,0,0,0,0}，maxVal 不动是 0，minVal 不动是 14，max-min = 0 - 14 = -14 <= 4 成立，返回 true，正确。如果初始 minVal 设成很大的数、maxVal 设成 0，恰好是这个效果，别把初始值设反了导致纯 0 误判。
• 讲义里的 Java 版用的 boolean[] hash，和 C++ 版逻辑完全一致，两种语言都 AC。如果你更喜欢"排序 + 数 0 + 数 gap"，同样能过（我实测排序版对上述四组样例输出 1 0 0 1），只是哈希版更省一趟 sort。

排序 + 模拟

九、数组中的最长连续子序列（排序 + 模拟）

题干（题号 1008752，牛客 NC95）：

给定一个无序数组（可能有重复），求最长的连续数值子序列长度。什么叫"连续子序列"？它不要求下标相邻，只要求元素按大小是连续递增的，比如 100,4,200,1,3,2 里能挑出 1,2,3,4 也就是长度 4。求这个最大长度。

思路：

这类题有两条主流路：

• 排序 + 模拟：先 sort，排序之后连续的数自然挨在一起，扫描一遍把所有"差为 1"的连续段数出来，取最大。最大的坑是相同数字：arr[j] == arr[j-1] 时不能算"长度 +1"，但也不能断掉，得 j++ 跳过。
• 哈希集合（set）：先把所有数去重进 set，只从"没有前驱 x-1"的数起头向后顺延数长度。这是 O(n) 写法，是排序法的平行打法学。

完整可运行代码（排序 + 模拟）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    int MLS(vector<int>& arr)
    {
        sort(arr.begin(), arr.end());       // 先排序
        int n = (int)arr.size(), ret = 0;
        for (int i = 0; i < n; )           // 外层：枚举每一段起点
        {
            int j = i + 1, count = 1;      // count 当前连续段长度
            while (j < n)
            {
                if (arr[j] - arr[j-1] == 1)      // 相邻连续：长度加一
                {
                    count++;
                    j++;
                }
                else if (arr[j] - arr[j-1] == 0) // 相同数字：跳过但不加长
                {
                    j++;
                }
                else
                {
                    break;                       // 断裂，本段结束
                }
            }
            ret = max(ret, count);          // 更新答案
            i = j;                          // 跳到下一段起点
        }
        return ret;
    }
};

运行结果（本地实测）：

[100,4,200,1,3,2]        -> 4
[0,3,7,2,5,8,4,6,0,1]    -> 9
[1,1,2,2,3,4,4]          -> 4

第三条是专门测"重复数"的：1,1,2,2,3,4,4 去掉重复后是 1,2,3,4，最长连续段为 4。如果实现时把 ==0 那段也当成"连续"（count++），就会数出 6，直接错。

哈希集合法（解法二，O(n)）：

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
class Solution {
public:
    int MLS(vector<int>& arr)
    {
        set<int> st(arr.begin(), arr.end());  // 去重并排序
        int ret = 0;
        for (int x : st)
        {
            if (st.count(x - 1)) continue;    // 有前驱 x-1，说明 x 不是段头
            int len = 1;
            while (st.count(x + len)) len++;  // 从段头向后顺延
            ret = max(ret, len);
        }
        return ret;
    }
};

实测同样三组输入，分别得到 4 / 9 / 4，与排序法完全一致。

复杂度分析：排序法 O(n log n) 时间、O(1) 空间（原地 sort）；哈希法用有序 set 仍 O(n log n)，若换成 unordered_set 则平均 O(n)，空间 O(n)。笔试让说复杂度时，能讲清这两种差异最加分。

详解答案与易错点：

• 排序法的 ==0 分支是灵魂。很多人只写 ==1 就 count++，遇到重复直接 break 或 count++，两个方向都错——前者漏算了去重后的真正长度，后者把重复多算进去。正确处理是"跳过但不打断"。
• i = j 的外层跳转：和第一题同理，一段已断开的区间内部不可能再诞生更长连续段，所以直接跳到 j，既对又快。若写成 i++，重复段会被反复扫描，不优雅。
• 哈希法为什么只从"没有前驱"的数起头：这是避免"每个数都把它的整条链再数一遍"变成 O(n²) 的关键。只有段头（没有 x-1）才值得顺延，保证整体 O(n)。

贪心思想（含一个"贪心反例"）

贪心，是"每一步都取当前看起来最赚的选择"。但贪心之所以难，不是因为它复杂，而是因为它经常错——你以为局部最优等于全局最优，结果栽了。本周三题里，第 12 题就是一个精心设计的"贪心必错"的陷阱题。

十、买卖股票的最好时机(一)（贪心）

题干（题号 2364518，牛客 DP30）：

已知未来 n 天的股价序列，只能做一次买卖（先买后卖），求能获得的最大利润。如果怎么都是亏，返回 0。

思路：

只看 [0, i] 天，那么假设在第 i 天卖出，我一定希望买入价是 [0, i] 里的最低价。所以维护一个"遍历到当前为止的最低买入价 prevMin"，每来一个新价格就更新它，并顺手更新 max(答案, 今天价格 - 最低价)。这就是一句话的贪心。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int N = 1e5 + 10;
int n;
int arr[N];
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    int ret = 0, prevMin = arr[0];      // prevMin：到当前为止的最低买入价
    for (int i = 1; i < n; i++)
    {
        prevMin = min(arr[i], prevMin); // 更新最低价
        ret = max(ret, arr[i] - prevMin); // 今天卖出的最优利润
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
6
7 1 5 3 6 4
# 输出
5

# 输入（一路下跌）
5
7 6 4 3 1
# 输出
0

第一组：第 2 天（价 1）买入、第 5 天（价 6）卖出，利润 5。第二组一路下跌，任何一天买都是亏，答案 0。

复杂度分析：单趟，O(n) 时间、O(1) 空间。

详解答案与易错点：

• 千万别写成"输出整个序列里的最大值减最小值"——那等于允许先卖后买，会算出错误答案。前 i 天最低价 和 今天价格 的先后次序由 prevMin 的更新时机天然保证：我们总是"先看今天能赚多少，再更新最低价"，这样买入一定发生在卖出之前。
• 暴力写法在这里是反面教材：双重循环 i 买、j 卖，O(n²)，数据一大就超时。笔试能顺手答出"暴力是 O(n²)、贪心优化到 O(n)"这个对比，说明你真的懂这题。

十一、买卖股票的最好时机(二)（贪心）

题干（题号 2364576，牛客 DP31）：

与上一题同序列，但这一题可以无限次买卖（每天可以买卖，只要手上有就买、没有就卖，手里最多持一股）。求最大累计利润。

思路：

既然不限次数，那只要今天的价格比昨天高，这一天就值得"持有吃下这段涨幅"。把每一个 arr[i] > arr[i-1] 的差值累加就是答案。这是"能吃到的每一段上涨都吞进肚子"的贪心，直觉上违背直觉，却是对的。

为什么对？因为任意一次"低买高卖"的整体收益，可以被拆成若干个相邻上涨段的累加，而拆到不能再拆就到单日差。所以累加所有正的单日差，恰好等于最优总收益。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int N = 1e5 + 10;
int n;
int arr[N];
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    int ret = 0;
    for (int i = 1; i < n; i++)
        if (arr[i] > arr[i - 1])            // 今天比昨天高：吃下这截涨幅
            ret += arr[i] - arr[i - 1];
 
    cout << ret << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
6
7 1 5 3 6 4
# 输出
7

拆解：1→5 赚 4，3→6 赚 3，合计 7。注意买在 1 卖在 6 单独一次也只有 5，分两段吃反而更多。

复杂度分析：O(n)、O(1)。

详解答案与易错点：

• 这题和上一题的区别就是"交易次数"。一题用 prevMin，一题累加所有上涨段。笔试题最爱把这两题放一起考你"能不能根据限制选对策略"。
• 不要试图"找波峰波谷"再算价差，那要记状态还容易错；直接累加相邻上涨差，简单且万无一失，这就是贪心精妙之处。

十二、游游的水果大礼包（枚举，贪心反例）

题干（题号 10274354）：

游游有 n 个苹果和 m 个桃子，包装两种礼包：1 号礼包需要 2 个苹果 + 1 个桃子，卖 a 元；2 号礼包需要 1 个苹果 + 2 个桃子，卖 b 元。问最多能卖出多少元（水果可以不用完）。

思路：

这题是**"贪心得先证明，否则别急着贪"**的活教材。直觉上你会说："哪个礼包贵，就多包那种。"然后你就会掉坑。

为什么贪心错？因为两种礼包对不同水果的消耗比例不同——1 号礼包吃苹果多、2 号礼包吃桃子多。假如总是贪贵的 1 号礼包，可能会把苹果过早耗光，结果白白浪费掉一堆桃子，算下来总价反而更低。所以正确打法是枚举 1 号礼包的个数 x，剩下的水果尽量多包 2 号礼包，对每个 x 算一次总价，取最大。

具体约束推导：

• 1 号礼包 x 个消耗 2x 苹果、x 桃子，所以 x 至多 min(n/2, m)。
• 剩下的苹果 n - 2x、桃子 m - x，全部给 2 号礼包（吃 1 苹果 2 桃），所以 y = min(n - 2x, (m - x)/2)。
• 总价 a*x + b*y，对所有 x 取最大。

完整可运行代码：

#include <iostream>
#include <algorithm>
using namespace std;
 
long long n, m, a, b;   // 用 long long：数据量一大，乘积可能溢出 int
 
int main()
{
    cin >> n >> m >> a >> b;
 
    long long ret = 0;
    // 枚举 1 号礼包的个数 x
    for (long long x = 0; x <= min(n / 2, m); x++)
    {
        long long y = min(n - x * 2, (m - x) / 2);   // 剩余最多能包多少个 2 号礼包
        ret = max(ret, a * x + b * y);               // 更新总价
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
5 6 1 1
# 输出
3

5 苹果、6 桃，两种礼包单价都是 1 元。全包 1 号最多 2 个（用 4 苹果 2 桃），剩 1 苹果 4 桃可再包 2 个 2 号？不对，2 号吃 1 苹果 2 桃，一个 2 号就用完苹果了。于是：x=2, y=min(5-4, (6-2)/2)=min(1,2)=1，总价 3。实测 3，正确。

复杂度分析：枚举 x 从 0 到 min(n/2,m)，至多 O(min(n/2,m))；对大数据要留神，但通常够快，时间 O(n) 量级、空间 O(1)。

详解答案与易错点：

• 为什么不贪心：因为 1 号礼包和 2 号礼包水果消耗比例不同，局部"哪个贵做哪个"会破坏水果配比，导致整体次优。讲义原话就是"贪心是错的，正确的解法应该是枚举所有的情况"。
• y 的表达式别抄错：剩下的桃子 m - x，2 号礼包吃 2 个桃，所以是 (m-x)/2；再和剩余苹果 n-2x 取最小，双双满足才有意义。
• 用 long long：n,m 可以很大，a*x+b*y 可能溢出 int，讲义原版用的就是 long long。这是笔试喜欢考的数值边界细节点。

动态规划：路径问题

路径问题学的是 DP 里一张最基本的模态：从左上角走到右下角，每次只能向右或向下，问最优/方案数。它的精髓在于状态转移方程往往是 dp[i][j] = f(dp[i-1][j], dp[i][j-1])。本周来了两道：字母收集（加权和），过河卒（带障碍的方案数）。

十三、字母收集（路径 DP）

题干（题号 1714951，牛客 DP39）：

有一个 m×n 的字符矩阵，小蓝从左上角 (1,1) 出发，每次只能向右或向下移动一步，走到右下角 (m,n)。经过的每个格子带有分值：l=4、o=3、v=2、e=1（其余字符为 0）。求一条路径，使其收集到的分值总和最大，输出最大分值。

思路：

标准的"数字/字符三角形"式 DP。设 dp[i][j] 为"从起点到 (i,j) 能拿到的最大分值"，则因为只能从上（(i-1,j)）或左（(i,j-1)）来：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 该格子的分值

为了让 i-1、j-1 在 i=1、j=1 时不越界，把矩阵下标从 1 开始存（多开一圈），这样 dp[0][*] 和 dp[*][0] 天然是 0。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int N = 510;
char g[N][N];
int dp[N][N];
int m, n;
 
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++)               // 从 1 开始读，避免 dp 下标越界
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
 
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int t = 0;                          // 该格子分值
            if (g[i][j] == 'l')      t = 4;
            else if (g[i][j] == 'o') t = 3;
            else if (g[i][j] == 'v') t = 2;
            else if (g[i][j] == 'e') t = 1;
 
            // 只能从上或左来，取较大者 + 当前分值
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + t;
        }
    }
 
    cout << dp[m][n] << endl;
    return 0;
}

运行结果（本地实测，用一个 2×2 的小网格手算可核对）：

# 输入
2 2
l o
v e
# 输出
8

手算：dp[1][1]=4(l)；dp[1][2]=max(0,4)+3=7；dp[2][1]=max(4,0)+2=6；dp[2][2]=max(7,6)+1=8。输出 8，对得上。

复杂度分析：双循环填充，O(m×n) 时间、O(m×n) 空间（或滚动数组压到 O(n)）。

详解答案与易错点：

• 下标从 1 开始是关键：让 dp 的边界行/列天然是 0，max(dp[i-1][j], dp[i][j-1]) 在起点 (1,1) 处不会读到野值。这是路径 DP 的通用规范写法。
• 字符分值映射别写反：l→4、o→3、v→2、e→1，这个映射出错整题就废，看清楚题干给的对照表。
• 本题也是"最大路径和"问题的不同变体，把分值由字符映射而来。核心转移方程和"数字三角形"一致，学会这题，后续大量路径 DP 都是它的壳。

十四、过河卒（路径 DP + 障碍）

题干（题号 2378812，牛客 DP13，NOIP2002 普及组）：

棋盘上有 A(0,0) 和 B(n,m) 两个点，卒从 A 到 B，每次只能向右或向下走一步。棋盘上有匹马位于 (x,y)，马站稳的位置以及马一步能跳到的 8 个控制点，卒都不能经过。求从 A 到 (n,m) 的通路条数（结果可能很大，用 64 位）。

马的走法是"日"字：在二维平面上 <i diff, j diff> = <±1, ±2> 或 <±2, ±1>。

思路：

路径方案数 DP：dp[i][j] = dp[i-1][j] + dp[i][j-1]，但凡是"马控制点或马本身"，直接置 0（不可达）。为避免 i-1、j-1 越界，把棋盘整体平移 1（从下标 1 开始），并在 dp[0][1] 打一个"虚起点"为 1，这样 dp[1][1]=dp[0][1]+dp[1][0]=1+0=1，正确表达"起点本身是一条路径"。

马的控制点判断：一个点 (i,j) 如果要被马控制，它到马 (x,y) 的行列差的曼哈顿距离必须等于 3，且不能在某一行/列完全重合（i != x 且 j != y）——这正是"日"字的特征：|Δi| = 1 且 |Δj| = 2，或反过来。加上马本身位置，一共 9 个禁点（8 个控制点 + 马自己）。

讲义给的条件是 (abs(i-x)+abs(j-y)==3 && i!=x && j!=y) || (i==x && j==y)，恰到好处：曼哈顿距离==3 且两坐标都有变化，才是日字落脚点；马本身再单独处理。

完整可运行代码：

#include <iostream>
#include <cmath>
using namespace std;
 
int n, m, x, y;
long long dp[25][25];       // 用 64 位：方案数可能非常大
 
int main()
{
    cin >> n >> m >> x >> y;
 
    x += 1; y += 1;         // 整体平移 1，让 dp 下标从 (1,1) 开始避免越界
    dp[0][1] = 1;           // 虚起点，让 dp[1][1] 是 1（起点本身就 1 条路）
 
    for (int i = 1; i <= n + 1; i++)
    {
        for (int j = 1; j <= m + 1; j++)
        {
            // 是马本身，或是马的控制点（日字落脚处）=> 不可达
            if ((abs(i - x) + abs(j - y) == 3 && i != x && j != y) ||
                (i == x && j == y))
            {
                dp[i][j] = 0;
            }
            else
            {
                // 只可能从上边或左边到达
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
 
    cout << dp[n + 1][m + 1] << endl;
    return 0;
}

运行结果（本地实测，并用独立暴力 DFS 交叉验证过）：

# 输入
6 6 3 3
# 输出
6

# 输入
8 8 1 1
# 输出
660

6 6 3 3 是 NOIP 经典样例，答案正是 6，官方标准答案无误。

复杂度分析：O(n×m) 时间、O(n×m) 空间。

详解答案与易错点：

• 平移坐标是约定俗成的防坑手段：输入里 A 在 (0,0)，但 dp 数组从 (1,1) 计数。把 x、y 各加 1 后，(0,0) 变成 (1,1)，马的位置也对齐到平移后的坐标系，否则关键判断全会偏掉。
• dp[0][1]=1 这行是起点逻辑的关节：没有它，dp[1][1] 会算成 dp[0][1]+dp[1][0]=0+0=0，整张表全错。
• 控制点判断别简写成 abs(i-x)+abs(j-y)==3：那会把同一直线上的点（比如 |Δ|=3 且在同列）也误判成控制点。必须补上 i != x && j != y 排除同行/同列。我自己写独立递归暴力验证时，正是这两组条件保证了 6 6 3 3 得 6、8 8 1 1 得 660，完全吻合。
• 用 long long：路径数增长极快（无马时是组合数 C(n+m,n)），int 会溢出，讲义原版就用的 long long。

动态规划：线性 DP 入门口味

十五、跳台阶（斐波那契）

题干（题号 2357966，牛客 DP2）：

一只青蛙一次可以跳 1 级或 2 级台阶，问跳上 n 级台阶共有多少种跳法（n 从 1 开始，f(1)=1，f(2)=2）。

思路：

这是"最简单动态规划"的招牌题。设 f(i) 为跳上第 i 级的方法数，最后一步要么从 i-1 跳 1 级、要么从 i-2 跳 2 级，所以：

f(i) = f(i-1) + f(i-2), f(1)=1, f(2)=2

这恰好是"位移一位的斐波那契"。可以开数组，也可以只滚动三个变量 a,b,c。

完整可运行代码（滚动变量版）：

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    if (n == 0 || n == 1)   // 边界：0 或 1 级直接返回
    {
        cout << n << endl;
        return 0;
    }
 
    int a = 1, b = 1, c = 0;   // a=f(i-2), b=f(i-1), c=f(i)
    for (int i = 2; i <= n; i++)
    {
        c = a + b;             // f(i) = f(i-1)+f(i-2)
        a = b;
        b = c;
    }
 
    cout << c << endl;
    return 0;
}

运行结果（本地实测）：

# 输入 3 -> 3
# 输入 5 -> 8
# 输入 1 -> 1

f(3)=f(2)+f(1)=2+1=3，f(5)=8，f(1)=1，全对。

复杂度分析：O(n) 时间、O(1) 空间（滚动变量）。

详解答案与易错点：

• 边界 n==1 要单独防：如果 n=1，循环 for(i=2;i<=1;...) 不会执行，c 还是初值 0，直接输出 c 就错了。讲义用 if(n==0||n==1) cout<<n 兜底，正是这个道理。
• 递推本质是斐波那契：把 f 序列写出来是 1, 2, 3, 5, 8, 13...，即"斐波那契整体往后移一位"。笔试里问"跳台阶能不能用矩阵快速幂加速到 O(log n)"，答案是可以，但应该是进阶题才用得上，这里 O(n) 足够。

十六、mari和shiny（线性 DP：子序列计数）

题干（题号 375040）：

输入一个长度为 n 的字符串（只含小写字母 s/h/y 等），统计其中"子序列" shy 的出现次数。所谓子序列，是不要求连续、但要保持相对顺序地从字符串里挑出的字符序列 s、h、y。次数可能很大，用 64 位输出。

思路：

这是经典"a→ab→abc"式的三段式线性 DP。维护三个量：

• s：扫描到现在一共出现过多少个字符 s（即能作为 shy 开头的 s 数量）。
• h：能够作为 shy 中间位 h 的"sh"子序列个数。每遇到一个 h，它都能和之前所有的 s 组成新的 sh，所以 h += s。
• y：shy 子序列总数。每遇到一个 y，它都能和之前所有的 sh 组成新的 shy，所以 y += h。

一通扫描，答案就是 y。

完整可运行代码：

#include <iostream>
#include <string>
using namespace std;
 
int n;
string str;
 
int main()
{
    cin >> n >> str;
 
    long long s = 0, h = 0, y = 0;   // 分别累计 s / sh / shy 的数量
    for (int i = 0; i < n; i++)
    {
        char ch = str[i];
        if (ch == 's')
            s++;        // 新 s：给以后所有 h 做"sh"的开头
        else if (ch == 'h')
            h += s;     // 新 h 与前面每个 s 组成新的 sh
        else if (ch == 'y')
            y += h;     // 新 y 与前面每个 sh 组成新的 shy
    }
 
    cout << y << endl;
    return 0;
}

运行结果（本地实测）：

# 输入
5
shyys
# 输出
2

拆解：s(0) h(1) y(2) y(3) s(4)。第一个 h 使 h=1；第一个 y 让 y=1；第二个 y 让 y=2；最后 s 只让 s=2。总计 shy 子序列 = 前两个 shy（用第 0 个 s + 第 1 个 h + 第 2/3 个 y），共 2。

复杂度分析：单趟扫描，O(n) 时间、O(1) 空间。

详解答案与易错点：

• 顺序很重要：s / h / y 三个变量的更新有先后依赖——必须保证"看到 y 时，h 已是它前面所有 sh 的计数，而 h 的计数又来自更前的 s"。所以代码里三个分支按字母出现独立更新即可，无需额外排序，因为我们是逐字符扫的，天然按位置先后累计。
• 用 long long：shy 个数在最坏情况下是 O(n³) 量级的组合数，n 一大就爆 int。讲义原版给的正是 long long s,h,y。
• 这题的套路可以无痛推广到 mari（即"m→ma→mar→mari"四级计数），方法完全一致，只是多加一重累加。能举一反三的同学，在这里能直接说出推广版。

回文串专题

十七、最长回文子串（中心扩展 / 区间 DP）

题干（题号 25269，牛客 OR26）：

给定一个字符串，求其中最长的回文子串长度。回文串即正着读反着读都一样的串，比如 "babad" 的最长回文子串是 "bab" 或 "aba"，长度 3。

思路：

回文串最长长度的主流打法有二：

• 中心扩展（讲义推荐）：回文串一定有个"中心"，向两边对称展开直到不对称。难点在于中心有两种：奇数长度中心是单字符，偶数长度中心是两字符中间的空隙。对每一个位置都分别以"单字符中心""两字符空隙中心"向外扩展，用双指针 left/right 扩散并记录半径，取最大。
• 区间 DP：dp[i][j] 表示子串 s[i..j] 是否为回文，用 dp[i][j] = (s[i]==s[j] && dp[i+1][j-1]) 递推，O(n²)。

完整可运行代码（中心扩展）：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    int getLongestPalindrome(string s)
    {
        int ret = 1, n = (int)s.size();
        if (n == 0) return 0;
 
        for (int i = 1; i < n; i++)        // 枚举每个"中点"（从 1 开始）
        {
            // 情况一：奇数长度，以 i 为中心，向两边扩散
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            ret = max(ret, right - left - 1);   // 本次回文长度
 
            // 情况二：偶数长度，以 (i-1, i) 中间的空隙为中心
            left = i - 1;
            right = i;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            ret = max(ret, right - left - 1);
        }
        return ret;
    }
};

区间 DP 版本（一题多解，供对照）：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
class Solution {
public:
    int getLongestPalindrome(string s)
    {
        int n = (int)s.size();
        if (n == 0) return 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));  // dp[i][j]: s[i..j]是否回文
        int ret = 1;
        for (int i = 0; i < n; i++) dp[i][i] = true;        // 单字符都是回文
 
        for (int len = 2; len <= n; len++)                  // 枚举区间长度
        {
            for (int i = 0; i + len - 1 < n; i++)
            {
                int j = i + len - 1;
                if (s[i] == s[j])
                {
                    if (len == 2) dp[i][j] = true;          // 两个相同字符
                    else          dp[i][j] = dp[i + 1][j - 1]; // 看内层是否回文
                }
                if (dp[i][j]) ret = max(ret, len);          // 更新最大长度
            }
        }
        return ret;
    }
};

运行结果（本地实测中心扩展）：

babad -> 3      (bab / aba)
abc1234321ab -> 7   (1234321)
ababc(DP) -> 3  (aba)

复杂度分析：中心扩展对每个中心至多扩到串两端，O(n²) 时间、O(1) 空间；区间 DP O(n²) 时间、O(n²) 空间。n 小时两个都行，笔试若卡大范围推荐中心扩展（省空间）。

详解答案与易错点：

• 中心有两种，别只写奇数。不回文的最小情况是"偶数长度"，比如 "abccba" 的对称中心落在两个 c 之间的空隙，只用"单字符中心"会漏算。讲义中心扩展同时写两段 while，正因如此。
• right - left - 1 为什么是回文长度：当两个指针在不对称处停下时，回文的实际区间落在 (left, right) 之间，长度恰为 right - left - 1。这是中心扩展最优雅的一句公式，背下它。
• 初始 ret=1：任意单字符天然是回文，哪怕整体没有更长的，答案至少是 1。空串要特判返回 0。
• DP 的递推顺序：外层按区间长度 len 从 2 到 n 推进，保证计算 dp[i][j] 所需的 dp[i+1][j-1]（更短区间）已算出。

链表

十八、两个链表的第一个公共结点（多解）

题干（题号 23257，牛客 JZ52）：

输入两个无环单链表，如果它们从某个结点开始发生"相交"（共用同一段后缀），求相交的第一个结点。若不相交，返回 nullptr。空间越省分越高。

思路：

求链表公共结点有三套经典打法，我从易到难给你讲：

1. 暴力/哈希：把链表 A 的所有结点地址塞进哈希集合，再遍历 B，第一个在集合里出现的结点即答案。简单，但 O(n+m) 空间。
2. 长度差法：先测两条链长度，把较长那条先走掉差值的 |lenA-lenB|，然后两指针同步走，首次相遇（a==b）就是公共结点。O(1) 空间。
3. 路程相同法（最妙）：两条链相交后长度可能不同，但让两个指针都在「走到结尾就换成对方链头」的路上走，因为两个指针走过的总路程完全相等（都等于 lenA+lenB），它们必然在公共结点或空结点处相遇。一行 while 搞定，O(1) 空间。

完整可运行代码（路程相同法，推荐）：

#include <iostream>
using namespace std;
 
// 牛客给的链表结构
struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* cur1 = pHead1;
        ListNode* cur2 = pHead2;
 
        // 两个指针都"走到头就换另一条链"，走过的路程必相等
        while (cur1 != cur2)
        {
            cur1 = cur1 ? cur1->next : pHead2;   // 走到空就换链
            cur2 = cur2 ? cur2->next : pHead1;
        }
        return cur1;   // 相交：即第一个公共结点；不相交：都会走到空，返回 nullptr
    }
};

长度差法（一题多解，O(1) 空间）：

#include <iostream>
#include <algorithm>
using namespace std;
 
struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    int ListLen(ListNode* p)   // 求链表长度
    {
        int n = 0;
        for (; p; p = p->next) n++;
        return n;
    }
 
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
    {
        int len1 = ListLen(pHead1), len2 = ListLen(pHead2);
 
        // 让 a 指向较长链
        ListNode* a = pHead1;
        ListNode* b = pHead2;
        if (len1 < len2) { swap(a, b); swap(len1, len2); }
 
        // 较长链先走掉差值，让两个指针"对齐"到同一水平
        for (int i = 0; i < len1 - len2; i++)
            a = a->next;
 
        // 同步走，首次相同即公共结点
        while (a != b)
        {
            a = a->next;
            b = b->next;
        }
        return a;
    }
};

运行结果（本地实测，构造 A=1→5，B=2→3，公共后缀从链头 4→6 开始）：

公共结点应为 4
路程相同法结果 = 4
长度差法结果  = 4

两法都在公共结点 4 处正确返回。

复杂度分析：路程法一趟，O(lenA+lenB) 时间、O(1) 空间；长度差法同理。哈希法时间 O(lenA+lenB)、空间 O(lenA)。

详解答案与易错点：

• 路程相同法为什么成立：令 a 从 A 出发、b 从 B 出发，走完一轮后 a 总路程 lenA + lenB、b 总路程 lenB + lenA，两者相等。若相交，两人必在公共段入口处首次相遇；若不相交，两人同时走完全程后都变为 null，cur1==cur2==null 退出，返回空指针。既有终止条件又天然处理无交点，堪称链表题最优雅的一道解法——但前提是两个链表都无环，题目已保证。
• 哈希法的"入"：教科书里没有地址比较不能做，unordered_set< ListNode* > 记录的是结点指针（地址），不是值域，这样才能判断"同一个结点"。把值相等的不同结点当成公共节点就错了。
• 别被值迷惑：公共结点的判据是"地址相同（是同一个结点）"，不是 val 相等。两个不同结点值一样不叫相交。面试官最爱拿这点考你。

收尾：本周怎么复习

一口气刷完这 18 题，你其实已经把笔试最常见的六大算法套路走了一遍：模拟、双指针、搜索（floodfill）、枚举、贪心、动态规划，外加字符串和链表两大高频载体。别急着翻页，给你三个动作收尾：

1. 把"一题多解"的对照当作复习主线。比如最长回文子串：中心扩展跟区间 DP；买卖股票(一)：贪心跟暴力。不要只记答案，要记"同一道题，不同口味的做法各长什么样、复杂度差在哪"。笔试问"还有别的写法吗"，就是问这个。
2. 把"坑"做成自己的错题本。这周坑点密集：i = j 的跳转、substr 边界、1+1=2 不算三角形、顺子的 max-min<=4、水果配比的换成 long long、过河卒的控制点判定、跳台阶的 n==1、字符判断要 i!=x&&j!=y……每一条都是血泪。复制一份到笔记里，考前泛读一遍。
3. 重跑一遍"亲手验证"。上面所有代码我都在 g++ -std=c++17 上跑出了真实结果。你最好把每题的样例输入自己敲一遍，亲眼看到输出和你手算一致——动手和看懂，隔着一整个世界。

这周的题不是让你背的，是帮你把"看到题 → 认出套路 → 写出能过的代码"这条链路跑顺。能把十八题全都"独立看懂再独立敲出来"，第 03 周迎接新套路时，你就有底气多了。我们下周见。