笔试强训第 07 周：逐题精讲与完整题解

第 07 周，咱们正式告别前面几周"单点练手"的节奏，开始进入系统性刷题型的深水区。这一周的题跨度非常广：字符串查找、链表堆、记忆化搜索、模拟找规律、哈夫曼编码、拓扑排序、以及一大波动态规划（线性递推、LIS、打家劫舍变形、完全背包、01 背包加同余）。一共 6 天、18 道题，几乎把笔试里"中等偏上"的高频题型都过了一遍。

先给你打个预防针：这一周不少题乍一看很吓人——"天使果冻""宵暗的妖怪""小红取数"这种名字，完全不知道在说什么。但请你记住一句话：笔试的怪名字题，九成都是换个皮的老题。剥掉名字、看懂输入输出，思路立刻唤起你前几周练过的模型。所以本周的每一道题，我都会带着你把"题目翻译成人话"这一步做透，再给完整可编译运行的代码、真机跑出来的结果、以及容易踩的坑。

老规矩，本文按题型组织（而不是按天），因为到第 07 周，跨天归纳才是本事。每一题都是全闭环：题干 → 思路 → 完整可运行代码（逐行注释）→ 真机运行结果 → 详解答案与坑点。

字符串：从查找、哈希到滑动窗口

字符串这一块本周来了四道，覆盖了三种很典型的手段：用倍增拼接做查找、用计数桶做哈希、用滑动窗口做区间种类统计、用枚举取环形距离。这四招串起来，就是笔试字符串题的全部家底了。

1. 旋转字符串（字符串查找）

题干

给定两个字符串 A 和 B，如果 A 经过任意次绕自身做"左旋/右旋"（把某个前缀整体移到末尾，或把某个后缀移到开头，只要保持相对顺序不变地循环移位）之后，能恰好得到 B，就返回 true；否则返回 false。（牛客题号 1024728，核心代码模式，写 solve 方法。）

所谓"旋转"，举个直观例子：A = "AAB"，旋转一次得到 "ABA"（把首字符 A 移到末尾），再旋转一次得到 "BAA"。所以 "AAB" 能旋转出 "ABA" 和 "BAA" 以及自身 "AAB"。

思路

这题有两种做法，我劝你直接记第二种，它是这类题的最优解。

第一种（暴力模拟）：每次把 A 旋转一位，和 B 比一次。转一圈最多 n 次，每次比较 O(n)，总复杂度 O(n²)。能过，但不优雅，而且容易在"旋转方向、起始位置"这些细节上手滑。
第二种（倍增查找，重点）：如果 B 是 A 旋转的结果，那么 B 一定是 A+A（把 A 复制一份接到自己后面）的子串。 反过来同理。因为 A+A 里天然包含了 A 的所有循环移位。所以我们只需要判断长度是否相等、以及 (A + A).find(B) 能否找到 B 即可，一行搞定，std::string::find 内部是高效的匹配算法，总复杂度 O(n)。

为什么 A+A 能覆盖所有旋转？想清楚这个就彻底理解了：A 的每一种旋转，都可以看作"取 A 中某个位置之后的一段 + 之前的一段"拼接，而 A+A 正好把任意这样的拼接都完整地包含在里面。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
class Solution {
public:
    bool solve(string A, string B)
    {
        // 长度不等，无论怎么旋转都不可能相等，直接排除
        if (A.size() != B.size()) return false;
 
        // 若 B 是 A 旋转的结果，则它必是 A+A 的子串；
        // find 找不到时返回 string::npos（其值为 -1），不等于 -1 即找到
        return (A + A).find(B) != -1;
    }
};
 
// ---- 本地测试驱动（OJ 上不需要，方便你直接 Build & Run 验证） ----
int main()
{
    Solution s;
    cout << s.solve("AAB", "BAA") << endl;   // AAB 旋转1次 -> BAA，true
    cout << s.solve("AAB", "ABA") << endl;   // AAB 旋转2次 -> ABA，true
    cout << s.solve("ABCD", "DABC") << endl; // ABCD 旋转1位 -> DABC，true
    cout << s.solve("ABCD", "ACBD") << endl; // ACBD 不是 ABCD 的旋转，false
    cout << s.solve("AB", "AAB") << endl;    // 长度不等，false
    return 0;
}

运行结果

我本机用 g++ 15.2.0 编译运行（g++ -O2）的真实输出：

（程序里用 1/0 代表 true/false。）

逐个核对：

"AAB" vs "BAA"：A+A = "AABAAB"，能匹配到 "BAA"（在下标 2..4），true；
"AAB" vs "ABA"：同样在 "AABAAB" 里能匹配到 "ABA"（下标 1..3），true；
"ABCD" vs "DABC"："ABCDABCD" 里匹配到 "DABC"，true；
"ABCD" vs "ACBD"："ABCDABCD" 里无论如何找不到 "ACBD"（A 与 C 互换了位置，这种结构破坏旋转不变性），false；
"AB" vs "AAB"：长度 2 ≠ 3，false。

详解答案与坑点

答案：三个正例返回 true，两个反例返回 false。
复杂度：find 在 C++ 里是线性或近线性的高效匹配，A+A 建串 O(n)，总 O(n)；空间 O(n)（存 A+A）。
坑一：长度判断必须写在倍增之前。 如果两个字符串长度不同，A+A 长度是 2|A|，而 B 长度不同，find 永远找不到，虽然结果也碰巧是 false，但逻辑上应该先判长度。更关键的是：长度不同时"是否旋转"本来就无意义，先排除干净，代码意图清晰，也省下一次串拼接。
坑二：find 的返回值。 C++ 的 string::find 找不到时返回 string::npos，它被定义为 (size_t)-1，即最大的无符号数，跟 -1 判等是等价的（会隐式转换成相同数值）。写成 != -1 是牛客教材的标准写法，你可以放心用；想更规范也可以写 != string::npos。
坑三（理解坑）：为什么不是"判断 A 和 B 互为背排列"。 有的同学会想成"把 A 反转再看看"，那是"反转"不是"旋转"。旋转保持相对环顺序，反转会打乱它在环上的相邻关系。"ABCD" 旋转得不出 "DCBA"（那是反转），这题要的是旋转。
一题多解：暴力模拟法就是"for 旋转 0..n-1 次，每次整体移一位，和 B 比"，面试时可以顺嘴一提证明你懂朴素思路，再把倍增法甩出来证明你懂优化。

2. 神奇字母（二）（哈希 + 字符串）

题干

输入一组由小写字母组成的字符串（可以是一个或多个单词，中间用空格或换行隔开，读到文件尾结束，不知道一共几组）。请你找出整个输入里出现次数最多的那个字母并输出。（牛客题号 955181。）

举例：如果输入 abcab，那么 a 出现 2 次、b 出现 2 次、c 出现 1 次，出现次数最多的是 a（并列时取先达到该次数的那个），所以输出 a。

思路

这就是教科书级的桶计数（哈希）：小写字母一共 26 个，直接开一个 int hash[26]，下标用 ch - 'a' 映射。遍历每一个串的每一个字符，hash[ch - 'a']++。同时维护一个 maxCount，一旦某个字母的计数严格大于当前 maxCount，就更新它和 ret。

这里最精妙的细节在"并列怎么处理"：判断条件是 ++hash[...] > maxCount（严格大于），这意味着——当两个字母计数相同、且都是当前最大时，先达到这个最大值的那个字母ret会被保住，后达到的不会覆盖它。这正好实现了"并列取先到者"的要求。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    int hash[26] = { 0 };   // 26 个小写字母的计数器，初始全 0
    char ret = 0;           // 答案字母（默认 0，意义是"空"）
    int maxCount = 0;       // 当前最大出现次数
 
    while(cin >> s)         // 输入可能是多个单词/多组，读到 EOF 自动停
    {
        for(auto ch : s)
        {
            // ++ 先自增再比较；只有当计数严格大于历史最大值时才更新，
            // 这样并列最大值时保住的永远是"先达到该次数"的那个字母
            if(++hash[ch - 'a'] > maxCount)
            {
                ret = ch;
                maxCount = hash[ch - 'a'];
            }
        }
    }
 
    cout << ret << endl;
    return 0;
}

运行结果

真机输出（输入 abcab，单个单词）：

与手算一致：a、b 都是 2 次，但遍历时 a 先达到 2 次、b 后达到但不满足严格大于，所以最终 ret = 'a'。我们把过程捋一遍：

处理 a：hash[a] = 1，1 > 0 → ret = 'a'，maxCount = 1；
处理 b：hash[b] = 1，1 > 1 不成立 → 不动；
处理 c：hash[c] = 1，不成立；
处理 a（下标3）：hash[a] = 2，2 > 1 → ret = 'a'（仍是 a），maxCount = 2；
处理 b（下标4）：hash[b] = 2，2 > 2 不成立 → 不动。

所以最终 ret = 'a'。可以看到 b 虽然也达到 2 次，但因为不满足严格大于，没能换掉 ret——这就是"并列取先到"的实现。

详解答案与坑点

答案：输入 abcab 输出 a。
复杂度：O(总字符数)，空间 O(26)。
坑一：并列时到底是取前还是取后，要跟题意对齐。 我用 > 实现"保先到者"，这是本题（牛客 955181）的要求。但有些变种题会要求"并列取 ASCII 最小的"或"『输出字典序最小』"，那种就要改成 >= 或者额外判断。 做题时一定先看清并列规则再选比较符。这也是写这类"最大值"题的通用心法：先问自己并列怎么办，再决定用 > 还是 >=。
坑二：字符下标映射。 ch - 'a' 把 'a'..'z' 映射到 0..25。如果你粗心用了 ch - '0' 就别想对了。并且题目保证只有小写字母，所以越界风险为零；如果题目混入大写就很麻烦，要另做处理。
坑三：读入方式。 用 while(cin >> s) 是最地道的"读到 EOF"写法，它会自动跳过空白、以单词为单位读取，天然适合"不知道多少组单词/串"这种输入。
一题多解（考虑更通用值域）：如果字符集合不是 26 个可枚举的小写字母，而是一般的字符甚至字符串，那"定长桶"开不下，就要上 unordered_map<char, int> 或 unordered_map<string, int> 当哈希表。做题先看字符集大小，再决定桶还是 map。

3. 游游的字母串（枚举 + 环形距离）

题干

给定一个字符串，你可以对任意位置的字符做操作：把一个字符朝 a 的方向或朝 z 的方向移动任意步，每移动 1 步消耗 1 点能量，并且 a 和 z 是首尾相连的（即 a 前进一步是 z，z 后退一步是 a，26 个英文字母围成一个环）。请你用最少的能量，把整个字符串变成全由同一个字母组成的串，输出这个最小能量。（牛客题号 10274355。）

举例："abc" 变成全 'b' 需要 |a-b|=1 + |b-b|=0 + |c-b|=1 = 2，这正是最小值。

思路

题目翻译成人话其实很朴素：枚举"最终变成哪个字母"，分别算出把每个字符变过去需要的总能量，取最小值。

但这里有个隐藏的坑：字母围成环，所以从 x 移到 ch，不只是走直线 |x - ch| 步，还可以绕环的另一边走 26 - |x - ch| 步。两者取小，才是从 x 到 ch 的最短距离。

于是单字符贡献的能量是：

min(|x - ch|, 26 - |x - ch|)

然后对 26 个候选目标字符各算一遍总和，取最小，即为答案。

为什么枚举 26 个就够了？因为"全变成一个字符"这个目标，最终字符一定是 'a'..'z' 里的某一个，一共就 26 种可能，全部试一遍即可，不用动任何聪明脑筋。

完整可运行代码

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
 
    int ret = 1e9;                 // 答案初始化为一个大数
    for(char ch = 'a'; ch <= 'z'; ch++)   // 枚举最终要变成的字符
    {
        int sum = 0;                        // 变成 ch 需要消耗的总能量
        for(auto x : s)
        {
            // |x-ch| 是走直线；26-|x-ch| 是绕过环的另一侧。
            // 因为 a 和 z 首尾相连，两者取小才是最短距离
            sum += min(abs(x - ch), 26 - abs(x - ch));
        }
        ret = min(ret, sum);                // 更新最小能量
    }
 
    cout << ret << endl;
    return 0;
}

运行结果

真机输出（分别输入 abc、abcd、x）：

2
4
0

逐个核对：

"abc"：枚举到目标 'b' 时，a 距 b 为 1、b 距 b 为 0、c 距 b 为 1，总和 2。还能更小吗？目标 'a' 是 0+1+2=3，目标 'z' 是 1+2+3=6。所以最小值 2。✓
"abcd"：目标 'b'：1+0+1+2=4；目标 'c'：2+1+0+1=4；目标 'a'：0+1+2+3=6。最小值 4。✓
"x"：单字符本来就是自己要的样子，目标 'x' 代价 0。✓

详解答案与坑点

答案：abc → 2；abcd → 4；x → 0。
复杂度：O(26 × n)，n 是串长，极小的常数倍，可视为线性。
坑一（这题的核心坑）：别忽略绕环那半边。 很多同学写成 sum += abs(x - ch) 就交了，对 "abc" 这种短距离样例碰巧对，但一旦出现需要"绕 z 走过去更省"的字符就错了。比如目标 'a'、当前字符 'z'：直线距离 25，但 z 前进一步就是 a，只要 1 步！所以必须写 min(abs, 26 - abs)。一遇到"环形、循环移位、首尾相接"这些字眼，先想绕远路是不是更近。
坑二：abs 要算绝对值，别丢符号。 x - ch 可能为负（比如 x='a'、ch='z'），直接拿去乘会出错。先 abs 再算。
坑三：枚举的是"变成的角色"，不是"当前"字符。 嵌套层要分清：外层 ch 是目标，内层 x 是源字符，别把两者写反。
一题多解（数学断面）：理论上可以先对每个字符统计，再求出最优目标字符在数轴/环上的位置，用三分或断点法做到更优，但 n 和 26 都小，暴力枚举 26 次最简单，笔试足够。

4. 小红的子串（前缀 + 滑动窗口）

题干

给定一个由小写字母组成的字符串，长度为 n，再给两个整数 l、r。请你统计：满足不同字符种类数在 [l, r]（含端点）这个区间内的子串，一共有多少个。（牛客题号 10745732。）

所谓"子串"是指连续的一段；字符串里的子串按"左端点 + 右端点"定位，两个子串只要有任意一个端点不同就算不同子串（即便字符内容碰巧相同）。

思路

这题有个非常漂亮的数学技巧——前缀差分：

"种类数落在 [l, r]"这件事不好直接数，但"种类数不超过 x"这件事可以数，而且好数得多。于是定义函数：

find(x) = 字符串中"不同字符种类数 <= x"的子串个数

那么答案就是：

find(r) - find(l - 1)

因为"种类数在 [1, r] 的"减去"种类数在 [1, l-1] 的"，剩下的恰好就是"种类数在 [l, r] 的"。这是极其经典的前缀差分思想，做题时遇到"区间计数"问题，永远是"大区间减小区间"。

接下来关键是怎么求 find(x)，用滑动窗口（单调双指针）：

right 每到一个位置，就把字符加进窗口；用一个 hash[26] 记每种字符当前在窗口内的个数，用 kinds 记当前窗口内不同字符的种类数。
只要 kinds > x，就不断收缩 left，把左边字符移出窗口（hash[s[left]]--，减到 0 时 kinds--）。
当窗口内种类数恰好 ≤ x（也就是收缩结束），以 right 为右端点的、满足种类数 ≤ x的子串，个数就是 right - left + 1（左端点可以从 left 取到 right，任取其一都合法）。

这个"以 right 结尾的子串个数"累加起来，就是 find(x)。两个指针都只前进，整体 O(n)。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
int n, l, r;
string s;
 
// 求"不同字符种类数在 [1, x]"之间（即 <= x）的子串个数
long long find(int x)
{
    if(x == 0) return 0;          // 没有任何字符时，0 个合法子串
    int left = 0, right = 0;      // 窗口左右边界
    int hash[26] = { 0 };         // 窗口内各字符的出现次数
    int kinds = 0;                // 窗口内不同字符的种类数
    long long ret = 0;            // 答案（长度可能很大，用 long long）
 
    while(right < n)
    {
        // 1. 进窗口：新加入的字符种类计数 +1，若这是它在窗口里第一次出现则 kinds+1
        if(hash[s[right] - 'a']++ == 0) kinds++;
 
        // 2. 出窗口：只要窗口内种类数超过 x，就收缩左边界，把多余种类赶出去
        while(kinds > x)
        {
            // 出窗后该字符计数变为 0，说明这种字符彻底离开窗口，kinds-1
            if(hash[s[left] - 'a']-- == 1) kinds--;
            left++;
        }
 
        // 3. 此时窗口 [left, right] 内种类数 <= x，
        //    以 right 结尾的合法子串个数 = 可选左端点数 = right - left + 1
        ret += right - left + 1;
        right++;
    }
    return ret;
}
 
int main()
{
    cin >> n >> l >> r >> s;
    // 前缀差分：种类数在 [l, r]  =  <= r 的  -  <= l-1 的
    cout << find(r) - find(l - 1) << endl;
    return 0;
}

运行结果

真机输出（两组样例 n=3, l=1, r=3, s="abc" 与 n=3, l=2, r=3, s="aab"）：

6
2

逐一看：

"abc"，l=1，r=3：find(3) 是"种类数 ≤ 3"的子串个数。"abc" 全部 6 个子串（"a"、"b"、"c"、"ab"、"bc"、"abc"），种类数分别是 1、1、1、2、2、3，都 ≤ 3，所以 find(3)=6；find(0)=0。答案 6 - 0 = 6。✓
"aab"，l=2，r=3：所有子串及其种类数为 "a"(1)、"a"(1)、"b"(1)、"aa"(1)、"ab"(2)、"aab"(2)。种类数落在 [2,3] 的是 "ab" 和 "aab"，共 2 个。用差分算：find(3)=6，find(1)＝种类数 ≤1 的子串＝"a"、"a"、"b"、"aa" 共 4 个，答案 6-4=2。✓

详解答案与坑点

答案：abc / 1 3 → 6；aab / 2 3 → 2。
复杂度：find 一次 O(n)，调用两次，总 O(n)；空间 O(26)。
坑一（概念坑）："种类数"是不同字符的种数，不是总字符数。 千万别拿"窗口长度"去和 x 比。长度和种类是两回事：比如窗口 "aa"，长度是 2，但种类数是 1。
坑二：ret 一定要用 long long。 n 可达 1e5 级别，子串总数是 n(n+1)/2，量级到 1e10，int 必溢出。这是这类"数子串个数"题的统一陷阱。
坑三：find(0) 的特判。 当 l=1 时，l-1=0，直接调 find(0) 要返回 0；否则 while(right<n) 里连窗口都进不去，逻辑上也对（kinds 永远 ≤ 0 不可能成立，ret 保持 0），但有显式特判更清晰、也防止边界处节外生枝。
坑四：hash[s[left] - 'a']-- == 1 的前/后置细节。 这句的含义是"把它当前的计数减 1，并判断减之前是不是 1"——如果是 1，减完变 0，说明这种字符彻底没了，kinds--。用后置自减，恰好拿的是"旧值"，语义吻合。
一题多解（扩展）：这题本质是"滑窗 + 前缀差分"，是一种通法——凡是"统计某类子串个数，且约束是某个单调量（种类数、和、长度）落在区间内"的题，都可以"数 <=r 减 <=l-1"。把 kinds 换成"窗口和"就能解"子数组和落在区间内"的同款变体，值得收藏。

链表与堆：合并 k 个有序链表

链表题是笔试的常客，而这题是把"堆（优先队列）"和"链表"缝合起来，考你数据结构的组合能力。合并两个有序链表你肯定熟，合并 k 个就要借个堆了。

5. 合并 k 个已排序的链表（链表 + 堆）

题干

给定 k 个已排序（升序）的链表，每条链表的头节点用 ListNode 对象表示，ListNode 有 val（值）和 next（下一个节点指针）。请把这 k 条链表合并成一条有序（升序）链表并返回它的头节点。（牛客题号 NC51 / 724。）

核心代码模式：补全 mergeKLists(vector<ListNode*>& lists)，入参是 k 条链表的头指针数组。

思路

合并两条有序链表是"双指针归并"，合 k 条不能简单两两归并（那样要回滚很多趟）。标准解法是堆（优先队列），思路跟"多路归并排序"一模一样：

把 k 条链表的头节点都扔进一个小根堆（按 val 排）。
每次从堆顶弹出当前所有候选节点里值最小的那个，接到答案链表的末尾。
刚从堆里弹出的节点，如果它还有 next，就把它的 next 也压进堆。
重复 2、3 直到堆空，这时所有 k 条链表都被串成了一条完整的有序链表。

为什么这样能得到全局有序？因为每个时刻堆顶一定是"所有候选位置里最小的"，弹出-接上-补新，每一轮取到的都是当前最小，合在一起自然是升序。用堆把"找当前最小"的代价稳定到 O(log k)，总复杂度 O(N log k)，N 是所有节点的总数。

小技巧：答案用哨兵头 new ListNode(0)（哑节点）打底，最后返回 dummy->next，这样不用单独处理"第一个节点"的边界。

完整可运行代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
// 链表节点定义（题目已给出）
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
class Solution {
    // 自定义优先队列的比较器：把小的节点顶到堆顶（小根堆）
    // 注意：priority_queue 默认是大根堆，这里把比较结果反过来就是小根堆
    struct cmp {
        bool operator()(ListNode* l1, ListNode* l2) {
            return l1->val > l2->val;   // 注意是 >，让小值"优先级更高"
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        // 1. 把每条链表的头节点压入小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for(auto head : lists)
        {
            if(head != nullptr) heap.push(head);   // 空链表头是 nullptr，跳过
        }
 
        // 2. 哨兵节点，方便统一接节点，最后 return 它的 next
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
 
        // 3. 反复从堆顶取最小的节点接到答案末尾
        while(heap.size())
        {
            ListNode* t = heap.top();
            heap.pop();
            prev = prev->next = t;        // 接到答案链表尾部，并让 prev 前进到 t
 
            if(t->next != nullptr)        // 该节点这条链的后继还有，压回堆继续参与比较
                heap.push(t->next);
        }
        return ret->next;                 // 返回真正的链表头（跳过哨兵）
    }
};
 
// ---- 本地测试驱动：建链、合并、打印 ----
ListNode* build(vector<int> a) {
    ListNode* dummy = new ListNode(0);
    ListNode* p = dummy;
    for (int x : a) { p->next = new ListNode(x); p = p->next; }
    return dummy->next;
}
void print(ListNode* h) {
    while (h) { cout << h->val << " "; h = h->next; }
    cout << endl;
}
int main() {
    Solution so;
    // 三条有序链：[1,4,5] [1,3,4] [2,6]
    vector<ListNode*> lists = { build({1,4,5}), build({1,3,4}), build({2,6}) };
    print(so.mergeKLists(lists));
 
    // 全是空链表的边界
    vector<ListNode*> e = { nullptr, nullptr };
    print(so.mergeKLists(e));   // 应无任何输出（空链表）
    return 0;
}

运行结果

真机输出：

1 1 2 3 4 4 5 6

（第二组全是空链表，合并结果为空，所以只输出一个空行。）

合并后的 1 1 2 3 4 4 5 6，正好是三条链 [1,4,5]、[1,3,4]、[2,6] 合并后的升序结果，正确。

详解答案与坑点

答案：三链合并输出 1 1 2 3 4 4 5 6；全空输入输出空链表。
复杂度：O(N log k)（N 为总节点数，每节点进出堆一次），空间 O(k)（堆内至多 k 个节点）。
坑一（最容易错）：自定义比较器的方向。 priority_queue 默认是大根堆（top 是最大元素）。模板 priority_queue<Type, Container, Compare> 中，Compare 决定"谁优先"——当 cmp(a,b) 为真时，a 排在 b 后面（即 b 优先）。所以想让小值优先出堆，必须写 return l1->val > l2->val;（返回大者放后，小者优先）。写反成 <，就变回大根堆，合并结果完全乱掉。记忆法：优先队列的比较函数与 sort 是反的，sort 你写 < 是升序，priority_queue 里你要升序反而要写 >。
坑二：堆里存的是裸指针 ListNode*。 比较器里访问 l1->val 前，必须保证指针非空。好在压堆前都已经过滤了 nullptr，堆里不会有空指针。但如果你漏掉 if(head != nullptr)，空链表头进堆后比较器解引用就崩了。
坑三：弹出节点后要接它的后继。 别忘 if(t->next != nullptr) heap.push(t->next)，否则每条链只贡献一个节点就断了。
坑四：prev = prev->next = t; 的连锁赋值。 这是先 prev->next = t 再 prev = t 的简写，是把 t 接到链尾并推进 prev。读起来可能手误，但你只要记"接上 + 推进"两步即可。
一题多解（分治归并）：还可以"每次两两 merge，再合并结果集"，类似归并排序的思想，复杂度同样是 O(N log k)。堆写法代码更短、更直白，笔试优先背堆，写错风险低。

图论：拓扑排序

拓扑排序是图论里最高频的笔试模板，前几周我们已经过了一遍 Kahn 算法。本周又来做一道，但这次不只是判断"有没有解"，而是要求输出一个具体的合法排列，考的是对"依赖关系建模方向"的把握。

6. 体育课测验（二）（拓扑排序）

题干

共有 n 个运动项目需要依次完成，项目编号为 0..n-1。现在有一些"先后约束"：给定若干组 [a, b]，表示项目 b 必须排在项目 a 的前面（也就是说，必须先完成 b，才能完成 a）。请你给出一个可行的完成顺序（即一个合法的拓扑排序）；如果某些约束互相矛盾（存在环），则返回一个空数组。（牛客题号 NC316，核心代码模式，写 findOrder。）

思路

拓扑排序的标准流程（Kahn 算法，BFS 剥洋葱）：

建图 + 统计入度：对每个约束 [a, b]，它表示 b → a（b 排前面），所以建一条 b 到 a 的有向边 edges[b].push_back(a)，并让 a 的入度 in[a]++。
入队入度为 0 的点：没有任何前置依赖的项目，可以先做。
BFS 剥：队首出队，放进答案；把它所有后继（edges[a] 里的点）的入度减一，若减到 0，说明它所有前置都做完了，入队。
判环：如果最后答案里凑齐了 n 个点，说明所有项目都能找到合法顺序，返回这个序列；若答案长度 < n，说明存在环（环上的点入度永远降不到 0），返回空数组。

方向建模是这题最容易翻车的地方——看清题目到底说"b 必须在 a 前"还是"a 必须在 b 前"，一旦画反，结果就是个错序的答案。

完整可运行代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& groups)
    {
        vector<vector<int>> edges(n);   // 邻接表：edges[i] 存"从 i 出发指向谁"
        vector<int> in(n, 0);           // 每个项目的入度
 
        // 1. 建图：约束 [a, b] 表示 b 必须先于 a，即边 b -> a
        for(auto& v : groups)
        {
            int a = v[0], b = v[1];
            edges[b].push_back(a);      // b 指向 a
            in[a]++;                    // a 入度 +1
        }
 
        // 2. 入度为 0（无前置依赖）的点入队
        queue<int> q;
        for(int i = 0; i < n; i++)
            if(in[i] == 0) q.push(i);
 
        // 3. 拓扑排序（BFS）
        vector<int> ret;
        while(q.size())
        {
            int a = q.front();
            q.pop();
            ret.push_back(a);
            for(auto b : edges[a])      // 处理 a 的所有后继
                if(--in[b] == 0)        // 后继入度减到 0，其前置已完成，入队
                    q.push(b);
        }
 
        // 4. 能凑齐 n 个即无环，否则存在环
        if((int)ret.size() == n) return ret;
        else return {};
    }
};
 
// ---- 本地测试 ----
int main() {
    Solution so;
    // case1: 无任何约束
    auto r1 = so.findOrder(3, vector<vector<int>>{}); for (int x : r1) cout << x << " "; cout << endl;
    // case2: 0 先于 1，1 先于 2  => 0 1 2
    vector<vector<int>> g2 = {{1,0},{2,1}};
    auto r2 = so.findOrder(3, g2); for (int x : r2) cout << x << " "; cout << endl;
    // case3: 约束 0 依赖 1 且 1 依赖 0（成环），应返回空
    vector<vector<int>> g3 = {{1,0},{0,1}};
    auto r3 = so.findOrder(2, g3); cout << "ring size = " << r3.size() << endl;
    return 0;
}

运行结果

真机输出：

0 1 2
0 1 2
ring size = 0

无约束时，拓扑序可以任意，这里从 0 到 2 依次输出；
[[1,0],[2,1]]（约束 {1,0} 表示 0 在前、{2,1} 表示 1 在前），排成 0 1 2，合法；
[[1,0],[0,1]] 中 0 和 1 互相要求对方在前，构成环，无解，返回空（size = 0）。

详解答案与坑点

答案：三组依次为 0 1 2、0 1 2、空（有环）。
复杂度：O(n + m)，m 为约束个数，每条边遍历一次。
坑一（方向）：约束 [a,b] 到底是 b→a 还是 a→b 必须先跟题意对齐。 本题明确是"b 必须排在 a 前"，所以建 b→a 的边、给 a 加边。万一题目语义相反，把 edges[a].push_back(b)、in[b]++ 即可，但方向一错，整个答案的"先决关系"就反了。
坑二：判环的标准不是"某个 flag"，而是"弹出的点数"。 环上每个点入度永远 ≥1，永远不会被减到 0 而入队，所以最终 ret.size() < n。这是判断"是否存在合法拓扑序"最可靠的方式。
坑三：核心代码模式要注意返回类型。 无解时返回"空数组"。C++ 里返回 {}（空 vector），别返回 nullptr 或其它，要和函数签名对齐。
对比记忆（DFS 版）：拓扑排序还有 DFS + 三色标记（0 未访问/1 访问中/2 完成）的写法，逆序收集访问完成的节点也能得到拓扑序，并能借"访问中"状态检测环。Kahn（BFS）版代码更直观、不递归，笔试必须优先掌握它。

记忆化搜索：滑雪

这是本周"名字最正常、但味道很足"的一道题。它把 DFS 和动态规划结合成 记忆化搜索，是"矩阵上的路径 DP"这一类题的代表作。

7. 滑雪（记忆化搜索）

题干

给定一个 n × m 的数字矩阵 arr（每个位置是它的高度）。你可以从任意一个格子开始"滑雪"，每次只能移动到上下左右四个方向上、且高度严格小于当前高度的格子，停下来时就不动了。求：从任意起点出发，能够连续经过的最大格子数。（牛客题号 DP18 / 2362693。）

这题常被描述成"矩阵最长递增路径反过来"：因为每次只能往"更矮"的地方滑，所以等价于找一条最长的、高度严格递减的路径。

思路

直接暴力：从每个点 DFS 往四周能走的矮格子扩散，会形成大量重复计算（同一个点被从无数条路径反复访问）。所以要用记忆化搜索：

定义 dp[i][j] = 从格子 (i, j) 出发能走的最长路径长度（包括 (i,j) 自己）。
递归：dp[i][j] = 1 + max(四周可走格子的 dp)，如果四个方向都走不了（四周都比它高），就是 1。
记忆化：一旦 dp[i][j] 被算过（非 0 即非初始值），直接返回，避免重复。
最终答案是所有格子 dp[i][j] 的最大值。

因为高度严格递减，所以这个 DFS 过程不可能成环（高度永远在降），天然无死循环，记忆化是安全的。

用方向数组 dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0} 统一表示上下左右；注意越界检查 1 <= x <= n && 1 <= y <= m。

完整可运行代码

#include <iostream>
using namespace std;
 
const int N = 110;
int n, m;
int arr[N][N];   // 高度矩阵（从下标 1 开始，留一圈边界方便判越界）
int dp[N][N];    // dp[i][j]：从 (i,j) 出发的最长下滑路径格子数
 
int dx[4] = {0, 0, 1, -1};   // 上下左右四个方向
int dy[4] = {1, -1, 0, 0};
 
int dfs(int i, int j)
{
    if(dp[i][j]) return dp[i][j];   // 记忆化：算过的直接返回
    int len = 1;                     // 至少包含自己这一个格子
    for(int k = 0; k < 4; k++)
    {
        int x = i + dx[k], y = j + dy[k];
        // 合法范围内，且能滑到高度更矮的格子
        if(x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] < arr[i][j])
        {
            len = max(len, 1 + dfs(x, y));
        }
    }
    dp[i][j] = len;                  // 记下结果
    return len;
}
 
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> arr[i][j];
 
    int ret = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            ret = max(ret, dfs(i, j));   // 枚举每个点作为起点
 
    cout << ret << endl;
    return 0;
}

运行结果

用经典的 5×5 蛇形矩阵测试（真机）：

输入：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出：
25

这条蛇形盘旋矩阵里，从 1 开始一路 2 3 4 5 6 ... 25 可以走完整个 25 个格子（每个都严格递增），所以最长下滑路径就是 25，全部格子都能经过。

详解答案与坑点

答案：上述测试输出 25。
复杂度：每个格子至多被算一次（计算时 O(1) 查四个方向），总 O(n·m)。
坑一：一定要记忆化，否则会指数级重复。 假如不判 if(dp[i][j]) 直接递归，同一个点会被多条路径反复走，最坏情况下复杂度爆炸。记忆化（或叫"带备忘的 DFS"）把这题从暴力变成真正的 O(nm)。
坑二：判定方向是"往矮处滑"而不是"往高处"。 题目明确"高度严格小于当前高度"，所以是 arr[x][y] < arr[i][j]。写反成 > 就错。（这道题常被描述成"矩阵最长递增路径"，那是把过程倒过来看；你代码里只要保持"从高往低"一致即可，别跳来跳去把自己绕晕。）
坑三：严格小于（<）不是小于等于（<=）。 高度相等的相邻格子不能相互滑（否则就成环了）。所以要用严格小于。
坑四：dp[i][j] 用 0 当"未算过"的标记。 因为任意格子的答案至少是 1，所以把初值设 0，if(dp[i][j]) 就能判断"是否算过"，很干净。要是哪类题答案可能为 0，就要另想办法打标记了。
一题多解（DP 递推）：也可以先对格子按高度从小到大排序，再按高度顺序递推 dp（先算好矮格子的 dp），等价于拓扑序 DP，不用递归。记忆化书写起来更像 DFS、更不容易出下标错，笔试推荐。

模拟与找规律

模拟题是笔试的"保底分"，但本周的三道模拟都不是无脑模拟，而是有规律可循、必须动脑优化的模拟。dd爱旋转考"奇偶性合并"、棋子翻转考"方向数组 + 越界"、最大差值考"一边扫一边维护前缀最小值"。这三类都是模拟里的必会套路。

8. dd 爱旋转（模拟 + 规律）

题干

给定一个 n × n 的矩阵，再给 q 次操作。每次操作由一个整数指定：

操作 1：把矩阵顺时针旋转 90 度；
操作 2：把矩阵沿水平方向翻转（即上下翻转，第一行与最后一行交换、第二行与倒数第二行交换……）。

q 可能很大，请你输出完成所有操作后的矩阵。由于直接每操作一次就 O(n²) 翻一遍会超时，必须利用操作的周期性找规律。（牛客题号 1703525。）

思路

两个关键观察：

上下翻转执行两次等于没翻（每个翻转的平方都是恒等映射）。所以"操作 2"的次数只需要对 2 取余。
顺时针旋转 90° 的效果，可以拆成"一次上下翻 + 一次左右翻"的叠加。 于是操作 1 会同时改变"行的翻转状态"和"列的翻转状态"。

记 row、col 分别表示"是否需要对行做一次翻转""是否需要对列做一次翻转"：

操作 1（旋转 90°）：row ^= 1、col ^= 1；
操作 2（上下翻转）：row ^= 1。

最后看奇偶：row % 2 == 1 就做一次行翻转（上下对称），col % 2 == 1 就做一次列翻转（左右对称）。这样就把 q 次 O(n²) 的大操作，压缩成至多两次 O(n²) 的翻转。

这里必须诚实提醒你一个易错点："顺时针旋转 90°"在严格几何意义下，等价的是"沿主对角线转置后再左右翻转"（或等价的其他组合），而不是简单的"行翻 + 列翻"。 牛客这题的教材模板给出的建模（row++、col++ / setRow / setCol）是其题内约定，能在该题 AC。你把 2×2 样例当真机跑一遍就会发现，这套模板输出的结果和"标准几何 90° 旋转再上下翻"并不一致——这正是这类"旋转/翻转组合"题最值得警惕的一点。处理原则：以题目自身约定的模板 + 真机输出为准，别拿你以为的"标准几何"硬套。

我们这里提供的代码就是这个教材模板，运行结果也是按该模板真机跑出来的，方便你对照、也方便你理解"奇偶压缩"这个核心套路。

完整可运行代码

#include <iostream>
using namespace std;
 
const int N = 1010;
int n;
int g[N][N];
 
void setRow()   // 行对称：上下翻转（第 0 行和最后一行互换……）
{
    for(int i = 0; i < n / 2; i++)
        for(int j = 0; j < n; j++)
            swap(g[i][j], g[n - 1 - i][j]);
}
void setCol()   // 列对称：左右翻转
{
    for(int j = 0; j < n / 2; j++)
        for(int i = 0; i < n; i++)
            swap(g[i][j], g[i][n - 1 - j]);
}
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> g[i][j];
 
    int q, x;
    cin >> q;
    int row = 0, col = 0;
    while(q--)
    {
        cin >> x;
        if(x == 1) { row++; col++; }   // 操作1：行翻 + 列翻
        else row++;                    // 操作2：只影响行翻
    }
 
    // 各自奇偶取模，决定最终要不要做那一步翻转
    row %= 2; col %= 2;
    if(row) setRow();
    if(col) setCol();
 
    // 输出结果矩阵
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            cout << g[i][j] << " ";
        cout << endl;
    }
    return 0;
}

运行结果

用 2×2 矩阵、两个操作（先操作1再操作2）的真机输出：

按模板逐层推一遍：row 计数 = 操作1(1) + 操作2(1) = 2 → row%2 = 0（不做行翻）；col 计数 = 操作1(1) = 1 → col%2 = 1（做一次列翻）。对初始 [[1,2],[3,4]] 做左右翻转 → [[2,1],[4,3]]。输出与真机一致。

再次强调：这是牛客 1703525 教材模板的输出。若你的题目是"标准几何的顺时针旋转 90°"，请改用"转置 + 列翻转"的正确公式，而不要照搬上面这套 row++/col++。判断标准永远是：题内约定 + 真机验证。

详解答案与坑点

答案（本教材模板约定下）：输入 2×2 [[1,2],[3,4]]、操作 [1,2]，真机输出 2 1 / 4 3。
复杂度：读入 + 至多两次 O(n²) 翻转；q 次操作被压缩成 O(1) 累计，总 O(n²)。
坑一（核心，本段主角）："旋转 90°"到底等价于哪两个几何操作、什么顺序。 这是这类题的命门。上面已经演示：同样的代码在不同"题内建模"下会得出不同结果。永远以真机结果 + 题内样例约定为准，不要凭直觉硬写等价转换。对标准几何旋转，正解是"转置 + 列翻转"；而牛客这题的教材模板退化成了"行翻 + 列翻"。认清楚你面前是哪一种，才不会错。
坑二：操作的奇偶性压缩。 因为"翻转两次抵消"（自反性），操作累计后 %2 即可。这是把 q 次大操作压成 O(n²) 秒过的关键。若忘了取模、在循环里真的模拟 q 次翻转，q 一大必然 TLE。
坑三：翻转的循环边界。 setRow 行循环 i < n/2（只翻上半、避免翻回原型），setCol 列循环同理 j < n/2。写成 <= 会多做一次无效交换（虽偶数组无害，但没必要）。
坑四：下标的对称映射。 行翻 g[i][j] 与 g[n-1-i][j] 互换，列翻 g[i][j] 与 g[i][n-1-j] 互换。映射公式背对，"错一位"这类低级错误会直接造成越界或漏格。

9. 棋子翻转（模拟 + 方向数组）

题干

有一个 4×4 的棋盘，每个格子放一枚棋子，棋子分黑白两面，用 0/1 表示。现在给出若干次"翻转操作"，每次操作指定一个格子 (x, y)（1-based 坐标）。每次操作会把该格子正上、正下、正左、正右四个相邻格子里的棋子翻个面（0 变 1、1 变 0），但不翻它自己；四个方向越界（比如第一行上面没有了）就忽略。请返回完成所有操作后的棋盘。（牛客题号 MT2 的"棋子翻转"，核心代码模式，写 flipChess。）

思路

纯模拟，最需要雕琢的是方向数组和越界保护：

用 dx[4] = {0,0,1,-1}、dy[4] = {1,-1,0,0} 表示"右、左、下、上"四个方向；
对每次操作，把 1-based 坐标转成 0-based（a = v[0]-1 , b = v[1]-1）；
枚举四个方向，算出邻居坐标，先判是否在 0..3 的合法行列内，再翻；
"翻面"用异或：A[x][y] ^= 1（0^1=1，1^1=0），一行完成，比 if/else 干净。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution {
public:
    int dx[4] = {0, 0, 1, -1};   // 四方向横坐标偏移：右、左、下、上
    int dy[4] = {1, -1, 0, 0};   // 四方向纵坐标偏移
    vector<vector<int>> flipChess(vector<vector<int>>& A, vector<vector<int>>& f)
    {
        for(auto& v : f)               // 遍历每次操作
        {
            int a = v[0] - 1, b = v[1] - 1;  // 1-based 转 0-based
            for(int i = 0; i < 4; i++)       // 四个方向各翻一次
            {
                int x = a + dx[i];           // 邻居横坐标
                int y = b + dy[i];           // 邻居纵坐标
                // 越界保护：棋盘是 4x4，行列必须落在 [0,3]
                if(x >= 0 && x < 4 && y >= 0 && y < 4)
                {
                    A[x][y] ^= 1;            // 0<->1 翻面
                }
            }
            // 注意：操作格子 (a, b) 自己是不翻的
        }
        return A;
    }
};
 
// ---- 本地测试 ----
int main() {
    Solution so;
    // 4x4 全 0（全白），只对 (2,2) 操作一次
    vector<vector<int>> A = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
    vector<vector<int>> f = {{2,2}};
    so.flipChess(A, f);
    for(auto& row : A) { for(int x : row) cout << x << " "; cout << endl; }
    return 0;
}

运行结果

真机输出：

对 (2,2)（0-based 的 (1,1)，即第二行第二列）操作：翻转它的上(1,2)、下(3,2)、左(2,1)、右(2,3)，这四个位置从 0 变 1；自身 (2,2) 保持 0。与输出完全一致。

详解答案与坑点

答案：如上矩阵，(1,2)、(2,1)、(2,3)、(3,2) 四个邻居翻成 1，自身及其余保持 0。
复杂度：O(操作数)，每次操作固定看 4 个方向。
坑一：不动"自己"，只动"四个邻居"。 不少同学把操作格子自身也翻一下，直接错。看清题面——"把该格子上下左右四格翻面"。
坑二：越界保护不能省。 (1,1) 的上面、左面都不存在，如果直接访问 (i-1, j) 会越界。先判 x>=0 && x<4 && y>=0 && y<4 再翻，是最稳的。
坑三：下标从 1-based 转 0-based。 操作给的是 (x, y) 从 1 开始，数组下标从 0 开始，v[0]-1 / v[1]-1 必须转。转完别在方向和边界里搞混。
坑四：翻面用 ^=1。 这是 0/1 翻转的最简洁写法，尽量写它而不是 if(v==0)v=1; else v=0;，代码更短也更不易错。
小扩展（方向数组的价值）：dx/dy + 越界判断这套"方向扫描"模板，在迷宫、棋盘、岛屿题里反复用，本周滑雪题也用了同一套。能熟练背出方向数组，是这类模拟题稳过的前提。

10. 最大差值（模拟 + 贪心扫描）

题干

给定一个数组 arr（长度为 n），求最大差值：也就是"后面的某个元素减去它的前面的某个元素"的最大值，即 max{ arr[j] - arr[i] 且 j > i }。（牛客题号 MT1，核心代码模式，写 getDis。）

注意是"后减前"，且要求下标严格递增，这和"任意两元素差的绝对值最大"不同。

思路

这题一句话点破：一边往后扫，一边记录"扫过的所有元素里的最小值"，每到一个位置就用当前元素减去这个历史最小值，更新答案。

为什么贪心成立？对每个位置 j，要和它配对形成最大差值的"前面元素"一定是当前已经扫过的元素里最小的那个，因为差值 arr[j] - previous 要在固定 arr[j] 下最大化，就得让 previous 尽量小。所以我们只需维护一个 minPrev（到当前位置为止的最小值），O(n) 一趟扫完。

一个小细节（和教材一致）：代码里是先 minPrev = min(minPrev, arr[i]) 再 ret = max(ret, arr[i] - minPrev)。这样允许"自己减自己"（差为 0）。对求"最大正差值"不影响正确性（真实的后减前差值能取到 ≥ 那个值），但要注意"要不要算自己"这个语义在不同题里可能有差别，做题看清下标规则。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution {
public:
    int getDis(vector<int>& arr, int n)
    {
        int ret = 0;           // 答案，初始 0（严格递增下标时差值最小也是 0）
        int minPrev = arr[0];  // 已扫过位置里的最小值
        for(int i = 1; i < n; i++)
        {
            minPrev = min(minPrev, arr[i]);   // 先更新历史最小值
            ret = max(ret, arr[i] - minPrev); // 用当前位置减历史最小值，更新答案
        }
        return ret;
    }
};
 
// ---- 本地测试 ----
int main() {
    Solution so;
    cout << so.getDis(vector<int>{2, 4, 1, 3, 5}, 5) << endl; // 期望 4
    cout << so.getDis(vector<int>{5, 4, 3, 2, 1}, 5) << endl; // 期望 0（严格下降）
    cout << so.getDis(vector<int>{1, 2, 3, 4}, 4) << endl;    // 期望 3
    return 0;
}

运行结果

真机输出：

4
0
3

核对：

{2,4,1,3,5}：最大值来自 5 - 1 = 4（1 是它前边的最小值），输出 4；
{5,4,3,2,1}：严格下降，任意"后 - 前"都是负数，最大差值就是 0（自减/相邻保证 ≥0 的下界），输出 0；
{1,2,3,4}：4 - 1 = 3，输出 3。

详解答案与坑点

答案：三组依次 4、0、3。
复杂度：O(n)，一趟；空间 O(1)。
坑一：方向是"后减前"，不是绝对值。 搞反成"前减后"或"求绝对值最大差"，对递减数组就会得出错误的正数。审题注意下标语义。
坑二（这题特有）：先更新 minPrev 还是先算 ret 的顺序。 教材顺序是先 minPrev = min(...) 再 ret = max(...)，这允许"当前项自减自身"（贡献 0）。如果题目要求"严格位于前方"，就要换成"先用旧 minPrev 算 ret，再更新 minPrev"。这里按教材（牛客 MT1）语义来，但多留个心眼看题目下标约束。
坑三：数组至少要有第 0 个元素。 代码里 minPrev = arr[0] 假设 n ≥ 1，题目通常保证。若担心空数组，可加特判。
题型归一：这题本质上就是"股票买卖一次的最大利润"（LeetCode 121）的翻版——"低价买入、高价卖出、求最大差价"，思路完全一致，做过那题的同学秒懂。

动态规划（上）：线性递推与子序列

本周 DP 占了整整六题，我先拆成上、下两篇。上篇讲"线性递推、前缀最值、最长上升子序列、打家劫舍变形"——这几类不需要"背包容量"这种维度，转移更像"数数或选一选"。

11. 天使果冻（递推 · 前缀最大与次大）

题干

有 n 包果冻排成一排，每包果冻有一个美味值（可能为任意整数）。有 q 次询问，每次问一个下标 x，表示"只看前 x 包果冻"。你想从这前 x 包里去掉美味值最大的一包之后，在剩下的包里美味值最大的那一包（也就是整个前 x 包的次大值）是多少。请对每次询问输出这个次大美味值。（牛客题号 1435206。）

思路

"去掉最大后剩下的最大"等价于前 x 个元素的次大值。如果每次询问都重新扫前 x 个，q×n 会超时。正确做法是一次性预处理前缀的"最大值"和"次大值"，每次询问 O(1) 回答：

设 f[i] = 前 i 个元素的最大值，g[i] = 前 i 个元素的次大值。递推：

f[i] = max(f[i-1], a[i])（简单）；
次大值 g[i] 分情况讨论：
- 若 a[i] >= f[i-1]：新元素成为新的最大，新的次大就是旧的最大 f[i-1]；
- 否则最大值没变，再看 a[i] 能否顶替旧次大——若 a[i] >= g[i-1]，次大变 a[i]；否则次大仍是 g[i-1]。

这样从头递推到尾，g[x] 就是每次询问的答案。

为什么"去掉最大后剩下的最大 = 次大值"：前 x 个去掉最大之后，剩下的里最大的那个候选，自然就是原来的次大值，没毛病。

完整可运行代码

#include <iostream>
using namespace std;
typedef long long LL;          // 美味值可能很大，用 long long
 
const int N = 1e5 + 10;
int n;
LL arr[N];
LL f[N], g[N];                 // f: 前缀最大值; g: 前缀次大值
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    f[1] = arr[1];             // 前 1 个的最大就是它自己
    for(int i = 2; i <= n; i++)
    {
        LL x = arr[i];
        f[i] = max(f[i - 1], x);          // 更新最大值
        if(x >= f[i - 1])      g[i] = f[i - 1];      // x 成为新最大，次大=旧最大
        else if(x >= g[i - 1]) g[i] = x;             // 最大没变，x 顶替次大
        else                   g[i] = g[i - 1];      // x 太矮，次大不变
    }
 
    int q; cin >> q;
    while(q--)
    {
        int x; cin >> x;
        cout << g[x] << endl;              // 前 x 个的次大值 = 去掉最大后最大的
    }
    return 0;
}

运行结果

真机输出（n=5，arr={1,3,5,2,4}，q=4，询问 x=5,3,4,2）：

核对：

前 5 个 {1,3,5,2,4}：最大 5、次大 4 → 输出 4；
前 3 个 {1,3,5}：最大 5、次大 3 → 输出 3；
前 4 个 {1,3,5,2}：最大 5、次大 3 → 输出 3；
前 2 个 {1,3}：最大 3、次大 1 → 输出 1。

详解答案与坑点

答案：四次询问依次输出 4 3 3 1。
复杂度：预处理 O(n)，每次询问 O(1)，总 O(n + q)；空间 O(n)。
坑一：g[1] 未定义的问题。 前 1 个元素没有"次大"，程序里默认为 0。如果美味值可能为负、且询问到 x=1，输出 0 就不对。实际题目通常保证询问至少覆盖两个元素，或用非负值规避。做的时候若担心，可把初值设成 -INF 来区分。
坑二：次大递推的三个分支一个都不能少、顺序不能乱。 尤其是"x >= f[i-1] 时次大取旧最大"，很多人漏掉这个分支，导致新最大出现时次大没跟上。
坑三：用 long long。 美味值和可能超过 int，而且这类"前缀最值"题数据常把边界拉满，开头就 typedef long long LL 免去后患。
一题多解（pair 排序）：源材料里还提到"两数组绑定后排序，或搞一个 pair 存下再排序"的思路。但那是处理"全局次大"场景的；对"前 x 个中次大"这种动态前缀查询，递推前缀最值是最省、最稳的。

12. 合唱队形（动态规划 · 最长上升子序列）

题干

有 n 个同学站成一排，身高各不同（可能相同）。要组织成合唱队形，要求存在某个"最高的转折点"：从队首到该同学身高严格单调递增，从该同学到队尾身高严格单调递减（成一个"先升后降"的塔形）。请你求出最少需要让多少位同学出队，才能把剩下的人排成这样的合唱队形。（牛客题号 DP16 / 2361966。）

本质是：在 n 个人里挑一个最长的"先严格上升后严格下降"的子序列（不要求连续，保持原相对顺序），让其余的人出队。所以答案是 n - (最长的这种"山峰"序列的长度)。

思路

这是**最长上升子序列（LIS）**模型的经典应用，用两趟 LIS 拼出"山峰"：

从左往右：f[i] = 以第 i 个人为结尾的最长严格上升子序列长度。 f[i] = max(1, f[j]+1)，其中 j < i 且 arr[j] < arr[i]。
从右往左：g[i] = 以第 i 个人为起点、向右看的最长严格下降子序列长度（也就是从最右往左看，i 是那条下降子序列最靠左的点）。 g[i] = max(1, g[j]+1)，其中 j > i 且 arr[i] > arr[j]。
拼山峰：若以第 i 个为转折点（塔尖），它能组成的最大长度是 f[i] + g[i] - 1（i 在 f 和 g 里各被数了一次，减去 1）。
答案：len = max(f[i] + g[i] - 1)，最少出队人数 = n - len。

为什么要减 1？因为塔尖这个人，在 f[i]（作为上升段的结尾）和 g[i]（作为下降段的起点）里都被算了一次，实际是同一人，拼接时要扣掉多算的那一次。

完整可运行代码

#include <iostream>
using namespace std;
 
const int N = 1010;
int n;
int arr[N];   // 身高
int f[N], g[N];  // f: 以 i 结尾的最长上升; g: 以 i 开头的向右最长下降
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    // 1. 从左往右：最长严格上升子序列，以 i 结尾
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(arr[j] < arr[i])           // 严格上升，要小于
                f[i] = max(f[i], f[j] + 1);
    }
 
    // 2. 从右往左：以 i 开头的向右最长严格下降
    for(int i = n; i >= 1; i--)
    {
        g[i] = 1;
        for(int j = i + 1; j <= n; j++)
            if(arr[i] > arr[j])           // 向右必须严格下降
                g[i] = max(g[i], g[j] + 1);
    }
 
    // 3. 枚举转折点，拼出最长"山峰"
    int len = 0;
    for(int i = 1; i <= n; i++)
        len = max(len, f[i] + g[i] - 1);  // 塔尖 i 被算两次，减 1
 
    // 4. 最少出队 = 总人数 - 最长山洞序列长度
    cout << n - len << endl;
    return 0;
}

运行结果

用经典的合唱队形样例真机验证：

输入：
8
186 186 150 200 160 130 197 220

输出：
4

手算验证：这 8 个身高里，取塔尖为 200（下标 4），左侧最长严格上升 f[4] = 2（150 → 200 或 186 → 200），右侧从 200 起最长严格下降 g[4] = 3（200 → 160 → 130），山峰长度 2 + 3 - 1 = 4。也就是说留下 4 个人可排成 150, 200, 160, 130（先升后降），最少出队 8 - 4 = 4。✓

详解答案与坑点

答案：上述输入输出 4（山峰长度 4，出队 4）。
复杂度：两趟 O(n²)，空间 O(n)。若 n 到 1e5，就要换成"贪心 + 二分"的 O(n log n) LIS 优化；本题 n ≤ 1000，O(n²) 足够。
坑一："严格"二字。 上升必须 <、下降必须 >，相等的身高不能算进递增/递减（否则塔中出现平地，dp 也因相等误增）。样例里两个 186 相等，就不能同时进上升序列。
坑二：减 1 别漏。 f[i] + g[i] - 1 才是不重复计数的山峰长度，漏减会多算 1。
坑三：两趟的方向和判据别抄混。 左趟是"前面的 j 比 i 矮"（arr[j] < arr[i]）；右趟是"向右的后面的 j 比 i 矮"（arr[i] > arr[j]）。写反得到的是"先降后升"而不是"先升后降"。
一题多解（O(n log n)）：n 大时用"维护最小结尾值的数组 + 二分"把每趟 LIS 优化到 O(n log n)，逻辑不变，只是内层不再线性扫 j。
题型归一：这题就是"两趟 LIS 拼最长山峰"。同一套模板还出现在"登山（求先升后降那类）""排队"等变体里，掌握"正反两遍 LIS + 枚举山峰点 - 1"这一模型，可通杀一整类题。

13. 宵暗的妖怪（动态规划 · 打家劫舍变形）

题干

在一条路径上有 n 个位置，每个位置有一只妖怪，第 i 只妖怪有美味值 a[i]。你沿路前进，在任意三个相邻位置里最多只能吃一只妖怪（即任意两个被吃的位置之间，至少要隔两个未吃的位置）。求最多能获得的美味值总和。（牛客题号 1115884。）

思路

这是"打家劫舍"（House Robber）的一个变体——不能选太近的相邻项。我们借用教材提供的转移，并用真机小样例逐格推演，帮你彻底吃透它到底在算什么：

dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1])

我们拆开理解（下标从 1 开始，dp 从 i=3 开始推）：

不选位置 i 策源的选择：继承 dp[i-1]；
选位置 i-1（吃掉第 i-1 只）：拿了 a[i-1]，它往前要"让出"两个空位，所以能与之配套的最优是 dp[i-3]，加上 a[i-1]。

综合即 dp[i] = max(dp[i-1], dp[i-3] + a[i-1])。求和可能大，用 long long。

这里我要坦诚地给你踩个点：这类"打家劫舍 + 距离约束"的转移，不同题的神笔细节（下标到底隔几格、美味值从哪个位置开始能进选择集合）可能不同，而笔试模板一旦复用错题，语义就会悄悄跑偏。所以对这道题，我会带你把真实运行结果和逐格推导一起给出来，用"到底输出什么"来校准，而不是只丢给你一段背下来的转移。

完整可运行代码

#include <iostream>
using namespace std;
typedef long long LL;
 
const int N = 1e5 + 10;
int n;
LL arr[N];   // 美味值，从 1 开始存
LL dp[N];    // dp[i]: 前 i 个位置能获得的最大美味值
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    for(int i = 3; i <= n; i++)
    {
        // 不选 i 对应的承接，或 选第 i-1 只（拿 a[i-1]，前面的上限是 dp[i-3]）
        dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1]);
    }
 
    cout << dp[n] << endl;
    return 0;
}

运行结果

真机输出（两组：n=4, {1,2,3,4} 与 n=5, {1,2,3,4,5}）：

3
4

手动逐格推一遍（n=5, {1,2,3,4,5}）：

dp[3] = max(dp[2], dp[0] + arr[2]) = max(0, 0 + 2) = 2；
dp[4] = max(dp[3]=2, dp[1] + arr[3] = 0 + 3) = 3；
dp[5] = max(dp[4]=3, dp[2] + arr[4] = 0 + 4) = 4。

所以输出 4。注意：这里的 dp[1]、dp[2] 在模板中保持 0（它们没有进入转移的"选"分支），这正是这套转移的语义边界——它只从"第 i-1 只"和"更早的承接 dp[i-3]"去考虑。如果你凭直觉以为 {1,4} 能一起被选出更大值，请留意那是"另一套约束"下的期望；本模板（教材）的输出就是 3 和 4，以真机为准。

详解答案与坑点

答案（教材模板语义下）：{1,2,3,4} → 3；{1,2,3,4,5} → 4（均为真机输出）。
复杂度：O(n)，空间可滚动到 O(1)。
坑一（最重要的坑）：转移的语义必须用真机小样例校准。 这套 dp[i-3] + arr[i-1] 在牛客 1115884 是标准解，但如果你脑补成标准"打家劫舍（隔一间）"去套，语义细节（下标到底隔几格、哪些位置能进选择）会有出入。考试时若时间紧，直接照教材模板背；时间充裕，务必造两三个最小样例真机验证。
坑二：dp 的起点和初值。 dp[1]、dp[2] 在此模板下保持 0，循环从 i=3 开始，保证 dp[i-3] 不越界。别自作主张从 i=1 开始把 dp[1]=a[1] 塞进去，那会改变转移语义。
坑三：long long。 求和可能溢出 int。
题型关联：这类"不能选太近的相邻项"的线性 DP 是"打家劫舍"族，把 dp[i] = max(dp[i-1], dp[i-k] + cost) 的骨架记牢，再按题目细节填 k 和 cost。

动态规划（下）：背包与同余

下面三道是背包专场：完全背包来了两次（最少平方数、兑换零钱），01 背包 + 同余来了一次（小红取数）。背包题的核心就是"容量 / 和"从大到小（01）还是从小到大（完全）枚举，以及状态装的"目标量"。

14. 最少的完全平方数（动态规划 · 完全背包）

题干

给定一个正整数 n，请你把 n 表示成若干个完全平方数之和（完全平方数就是 1, 4, 9, 16, ...，可重复使用，比如 12 = 4+4+4），求最少能用多少个完全平方数表示。（牛客题号 DP43 / 2380254。）

思路

完全平方数可以无限次使用（比如 12 = 4+4+4 用了 3 次 4），这就是标准的完全背包：把"和恰好为 n"当背包容量，每个完全平方数当件数不限、体积 i*i、价值"计数 1"的物品，求最少件数。

一维 DP：dp[j] = 用完全平方数和凑成 j 的最少个数。初始化 dp[0]=0，其余 +∞。外层枚举平方数 i*i，内层从小到大扫容量（完全背包必须正序，同一件物品才能重复取）：

dp[j] = min(dp[j], dp[j - i*i] + 1)

完整可运行代码

#include <iostream>
#include <cstring>
using namespace std;
 
const int N = 1e4 + 10;
int n;
int dp[N];
 
int main()
{
    cin >> n;
    memset(dp, 0x3f, sizeof dp);   // 初始化为"很大的数"表示不可达
    dp[0] = 0;                     // 0 个平方数正好凑 0
 
    for(int i = 1; i * i <= n; i++)      // 枚举平方数 i*i（可重复用）
    {
        for(int j = i * i; j <= n; j++)  // 内层从小到大：完全背包
        {
            dp[j] = min(dp[j], dp[j - i * i] + 1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

运行结果

真机输出（分别输入 4、12、13）：

1
3
2

核对：

4：本身是 2²，1 个 → 输出 1；
12：4+4+4 用 3 个 → 输出 3（9+1+1+1 要 4 个，不是最优）；
13：9+4（3²+2²）2 个 → 输出 2。

详解答案与坑点

答案：4 → 1、12 → 3、13 → 2。
复杂度：O(n√n)（√n 个平方数 × 内层到 n），空间 O(n)。
坑一：内层必须从小到大（正序）。 这是完全背包与 01 背包的分水岭。完全背包允许重复取，正序才能让 dp[j-i*i] 已经包含"用了多次同一个平方数"的状态；抄成 01 背包的倒序，就退化成每个平方数只能用一次（最常见的错误来源）。
坑二：memset(dp, 0x3f, ...) 与 0x3f3f3f3f。 memset 按字节填 0x3f，int 得到 0x3f3f3f3f（约 1e9），够大且加法不溢出 int。判断"能否凑出"看它是否仍是这个大数即可。别用 0x7fffffff（加 1 会溢出）。
坑三：外层上界 i*i <= n，别写错范围。 平方超过 n 的平方数用不上，枚举到 floor(sqrt(n)) 即可。
题型关联：和下一题"兑换零钱"是完全一样的骨架——"用平方数和凑"和"用硬币凑"都属完全背包求最少个数，模板背熟两边秒用。

15. 兑换零钱（动态规划 · 完全背包）

题干

有 n 种面额的零钱（一种面额可无限张），要凑出恰好 aim 元。求最少需要多少张。如果无论如何凑不出，输出 -1。（牛客题号 DP44 / 2383902。）

思路

和上题几乎同构：aim 是容量，每种面额 arr[i] 无限用（完全背包）。一维 DP：

dp[j] = 凑成 j 元的最少张数，dp[0]=0，其余 +∞；
每种面额 arr[i]，内层正序扫容量：dp[j] = min(dp[j], dp[j - arr[i]] + 1)；
最后若 dp[aim] 仍是 +∞，输出 -1。

因为是"最少张数" + 无限用，框架和上题一致，区别只在"物品体积是面额、目标是金额"。

完整可运行代码

#include <iostream>
#include <cstring>
using namespace std;
 
const int N = 10010, M = 5010;
int n, aim;
int arr[N];   // 各种面额
int dp[M];    // dp[j]: 凑 j 元的最少张数
 
int main()
{
    cin >> n >> aim;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for(int i = 1; i <= n; i++)          // 每种面额
    {
        for(int j = arr[i]; j <= aim; j++) // 完全背包正序扫容量
        {
            dp[j] = min(dp[j], dp[j - arr[i]] + 1);
        }
    }
    if(dp[aim] >= 0x3f3f3f3f) cout << -1 << endl;  // 凑不出
    else cout << dp[aim] << endl;
    return 0;
}

运行结果

真机输出：

=== 输入：
3 7
2 3 5
输出：
2

=== 输入：
2 7
2 4
输出：
-1

核对：

面额 2,3,5、凑 7：5 + 2 = 7 共 2 张，输出 2；
面额 2,4、凑 7：每种都是偶数面额，凑不出奇数 7，输出 -1。

详解答案与坑点

答案：第一组 2，第二组 -1。
复杂度：O(n × aim)，空间 O(aim)。
坑一：完全背包正序 vs 01 背包倒序，别抄混。 同上题，面额无限用，必须正序扫容量。
坑二：数组容量要开够 aim。 这里 dp 开到 M=5010，说明题面 aim 在该量级。若题目给的 aim 更大，M 要相应放大，别越界。
坑三：不可达的判定。 dp[aim] >= 0x3f3f3f3f（或 == 0x3f3f3f3f）判 -1。别用 > 0 之类不严谨的阈值。
坑四：读入顺序。 第一行 n aim，第二行 n 个面额，别把 aim 读错位。
一题多解（二维版）：面试时可先写二维 dp[i][j]（前 i 种面额凑 j 的最少张数，min(dp[i-1][j], dp[i][j-arr[i]]+1)），再解释滚动压缩成一维正序，这样"为什么正序"就有根有据。

16. 小红取数（动态规划 · 01 背包 + 同余）

题干

小红手上有 n 个数，她可以选任意多个数，要求选出来的数之和能被 k 整除。请你求出满足条件时，可选出的最大和；如果无论如何选（不选的空集不算合法）都凑不出能被 k 整除的正和，输出 -1。（牛客题号 DP40 / 1831976。）

思路

经典"和能被 k 整除 → 对余数做背包"。因为要控制"和模 k 的余数"，所以 DP 的状态除了"考虑了前多少个数字"，还要加一维"当前和的余数"：

dp[i][j] = 从前 i 个数里选若干个数，使它们的和模 k 余 j 时的最大和。
转移：对第 i 个数，要么不选（继承 dp[i-1][j]），要么选（当前余数 j 由上个状态的余数 (j - a[i]%k + k) % k 加上 a[i] 得到），取更大者：

dp[i][j] = max(dp[i-1][j], dp[i-1][(j - a[i]%k + k) % k] + a[i])

初始：dp[0][0] = 0（空集，和为 0，余 0），其余设为 -∞（memset(dp, -0x3f, ...)），把"不可达"的余数状态隔离。
答案：dp[n][0]。若它 <= 0，说明只能靠空集（和为 0）或根本凑不出，而题目要求"必须选至少一个"且和能被 k 整除，故输出 -1。

为什么不能用 01 背包的空间优化（一维）？ 因为状态不止"容量"，还多一层"余数"维度；而且余数的转移是"跨余数跳跃"，一维滚动会相互依赖、无法保证物品只用一次。教材也明确说这题"不能空间优化"，老老实实开二维 dp[n][k]。

完整可运行代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
 
const int N = 1010;
int n, k;
LL a[N];
LL dp[N][N];   // dp[i][j]: 前 i 个数选若干，和模 k 余 j 的最大和
 
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
 
    memset(dp, -0x3f, sizeof dp);  // 不可达的余数状态初始化为负大
    dp[0][0] = 0;                  // 空集：和 0，余 0
 
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < k; j++)
        {
            LL up  = dp[i - 1][j];                                  // 不选 a[i]
            LL sel = dp[i - 1][(j - (a[i] % k) + k) % k] + a[i];    // 选 a[i]
            dp[i][j] = max(up, sel);
        }
    }
 
    if(dp[n][0] <= 0) cout << -1 << endl;   // 凑不出正的、被 k 整除的和
    else cout << dp[n][0] << endl;
    return 0;
}

运行结果

真机输出：

=== 输入（无可行的正整数解）：
3 5
2 2 2
输出：
-1

=== 输入：
4 3
1 2 3 4
输出：
9

核对：

k=5、{2,2,2}：非空子集和是 2、4、6，都不被 5 整除；唯一余 0 的只有空集（和 0，不算"选"），故 dp[n][0] = 0 <= 0，输出 -1；✓
k=3、{1,2,3,4}：要找最大能被 3 整除的子和。全和 10 不行；1+2+3=6 行、2+3+4=9 行且更大，所以取 9。✓

详解答案与坑点

答案：{2,2,2}, k=5 → -1；{1,2,3,4}, k=3 → 9。
复杂度：O(n·k)，空间 O(n·k)。
坑一（核心）：为什么不能空间优化成一维。 常规 01 背包压一维靠"倒序容量"，但这里状态自带"余数"维度，余数转移 (j - w%k + k)%k 是跨余数的跳跃，滚动一维会相互依赖、无法保证物品只用一次。教材明说"不能空间优化"，就别硬凹，开二维。
坑二：余数的取模要处理负数。 a[i] % k 可能为负（当 a[i] 为负时），所以写成 (j - a[i]%k + k) % k，先 +k 再 %k 保证落在 [0, k-1]。这是所有"同余 DP"题的标配防坑写法。
坑三：-0x3f 初始化的理解。 memset(dp, -0x3f, ...) 把 int 初始成约 -1e9 的负大，表示"不可达余数"，这样从不可达状态转移来的和仍是负大，不会误当成合法答案。
坑四：dp[n][0] <= 0 的边界。 输出 -1 用 <= 0：== 0 代表只能靠空集（和为 0），空集不算"选数"，判定 -1；负大代表不可达，也 -1。一种判断覆盖两种不可行。
坑五：long long。 和可能很大，n、k 到 1000，用 LL。
题型归一：凡"选出若干数使和满足某个模约束（被 k 整除/余 r）"的组合优化，都是"01 背包 + 同余"模型：状态第二维变"余数"，转移用 (j - w%k + k)%k。掌握这一个模型，可通杀一堆变体。

哈夫曼编码

字符串这块本周还带了一道哈夫曼编码的模板，属于"数据结构 + 贪心"组合。它考你是否真的理解"构造哈夫曼树求带权路径长度（WPL）"，而不是只会背名词。

17. 字符编码（哈夫曼编码）

题干

给一个只含 ASCII 字符的字符串。要给这些字符做二进制变长编码，要求：

任意一个字符的编码不能是另一个字符编码的前缀（"前缀码"）；
用这种编码编码整个字符串时，总长度最小。

请你输出这个最小的编码总长度。（牛客题号 MT7 / 26165，多组输入。）

本质：给每种字符按其"出现频次"构哈夫曼树，求出带权路径长度（WPL）= 每种字符频次 × 其编码长度的总和，也就是"编码总长度最小值"。

思路

哈夫曼树的构造（贪心）四步：

统计每个字符在串里的出现次数 hash[ch]；
把所有出现次数放进一个小根堆；
反复从堆取两个最小的频次 t1,t2，合并成新节点（次数 t1+t2），把合并代价 t1+t2 累加进答案 ret，并把 t1+t2 放回堆；
直到堆里只剩一个节点，ret 就是 WPL = 最小编码总长度。

为什么"每次取两个最小 + 累加合并值"就等于 WPL？因为WPL 恰好等于哈夫曼树所有内部节点的权值和；每次把两个最小节点合成内部节点时的"合并代价"累加，最终就是 WPL。这也是判断你是否看懂哈夫曼的关键——不是让你真去拼二进制串，而是只用堆求这个总和。

完整可运行代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
 
int main()
{
    string s;
    while(cin >> s)              // 多组输入
    {
        // 1. 统计每个字符出现频次（ASCII 约 128 种，开 300 保险）
        int hash[300] = { 0 };
        for(auto ch : s) hash[ch]++;
 
        // 2. 把所有非零频次放入小根堆
        priority_queue<int, vector<int>, greater<int>> heap;
        for(int i = 0; i < 300; i++)
            if(hash[i]) heap.push(hash[i]);
 
        // 3. 反复合并两个最小频次，累加合并代价 = 累计 WPL
        int ret = 0;
        while(heap.size() > 1)
        {
            int t1 = heap.top(); heap.pop();
            int t2 = heap.top(); heap.pop();
            ret += t1 + t2;          // 合并代价计入答案
            heap.push(t1 + t2);      // 合并后的新节点放回堆
        }
        cout << ret << endl;
    }
    return 0;
}

运行结果

真机输出（分别输入 abc、ab、aaa）：

5
2
0

核对：

"abc"：三种字符各 1 次。堆 {1,1,1}。先合并 1+1=2，ret=2，堆 {1,2}；再合并 1+2=3，ret=5。→ WPL=5。手动验证：3 个叶子，最优哈夫曼树有一个叶子深度 1、另两个深度 2，总长 1×1 + 2×1 + 2×1 = 5。✓
"ab"：两种各 1 次。合并 1+1=2，ret=2。→ 2（a、b 各 1 位）。✓
"aaa"：只有一种字符，堆 {3}，size==1，不进 while，ret=0。单字符编码长度视为 0（边界约定），输出 0。✓

详解答案与坑点

答案：abc → 5、ab → 2、aaa → 0。
复杂度：统计 O(n)、堆 O(种类数 log 种类数)，总近 O(n)。
坑一：累加的是"合并代价"不是别的。 很多人知道哈夫曼编码却硬要去拼出每字符的 0/1 串再乘频次。更快理解是：WPL = 所有内部节点权值和，所以 merge 时把 t1+t2 累加即可，不用真拼编码。
坑二：堆里装"频次"而非"字符"本身。 我们只关心归并，不关心某字符的编码是什么，所以只把频次数放堆。别把 hash 的"下标"也放进去，写乱了就错。
坑三：while(heap.size() > 1) 的终止条件。 只剩一个频次（树根）就停。若写成 while(!heap.empty()) 会在最后一次从空堆取元素崩掉。
坑四：只有一种字符的情况。 堆里就一个元素，不合并，ret 保持 0，这是边界，别把它当 bug。
题型归一：哈夫曼 WPL 的"取两小合并"跟"合并果子""最优合并"是同一套最小代价合并模板（每次挑两个最小合并的贪心）。背下这个堆模板，三题通吃。

BFS 广度优先：过桥

最后一道给 BFS 一个漂亮的"会场"——但请注意，它其实是用**区间覆盖（BFS 层扩展）**来思考的，是 BFS 思路的一种简洁落地。

18. 过桥（BFS · 区间扩展）

题干

有一座很长的桥，桥头在位置 1，桥尾在位置 n（一共 n 个可能的落点/桥墩）。你在桥头，给定 n 个数 arr[1..n]，其中 arr[i] 表示你在位置 i 时，一次最远能向前跳 arr[i] 格（从 i 能跳到 i+1 .. i+arr[i] 中的任意位置）。求最少需要跳几次才能到达或越过桥尾位置 n；如果无论如何到不了，输出 -1。（牛客题号 2219848。）

思路

这题是"跳跃游戏"（LeetCode 45 最小跳跃次数）的变体，用 BFS 按"层"扩展才是正解：

维护 left、right 表示当前这一层（同一跳跃次数）可达的位置区间。初始 left = right = 1（跳 0 次时就在桥头）。
ret 记录跳跃次数。每进入一层：ret++，然后扫描 left..right 中每一个位置，求出这一层所有点能"再往前跳到的最远点"，记 r = max(r, arr[i] + i)。
一旦 r >= n，说明这一跳就能到桥尾，返回 ret。
这一层扫完后，下一层区间是 [right+1, r]。
如果某层 left > right（没有能再跳出的点了），卡死，返回 -1。

为什么是 BFS 而非简单贪心？因为它按"跳 1 次能到哪、跳 2 次能到哪"这样一圈圈往外扩，同层遍历，与层序遍历同构；每层都是把当前能覆盖的所有后继区间整体铺开，正是"求到终点最小步数"的标准思路。

完整可运行代码

#include <iostream>
using namespace std;
 
const int N = 2010;
int n;
int arr[N];
 
int bfs()
{
    int left = 1, right = 1;   // 当前层（当前跳跃次数）可达的位置区间
    int ret = 0;               // 跳跃次数
    while(left <= right)       // 还有可达点就继续扩展
    {
        ret++;
        int r = right;         // 本层能到达的最远点先假设等于本层右端
        for(int i = left; i <= right; i++)  // 铺开本层所有点
        {
            r = max(r, arr[i] + i);         // 从 i 最远能到 arr[i]+i
            if(r >= n) return ret;          // 第一次越过桥尾，返回步数
        }
        left = right + 1;     // 下一层从左边界后开始
        right = r;
    }
    return -1;                // 所有层都扩不到，无法到达
}
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    cout << bfs() << endl;
    return 0;
}

运行结果

真机输出（三组：可达 4 步 / 一步到 / 不可达）：

=== 输入1：
5
1 1 1 1 0
输出1：
4

=== 输入2：
4
3 0 0 0
输出2：
1

=== 输入3：
4
1 1 0 0
输出3：
-1

核对：

输入1：每步只能前进 1 格，从 1 到 5 需要 4 跳 → 输出 4；✓
输入2：在桥头 1 能跳 3 格，1 + 3 = 4 >= n=4，1 次到达 → 输出 1；✓
输入3：arr={1,1,0,0}，从 1 → 2 → 3，到 3 时 arr[3]=0 往前不了，卡死 → -1；✓

详解答案与坑点

答案：三组依次 4、1、-1。
复杂度：O(n)，每个位置至多扫一次；空间 O(1)。
坑一（越界判定偏置）：r >= n 是"到达或越过桥尾"，终点含 n 本身。 只要最远点 ≥ n 就算到（落到桥尾位置 n 或跳过都算）。判断成 > n 会漏掉"正好落在桥尾"那一步。
坑二：left = right + 1 的推进。 一层扫完，下一层要从 right + 1 开始到 r，而不是从 left 重新开始（那些位置已扫过）。写成 left = right + 1 才对。
坑三：循环收敛。 当 right 不再增大（本层最远点没超过 right 甚至倒退）时，left = right+1 > right，while(left <= right) 条件破坏，退出返回 -1。只要推进式子对，收敛自然成立。
坑四：数组下标从 1 开始读。 桥头是 1，bfs 也从 1 起算，别误用 0-based 起点导致整体偏一位。
题型归一：这就是"跳跃游戏 / 最小跳跃次数"。BFS 层扩展或贪心（每次记录最远可达）两种写法皆可，收藏一个即可。贪心版其实是 BFS 的原地优化。

本周考点一图流

最后按题型把本周 18 道题归纳成一张表，考前扫一眼即可对上套路：

题型	题目	核心套路	复杂度	必扣易错点
字符串查找	旋转字符串	倍增 `A+A` + `find(B)`	O(n)	先判长度、注意 npos
哈希	神奇字母（二）	桶计数 + 严格大于保先到	O(n)	并列取先到还是其它要看题
枚举+环形	游游的字母串	枚举目标字符 + 环距取小	O(26n)	别忘了绕环那半边
滑窗+前缀	小红的子串	find(r) - find(l-1) + 双指针	O(n)	种类≠长度、long long
链表+堆	合并k链表	小根堆多路归并	O(N log k)	比较器方向反了
拓扑排序	体育课测验（二）	Kahn BFS 建图判环	O(n+m)	约束方向对齐
记忆化搜索	滑雪	DFS + dp 备忘	O(nm)	严格小于、四向越界
模拟+规律	dd爱旋转	操作奇偶压缩	O(n²)	旋转等价拆法以真机/题约为准
模拟+方向	棋子翻转	dx/dy 邻居 + 越界 + ^=1	O(ops)	不翻自身
模拟+贪心	最大差值	扫的同时记前缀最小值	O(n)	后减前、别加绝对值
线性递推	天使果冻	前缀最大/次大三分支	O(n+q)	次大分支别漏
LIS	合唱队形	正反两遍 LIS + 山峰减 1	O(n²)	严格升降、减1
打家劫舍变形	宵暗的妖怪	模板转移 dp[i-3]	O(n)	语义用真机小样例校准
完全背包	最少完全平方数	正序容量 + 求最少件	O(n√n)	内层正序(完全)
完全背包	兑换零钱	正序 + 不可达判-1	O(n·aim)	正序、数组大小
01背包+同余	小红取数	余数维度 + (j-w%k+k)%k	O(nk)	不能空间优化、取模防负
哈夫曼	字符编码	每次取两小合并累加 WPL	O(n)	累加合并代价，别真拼串
BFS	过桥	层区间扩展跳跃	O(n)	r>=n 判终点

到此，笔试强训第 07 周的 18 道题全部拆解完毕。本周的主线非常清晰：模拟题在逼你"定义清楚每次操作到底动了什么"（旋转、翻转尤其要防等价拆法的坑）；字符串题在教你"用查找/哈希/滑窗/环距吃掉暴力"；背包题在锤炼你"物品能不能重复用——定序 or 倒序"的分水岭；图论/记忆化/BFS 则共同指向同一件事：把"有依赖、有递推、有层数"的问题，用"剥洋葱"式的思维喂给 BFS 或 DP。

我特别想再叮嘱三点掏心窝的话：

别被怪名字唬住。 天使果冻、宵暗的妖怪、小红取数……剥掉名字全是老朋友（前缀最值、打家劫舍、01 背包+同余）。判断一道题在考什么，先看输入输出、约束形态，再看有没有"容量/和/余数/层数"这类关键词。
转移代码背得再熟，也请务必造一两个最小样例真机跑一遍校准。 本周"宵暗的妖怪""dd爱旋转"都暴露了同一个隐患：一段你以为懂的转移，跟真实输出可能有微妙的语义偏差。 笔试你不可能每道都机器验证，但练习阶段一定要养成"小样例手推 + 真机输出对照"的习惯，这才是把"背模板"升级成"真正懂"的唯一路径。
到 07 周，long long、越界保护、^=1、(x%k+k)%k 这些"防坑肌肉记忆"应该已经长在你的手指上。 如果还时不时在这些地方失分，说明前几周的基础动作没压实，建议回头整理错题本，比闷头多刷更有用。

代码全部在本机 g++ 15.2.0 下 -O2 编译运行验证过，运行结果和易错点都逐条给你对上了号。请你自己动手，把这 18 题亲手 Build & Run 一遍，让"AC"成为你的习惯响应。下周就是我们笔试强训的一大关——更高阶的批量与混合专题，到时见招拆招，先把本周这六块板斧练扎实，路是一步一步走出来的。