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

这是「笔试强训」系列的第 01 周。这一周我们从最基础的"数学 + 模拟"一路摸到"高精度运算"，一共 18 道题，横跨 6 天，每天三道。题目本身都不难，但恰恰是我们最容易粗心翻车的地方——位运算取数、哈希去重、栈消除、浮点取整、线性 DP、滑动窗口、贪心、图论搜索、约瑟夫环、大数运算……题型覆盖面很广，正好用来验收一下你"基础是否真的扎实"。

我对文章的处理方式说明一下：每一道编程题我都会给"题干 → 思路 → 完整可运行的 C++ 代码（逐行注释）→ 运行结果（我用本机 g++ 15.2.0，-std=c++17 实测）→ 详解"，凡是适合的题目我会顺手给一题多解和复杂度分析；同时，每个知识点后面我都放了几道经典的"选择题精讲"——这些题是我针对本周高频易错点出的自编经典题，每题都逐项讲对错并给出最终答案，帮你把坑提前踩一遍。

小提醒：文中所有代码都是能直接复制进 OJ 或本地编译运行的完整程序；带 Solution 类的题目是牛客/力扣的原板子，我为方便演示补了 main 包装。

Day01：数字统计（数学+模拟）・两个数组的交集（哈希）・点击消除（栈）

第一天的三道题，恰好对应三种最基础的套路：模拟取位、哈希标记、栈匹配。它们难度不高，但"坑"一个比一个隐蔽。

第 1 题：数字统计（BC153 / NOIP2010）

题干给定两个整数 L 和 R（1 <= L <= R <= 100000），请计算在区间 [L, R] 中的所有整数里，数字 2 一共出现了多少次。例如区间 [2, 22] 中，数字 2 在 2、12、20、21、22 里出现，其中 22 含两个 2，所以一共出现 6 次。

思路这是非常典型的"模拟 + 逐位取数"题。对区间内每一个整数 i，我们把它拆成若干位，看每一位是不是 2。拆位的标准动作是：对 10 取余拿末位，再整除 10 把末位干掉，直到数字变成 0。循环提取末位，然后干掉末位，就是这套题的灵魂。

注意一个细节：while(tmp) 进入条件是"tmp 不为 0"，也就是说当 i = 0 的时候循环一次都不会进——这正好符合题意，因为 0 这一位根本不是 2。不过本题 L >= 1，一般不会遇到 0，但你要明白这个边界。

代码（C++，可用 g++ 编译）

#include <iostream>
using namespace std;
int main()
{
    int l, r;
    cin >> l >> r;                 // 输入区间 [l, r]
    int ret = 0;                   // 统计数字 2 出现的总次数
    for(int i = l; i <= r; i++)    // 枚举区间内每一个整数
    {
        int tmp = i;
        while(tmp)                 // 逐位提取
        {
            if(tmp % 10 == 2) ret++;   // 末位是 2 就计数
            tmp /= 10;                 // 干掉末位
        }
    }
    cout << ret << endl;
    return 0;
}

运行结果（输入 2 22）

详解拿 l = 2, r = 22 走一遍：2 -> 1 次；3~9、11、13~19、23 的每一位都不是 2；12 -> 1 次；20 -> 1 次；21 -> 1 次；22 -> 两 + 两个 2 共 2 次。加起来 6 次，与程序输出一致。

该实现的时间复杂度是 O((R - L) * logR)（每个数大约有 O(log R) 位），空间复杂度 O(1)。R 最大 1e5，位大约 5 位，肉眼可见轻轻松松。

讲师加餐・选择题精讲

1.（易错） 若将内层循环写成 while(tmp) { if(tmp % 10 == 2) ret++; tmp /= 10; }，那么当 i 的某一位为 2 但该位不是个位（例如数字 20）时，下列说法正确的是？ A. 一定会统计到十位的那个 2，因为 tmp 会进入第二次循环 B. 一定统计不到十位的 2 C. 只有数字本身等于 2 时才会统计 D. 程序会死循环

逐项分析：B 错——20 第一次 tmp % 10 == 0，不匹配；tmp /= 10 得 2；第二次循环 tmp % 10 == 2，命中。C 错，理由同上。D 错，tmp 每次除以 10 迟早变 0。所以 A 正确。

2.（边界） 若把外层循环写成 for(int i = l; i < r; i++)，在输入 2 22 时会漏掉哪个数字？ A. 21　B. 22　C. 20　D. 一个不丢

逐项分析：i < r 会让 i 最大取到 21，漏掉右端点 22。A、C 都会统计到，D 错。所以 B 正确。区间题"含不含端点"是最常见的丢分点。

第 2 题：两个数组的交集（NC313）

题干给定两个整数数组 nums1 和 nums2，返回它们的交集输出，结果中的每个元素一定是唯一的。要求不考虑输出结果的顺序。例如 nums1 = [4,9,5]、nums2 = [9,4,9,8,4] 的交集是 [9,4]。

思路两个思路任选其一：

思路一（哈希）：把其中一个数组丢进哈希表，遍历另一个数组时到哈希表里查。为避免重复输出，第一次命中后把标记清掉。
思路二（排序 + 双指针）：不管哪一个，先 sort 两个数组去独特的重复，然后用两个指针并行比较。

本题数据范围小（值域约在 [0, 1010)），源码直接用一个 bool 数组当"哈希表"用，实话实说是最省事的做法。但你要牢牢记住它的适用前提：元素是非负、且最大 < 数组容量。一旦值域跑到 1e9 这种大数，就必须换成 unordered_set / unordered_map，否则数组下标直接爆栈越界。

代码（C++，哈希版）

#include <iostream>
#include <vector>
using namespace std;
class Solution
{
    bool hash[1010] = { 0 };         // 值域 [0,1010)，用数组模拟哈希标记
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
        vector<int> ret;
        for(auto x : nums1) hash[x] = true;          // 标记 nums1 出现过的元素
        for(auto x : nums2)                          // 遍历 nums2 去查哈希
        {
            if(hash[x])          // 第一次在结果里遇到就收集
            {
                ret.push_back(x);
                hash[x] = false; // 置回 false，避免重复收集
            }
        }
        return ret;
    }
};
 
int main()   // 本地演示用的 main，OJ 上交代码时不需要
{
    Solution s;
    vector<int> nums1 = {4, 9, 5};
    vector<int> nums2 = {9, 4, 9, 8, 4};
    vector<int> ret = s.intersection(nums1, nums2);
    for(auto x : ret) cout << x << " ";
    cout << endl;
    return 0;
}

运行结果

9 4

详解：先标记 nums1 里的 4、9、5；再遍历 nums2 = 9,4,9,8,4。遇到 9：哈希为 true，入结果并置 false；遇到 4：入结果并置 false；再遇 9：已 false 跳过；8 未出现跳过；再遇 4：已 false 跳过。最终得到 [9,4]。

hash[x] = false 这一步是去重的关键——少了它，nums2 里出现多次的元素会重复入结果。

讲师加餐・选择题精讲

3. 关于上面"用 bool 数组模拟哈希"的写法，下列说法错误的是？ A. 若 nums1 中出现负数，程序会数组越界 B. 若 nums1 中某元素大于等于 1010，程序会数组越界 C. 该方法空间复杂度为 O(1)（借助固定大小数组） D. 该写法可以处理任意大小的任意整数

逐项分析：A、B 都会越界，是隐患，说法正确。C 空间依赖的是值域大小，值域固定 1010 时是 O(1)，表述没问题。D 错——它对值域有限制，别说任意大小，值域一大就崩。所以 D 是"错误"的说法，答案选 D（选错误的）。

第 3 题：点击消除（AB5）

题干给定一个只由小写字母组成的字符串 S，你可以不断进行"消除"操作：如果相连的两个字符相同，就删掉它们。重复这一过程直到不能再消除为止。请输出最终剩下的字符串；如果全部消除干净，输出 0。

思路用一个栈来模拟消除过程。扫描字符串，对每个字符：

如果栈非空，且栈顶字符和当前字符相等，说明这两个相邻字符相同，可以成对消除——弹出栈顶；
否则，当前字符入栈。

扫描结束后，栈里剩下的就是最终结果。这个"栈 + 消消乐"模型在括号匹配、相邻去重里反复出现，非常经典。这里我用 string 直接当栈用（back() 看栈顶、pop_back() 出栈、+= 入栈），省去std::stack的写法，本质完全一致。

代码（C++）

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s, st;           // st 当栈用，这里直接用 string 模拟栈
    cin >> s;
    for(auto ch : s)
    {
        // 栈非空且栈顶和当前字符相同 => 相邻相同，消除
        if(st.size() && st.back() == ch) st.pop_back();
        else st += ch;      // 否则入栈
    }
    cout << (st.size() == 0 ? "0" : st) << endl;   // 空栈输出 0
    return 0;
}

运行结果（输入 abba）

详解：以 abba 为例——a 入栈 [a]；b 入栈 [a,b]；第三个 b 和栈顶 b 相同，弹出，栈变 [a]；第四个 a 和栈顶 a 相同，弹出，栈空。最后栈空，输出 0。

再试 aab：a 入栈 [a]；第二个 a 与栈顶相同弹出，栈空；b 入栈。最终剩 b，输出 b。

注意输出空串时要打印 0 这个约定，是本题最容易漏掉的点。时间复杂度 O(n)，空间 O(n)。

一题多解：如果你不想用栈，这道题的"字符串原地双指针"其实是个好替代——维护一个 slow 指针当"逻辑栈顶"，fast 指针扫描原串，逻辑一模一样，只是空间省到 O(1)。核心思想互通，栈版本更直观，面试时讲栈版本足够了。

Day02：牛牛的快递（模拟）・最小花费爬楼梯（线性 DP）・数组中两个字符串的最小距离（模拟+贪心）

第二天的重头戏是线性 DP和贪心的初见。尤其 dp 那题，几乎是一切"爬楼梯类"题目的原型。

第 1 题：牛牛的快递（BC64）

题干每件快递都有一个重量 a（浮点数）和一个是否加急的标志 b（y 表示加急，n 表示不加急）。计费规则如下：首重 1kg 以内（含 1kg）收费 20 元；重量超过 1kg 的部分，每 1kg 加收 1 元，不足 1kg 按 1kg 计算（向上取整）；加急额外加收 5 元。请你计算总费用。

思路纯模拟，分情况处理，主要是"续重部分向上取整"。这里就会用到两个库函数——ceil（天花板，向上取整）和 floor（地板，向下取整）。超出 1kg 的部分 a - 1 需要"按整千克计费"，也就是 ceil(a - 1)。注意要 include <cmath>。

代码（C++）

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    double a;   // 重量
    char b;     // 是否加急 y/n
    cin >> a >> b;
    int ret = 0;
    if(a <= 1)          // 首重 1kg 以内（含 1kg）
    {
        ret += 20;
    }
    else                // 超过 1kg
    {
        ret += 20;      // 首重费 20 元
        a -= 1;         // 去掉首重的 1kg
        ret += ceil(a); // 续重每整 kg 加 1 元，向上取整
    }
    if(b == 'y') ret += 5;  // 加急额外 +5
    cout << ret << endl;
    return 0;
}

运行结果（输入 3 y）

详解：重量 3kg，先付首重 20 元；续重 3 - 1 = 2kg，ceil(2) = 2，加 2 元；加急加 5 元。20 + 2 + 5 = 27。

讲师加餐・选择题精讲

4.（库函数） 关于 ceil 和 floor，下列说法正确的是？ A. ceil(3.0) == 3　B. floor(-1.2) == -1　C. ceil(-1.2) == -1　D. (int)ceil(2.8) == 2

逐项分析：A 正确，ceil(3.0)=3（本来就整数不取整）。B 错，floor 向下取整，floor(-1.2) = -2（往更小的方向取整）。C 正确，ceil(-1.2) 向上取整到不大于它还是要往大的方向，即 -1.0。D 错，(int)ceil(2.8) 先取整得 3 再转 int 得 3。所以 C 正确、A 也正确，选 A、C。

5. 上面用 cin >> a >> b 同一行读入 3 y，如果题目把 y 改成一行一个输入，下面哪个读法可以正确读到单个字符 y？ A. cin >> b　B. cin.get(b)　C. getline(cin, b)　D. scanf("%c", &b)

逐项分析：B 会把上一次输入后的换行符 \n 读给 b，容易出错（除非先吃掉多余空白）。C 的对象是字符串不是 char。A 用 >> 能自动跳过空白，正确。D 用 %c 不会跳过空白，若前面有换行会读进 \n，需要手动处理——单论"能否正确读到 y"在本题前一行记为数字的情况下会读到换行，不安全。所以选 A。

第 2 题：最小花费爬楼梯（DP4）

题干给定一个长度为 n 的正整数数组 cost，cost[i] 表示跨上第 i 级台阶需要花费的体力值。你初始站在第 0 级（可以自由理解为从平地/第0级出发），每次可以选择向上跨越 1 级或者 2 级。请问从第 0 级出发，爬到最高的第 n 级台阶，最少需要花费多少体力？

（补充理解：很多这类题的隐藏约定是"从第 0 层出发时，到达第 0 层和第 1 层的花费都为 0"，因为你是站在起点而不是"跨"上去的，只有"跨上某层"才计费。）

思路这是一道线性 DP，属于"爬楼梯"家族的最简原型。设 dp[i] 为"爬到第 i 级的最小花费"。转移方程一眼写出：

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

它说的是：要到达第 i 级，要么从第 i-1 级跨 1 级上来（花费 cost[i-1]），要么从第 i-2 级跨 2 级上来（花费 cost[i-2]），取两者较小。初始 dp[0] = dp[1] = 0。

代码（C++）

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int cost[N];
int dp[N];                    // dp[i]: 爬到第 i 级的最小花费
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> cost[i];
    // dp[0] = dp[1] = 0（站在起点，跨上第 0/1 级不计费，或已初始化全局数组为 0）
    for(int i = 2; i <= n; i++)
    {
        // 从 i-1 跨 1 级上来(花费 cost[i-1]) 或 从 i-2 跨 2 级上来(花费 cost[i-2])
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    cout << dp[n] << endl;
    return 0;
}

运行结果（输入 3 然后数组 1 100 1）

详解：n = 3, cost = [1, 100, 1]。

dp[0] = 0、dp[1] = 0；
dp[2] = min(dp[1] + cost[1], dp[0] + cost[0]) = min(0 + 100, 0 + 1) = 1；
dp[3] = min(dp[2] + cost[2], dp[1] + cost[1]) = min(1 + 1, 0 + 100) = 2。

所以最少花费 2，程序输出 2。路径是：0 → 2（花 cost[0]=1）→ 3（花 cost[2]=1）。

时间复杂度 O(n)，空间 O(n)。这题还能滚动位数把空间压到 O(1)，因为每个 dp[i] 只依赖前两个。这是"线性 DP"最常见的一种：dp[i] 由 dp[i-1]、dp[i-2] 之类的前驱推出，转移只做一次 min/max。

一题多解：空间优化版只需要两个变量 a = 0, b = 0，每次算 c = min(b + cost[i-1], a + cost[i-2]) 再滚动更新。逻辑完全等价，面试时顺手体现一下复杂度意识很加分。

讲师加餐・选择题精讲

6.（DP 出口） 计算 dp[2] 时用到了 dp[0] 和 dp[1]，如果题目"从第 2 级才允许起步（即只能从第 2 级之后开始跳）"，初始化区别正确的是？ A. 仍令 dp[0]=dp[1]=0 ❌❌ 错误 B. 应把 dp[0]、dp[1] 设为一个很大的数，避免从"不允许的位置"转移 C. 让 dp[2] 直接等于 cost[0] + cost[1] D. 不需要任何初始化

逐项分析：思路在于"不合法状态要设成不可达"（无穷大）。若起点只能是第 1 级之类，就应把不可达的 dp[0] 弄成 INF 防止被选进转移。B 符合这一通用手法。A、D 都不处理边界，C 是在硬编码路径，不通用。故 B 正确。这一问主要是提醒：DP 的"非法状态"往往要用 INF 标志，而不是盲信 0。

第 3 题：数组中两个字符串的最小距离（模拟+贪心）

题干给定一个长度为 n 的字符串数组（一维），以及两个字符串 s1 和 s2。请找出这数组中任意一个位置是 s1、另一个位置是 s2 的最小的下标距离（即 |下标差| 的最小值）。如果数组中不存在 s1 或 s2（无法凑成一对），输出 -1。

思路不用枚举所有 (i, j) 对（那会 O(n²) 超时）。用小贪心，本质也是小 DP：

用 prev1 记录 i 位置之前最近一次出现 s1 的下标；
用 prev2 记录 i 位置之前最近一次出现 s2 的下标；

从左往右扫，当扫到 s1 时，它和"最近的那个 s2"（prev2）的距离必然是对该 s1 来讲最小的，更新答案并刷新 prev1；扫到 s2 同理。因为"最近的那个"一定比 "更早的那个" 距离更小，所以每次只用最近的前驱就够了——这就是贪心的正确性所在。

代码（C++）

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n;
    string s1, s2;
    string s;
    cin >> n;
    cin >> s1 >> s2;                    // 要统计距离的两个字符串
    int prev1 = -1, prev2 = -1, ret = 0x3f3f3f3f;   // 初始距离记成"无穷"
    for(int i = 0; i < n; i++)          // 逐个读入数组元素
    {
        cin >> s;
        if(s == s1)                     // 遇到 s1，去前面找最近一次的 s2
        {
            if(prev2 != -1) ret = min(ret, i - prev2);
            prev1 = i;                  // 更新最近 s1 位置
        }
        else if(s == s2)                // 遇到 s2，去前面找最近一次的 s1
        {
            if(prev1 != -1) ret = min(ret, i - prev1);
            prev2 = i;                  // 更新最近 s2 位置
        }
    }
    if(ret == 0x3f3f3f3f) cout << -1 << endl;   // 没凑出任何一对
    else cout << ret << endl;
    return 0;
}

运行结果（输入 4、a b，然后数组元素 a c b c）

详解：数组为 [a, c, b, c]，s1=a、s2=b。

i=0 扫到 a：prev2 还是 -1，不更新，prev1=0；
i=1 扫到 c：无关；
i=2 扫到 b：prev1=0，得 ret = 2-0 = 2，prev2=2；
i=3 扫到 c：无关。

最小距离 2，程序输出 2。

用 0x3f3f3f3f 当"无穷"初值是个常用技巧（它是一个很大的数，不容易被正常距离"撞上"），最后用它判断"是否存在过一对"就很自然。时间复杂度 O(n)，空间 O(1)。

讲师加餐・选择题精讲

7. 用 prev1、prev2 做贪心时，下列说法哪一个是正确的？ A. 只有 s1 出现在 s2 之后才能算出距离 B. 由于每次都取"最近的前驱"，所以不漏最优解 C. 需要先把数组排序才能用双指针 D. 该算法复杂度是 O(n²)（需两两比较）

逐项分析：A 错，s2 在前、s1 在后同样能算（反过来扫到 s1 用 prev2）。C 错，数组顺序是有意义的，不能排。D 错，是 O(n)。B 正是贪心正确性的核心表述——任意一对 (i, j)，用它俩之间"距它们最近"的那对前驱去逼近，距离只会更小，不会漏更优解。故 B 正确。

Day03：简写单词（模拟）・dd爱框框（滑动窗口）・除2!（贪心+堆）

第三天开始上"算法"了——滑动窗口和贪心+堆都是高频考点。

第 1 题：简写单词（BC149）

题干给出一段英文句子（可能由若干个单词构成，单词之间以空格分隔），请你把每个单词的首字母提取出来，如果首字母是小写，就把它转成大写后输出；如果首字母本来就大写（或非字母），原样输出。把这些首字母按顺序拼接输出即可。

思路这是一道处理输入的模拟题。核心技巧是：用 while(cin >> s) 这种"流式读词"会自动跳过所有空白（空格、换行），所以我们根本不用手动 split，每次读到的是一个完整单词。小写转大写就是 ch - 32，因为大写字母 ASCII 比对应小写字母小 32。也可以直接用库函数 toupper，思路等价。

代码（C++）

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    while(cin >> s)             // 逐个读单词，自动跳过空格
    {
        if(s[0] >= 'a' && s[0] <= 'z') cout << (char)(s[0] - 32);  // 小写转大写
        else cout << s[0];      // 本来就是大写/数字，原样输出
    }
    return 0;
}

运行结果（输入 hello world abc）

HWA

详解：while(cin >> s) 会依次读到 hello、world、abc，分别取首字母 h w a，转大写后输出 H W A，连起来就是 HWA。

注意：我们没有输出任何换行和空格，只连续输出首字母大写，符合题意——输出结果要的是"拼接后的字符串"。

讲师加餐・选择题精讲

8. 若要"把一行字符串按空格拆成单词"，下面哪种写法不能达到目的？ A. while(cin >> s) 读取 B. getline(cin, line) 后按空格手工 split C. cin.getline 每次只读一个词 D. 用 istringstream 配合 >>

逐项分析：A 正确（流式读词）。B 正确（整行 readline 再 split）。D 正确。C 错——cin 提供的 >> 能自动跳过空白，但 getline 是按行读、不会自动按空格把"一行"拆成多个词。要注意区分"按行读取"与"按空白分词"。所以选 C。

第 2 题：dd爱框框（滑动窗口）

题干给定一个长度为 n 的正整数数组和阈值 x，找出最短的一段连续子区间（窗口），使得区间内所有数的和 >= x。如果存在多个长度相同的最短窗口，输出最靠左的那个窗口的左右端点下标（下标从 1 开始）。题目保证有解。

思路这是**同向双指针（滑动窗口）**的经典套路，也叫"双指针找最短满足条件的连续子数组"。由于数组元素都是正整数，窗口右端 right 每扩展一步，和 sum 单调不减；满足 sum >= x 时我们就可以尝试收缩左端 left 来找更短窗口。四个标准动作：

进窗口：sum += arr[right]；
更新结果：当前 sum >= x 时，如果 right - left + 1 < retLen 就更新最省窗口；
出窗口：sum -= arr[left++]; 收缩左端，继续判断能不能更短；
右指针右移：right++。

代码（C++）

#include <iostream>
using namespace std;
const int N = 1e7 + 10;   // 数组开大，1 下标存储
int arr[N];
int n, x;
int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    int left = 1, right = 1, sum = 0;      // 窗口 [left, right]
    int retLen = N, retLeft = -1, retRight = -1;   // 最短窗口初始为"无穷长"
 
    while(right <= n)
    {
        sum += arr[right];                 // 进窗口
        while(sum >= x)                    // 满足条件就尝试收缩
        {
            // 更新结果：更短才更新（题目同样长取最左，所以只用 < 不用 <=）
            if(right - left + 1 < retLen)
            {
                retLeft = left;
                retRight = right;
                retLen = right - left + 1;
            }
            sum -= arr[left++];            // 出窗口，收缩左端
        }
        right++;                           // 右指针前进
    }
    cout << retLeft << " " << retRight << endl;
    return 0;
}

运行结果（输入 5 7，数组 1 3 5 7 9）

4 4

详解：x = 7，找和 >=7 的最短窗口。逐个验证发现：单元素窗口 [4,4]（arr[4]=7）之和正好 7，长度 1，已经是理论上最短了——所以答案是 4 4。程序输出 4 4。

关键点：这里 left 从 1 开始（数组 1 下标），比某些网上版本"left 从 0 开始"更贴近 OJ 下标。retLen 初始设为极大值 N，保证第一次满足条件时必然能更新。

复杂度：每个元素最多进窗一次、出窗一次，时间复杂度 O(n)，空间 O(n)（数组本身）。

讲师加餐・选择题精讲

9. 关于滑动窗口，下列说法正确的是？ A. 只有数组元素全为正数时，right 单调右移才不会漏解 B. 出现负数时，双指针法也可能仍正确，但"缩窗条件"要更小心 C. 窗口长度一定的基础上，right 越界即循环结束 D. 以上都对

逐项分析：A 表述有陷阱——数组全为正数时 sum 单调增、收缩逻辑才顺理成章；B 对：出现负数时和可能不单调，双指针要另行处理（可能要前缀和/同向双指针失效），“更小心”的说法成立。C 正确：right 超过 n 后没有新元素可进，循环结束。三者都成立，所以 D 正确。这一题提醒你：单调性是滑动窗口成立的基石。

第 3 题：除2!（贪心+堆）

题干给定 n 个正整数和最多 k 次操作。每次操作你可以选择一个偶数，把它除以 2。请你通过至多 k 次操作，让这 n 个数的总和最小，输出最小和。（除出来的数如果还是偶数，可以继续被后续操作选到。）

思路贪心：每次选当前最大、且是偶数的那个数减半，收益才最大（因为减半减少的量 = x - x/2 = x/2，x 越大省得越多）。用一个大根堆（priority_queue）维护"所有偶数"，每次取堆顶减半并更新总和，若减半后仍是偶数就放回堆里，重复直到操作次数用完或堆空。

这是"贪心 + 优先队列"的标准组合，核心是每次做出局部最优（削减最大）以保证全局最优。注意开销要开 long long，因为数据可能很大、总和很容易爆 int。

代码（C++）

#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
int main()
{
    priority_queue<LL> heap;        // 大根堆，只放偶数
    LL n, k, x, sum = 0;
    cin >> n >> k;
    while(n--)
    {
        cin >> x;
        sum += x;
        if(x % 2 == 0) heap.push(x);   // 只有偶数才有"减半"潜力
    }
    while(heap.size() && k--)          // 最多操作 k 次，每次优先减最大偶数
    {
        LL t = heap.top() / 2;         // 减半后的值 = 本次能减少的量
        heap.pop();
        sum -= t;                      // 总和减少 t
        if(t % 2 == 0) heap.push(t);   // 减半后仍是偶数，还能继续
    }
    cout << sum << endl;
    return 0;
}

运行结果（输入 2 2，数组 5 10）

详解：n=2, k=2，数组 5 10，初始和 15。堆里有 10（5 是奇数不进堆）。

第 1 次：取 10，减半为 5，和变为 15 - 5 = 10；5 是奇数，不再入堆。
第 2 次：堆已空，结束。

最终和 10，程序输出 10。

sum -= t 这里有个细节：减半后值 = t，那么减少的量恰好等于 t（因为 x - x/2 = x/2）。所以 sum -= 减半后的值 就是把"被削减掉的那部分"从总和里扣掉。时间复杂度 O((n + k) log n)。

讲师加餐・选择题精讲

10. 关于 priority_queue<LL> heap 默认为"大根堆"，下列说法正确的是？ A. heap.top() 返回最小的元素 B. heap.top() 返回最大的元素 C. heap.push、heap.pop 复杂度为 O(log n) D. 想让 top 返回最小值需要传入一个"greater 比较器"

逐项分析：A 错，默认大根堆 top 是最大。B 对。C 对（入堆/出堆 O(log n)）。D 对（priority_queue<LL, vector<LL>, greater<LL>> 才是小根堆）。所以选 B、C、D。

Day04：Fibonacci数列（Fib 数列）・单词搜索（搜索/DFS）・杨辉三角（动态规划）

第四天练"数"——斐波那契、深搜回溯、二维 DP。这三个都是必须吃透的。

第 1 题：Fibonacci 数列（WY22）

题干定义 Fibonacci 数列为：F(0)=0, F(1)=1, F(2)=1, F(3)=2, ...（即每个数等于前两个数之和）。给定一个正整数 n，你每次操作可以让 n 增大 1 或减小 1。请问至少需要多少次操作，能让 n 变成一个 Fibonacci 数列中的数？

思路在递推斐波那契的过程中，判断 n 落到哪两个相邻 Fib 数之间：设左边最近的 Fib 是 b，右边最近的 Fib 是 c（b <= n <= c），那么"最少操作步数"等于 min(c - n, n - b)——因为在这个区间内，往左走到 b、往右走到 c，取更近的那个即可。

代码（C++）

#include <iostream>
#include <cmath>
using namespace std;
int n;
int main()
{
    cin >> n;
    int a = 0, b = 1, c = 1;   // fib 序列前三个：0, 1, 1
    while(n > c)               // 找到第一个不小于 n 的 fib 数 c
    {
        a = b;
        b = c;
        c = a + b;             // 相邻三项滚动前进
    }
    // 此时 b 是 n 左边最近的 fib，c 是右边最近的 fib
    cout << min(c - n, n - b) << endl;
    return 0;
}

运行结果（输入 15）

详解：Fib 序列 0,1,1,2,3,5,8,13,21,...。n=15 在 13 和 21 之间。min(21-15, 15-13) = min(6, 2) = 2。也即把 15 减到 13 需要 2 步，程序输出 2。

注意边界：如果 n 本身就是 Fib 数（比如 n=8），循环会停在 c=8（因为 n > c 为假），b=5，min(8-8, 8-5)=0，正确输出 0。这是对"恰好命中"边界的完整覆盖。

时间复杂度 O(log n)，因为 Fib 增长是指数级的，n 越大需要的项越少。

讲师加餐・选择题精讲

11.（Fib 内联） 用 a=0, b=1, c=1 滚动 Fib 时，下列说法正确的是？ A. c 始终等于 a+b B. 循环结束后 c 一定大于 n，且 b 一定小于等于 n C. 当 n 是某个 Fib 数时，循环一次都不会进入 D. 循环结束后 b 可能是 0（当 n=0 时）

逐项分析：A 对，初始 c=1=a?——仔细看：a=0,b=1,c=1，c=a+b 成立；每次 c=a+b 更新，成立。B 对：n <= c 才停止，所以 c >= n；且进入循环的条件保证 b < n（因为 b 是上一个 c），故 b <= n。C 错：如果 n 是 Fib 数，比如 n=2，n > c(=1) 为真，还是会进入若干次循环。D 对：n=0 时 n > c(=1) 为假，循环不进入，b=1——等等，b=1 不是 0，D 说 b=0 不对。仔细：n=0 时不停，b=1。所以 D 错。正确答案 A、B。

第 2 题：单词搜索（NC242）

题干给定一个 m x n 的二维字符网格 board 和一个单词 word。请判断该单词是否存在于网格中——构成单词的每个字符必须在网格中连续（相邻的上下左右四个方向），并且同一单元格里的字母在组成单词时不能重复用一次（也就是不能回踩自己走过的格）。

思路这题是DFS + 回溯的经典应用。遍历网格，凡是和 word[0] 相同的格子都可能作为起点，从它出发做深度优先搜索；用 vis 数组记录当前搜索路径上占过的格子，防止回踩；搜索失败就要"回溯"把 vis[i][j] 复位，好让其它路径也能用这个格子。

代码（C++）

#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution
{
    int m, n;
    bool vis[101][101] = { 0 };
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    bool exist(vector<string>& board, string word)
    {
        m = board.size(); n = board[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(board[i][j] == word[0])          // 可能的起点
                    if(dfs(board, i, j, word, 0)) return true;
        return false;
    }
    bool dfs(vector<string>& board, int i, int j, string& word, int pos)
    {
        if(pos == (int)word.size() - 1) return true;  // 已匹配完最后一个字符
        vis[i][j] = true;                             // 标记占位，防止回踩
        for(int k = 0; k < 4; k++)                    // 上下左右四个方向扩展
        {
            int a = i + dx[k], b = j + dy[k];
            if(a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && board[a][b] == word[pos + 1])
            {
                if(dfs(board, a, b, word, pos + 1)) return true;  // 找到即返回
            }
        }
        vis[i][j] = false;                            // 回溯：解除占位，供其它路径用
        return false;
    }
};
 
int main()   // 演示包装
{
    Solution s;
    vector<string> board = {"ABCE", "SFCS", "ADEE"};
    string word = "ABCCED";
    cout << (s.exist(board, word) ? "true" : "false") << endl;
    return 0;
}

运行结果

true

详解：board 为：

A B C E
S F C S
A D E E

要找 ABCCED。起点在 (0,0)='A'，路径 A->B->C->(2)C->(2)E->D 步行走完 ABCCED，DFS 找到即返回 true。加括号的 C 是 (1,2)，E 是 (2,2)，D 是 (2,1)。DFS 能沿"上/下/左/右"绕过 (1,1)='F' 这个格子完成匹配，所以返回 true。

if(pos == word.size()-1) return true; 是个小优化：最后一个字符在调用 dfs 前已经匹配好了，所以当 pos 到了倒数第二位，能进入扩展说明下一位也匹配，可直接返回——不过更保守的做法是在进入 dfs 时先判断当期字符是否匹配。这里逻辑自洽即可。

一题多解：如果不需要回溯（比如允许重复经过格子），可以退化成"朴素的多起点多步扩散"，但本题"同一格不能用两次"强制要求回溯，所以必须配 vis + 复位。这是笔试里"DFS 最核心的三件套"：方向数组、vis 标记、回溯复位。

第 3 题：杨辉三角（BC140）

题干输入正整数 n，输出杨辉三角的前 n 行。杨辉三角的规律是：每行的第一个和最后一个数都是 1，中间每个数等于它"正上方"和"左上方"两个数之和。本题要求每个数按 %5d 的宽度输出（右对齐、宽度为 5）。

思路这是一个非常朴素的二维 DP 模型，也是"二维数组递推"的入门。用 dp[i][j] 表示第 i 行第 j 列的数，递推式就是定义本身：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

（全局数组初始全 0，所以 j=1（最左）时 dp[i-1][0]=0，自动得到 1；j=i（最右）时 dp[i-1][i]=0，也自动得到 1。）初始化 dp[1][1]=1 作为唯一种子。

代码（C++）

#include <iostream>
using namespace std;
int dp[31][31];
int main()
{
    int n;
    cin >> n;
    dp[1][1] = 1;                          // 种子：第 1 行第 1 列 = 1
    for(int i = 2; i <= n; i++)            // 从第 2 行开始递推
        for(int j = 1; j <= i; j++)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
    for(int i = 1; i <= n; i++)            // 按 %5d 输出
    {
        for(int j = 1; j <= i; j++)
            printf("%5d", dp[i][j]);
        printf("\n");
    }
    return 0;
}

运行结果（输入 5）

    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1

详解：输出恰好 5 行杨辉三角。第三行 1 2 1 中，2 = 1 + 1；第四行 1 3 3 1 中，3 = 1 + 2、3 = 2 + 1。每个都符合 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。

%5d 是 C 语言的格式化输出，用来右对齐到 5 个字符宽度，能保证输出对齐美观。时间复杂度 O(n²)，空间 O(n²)。

讲师加餐・选择题精讲

12.（二维 DP 边界） 杨辉三角用 dp[i][j]=dp[i-1][j]+dp[i-1][j-1] 递推时，为什么 j=1 和 j=i 的"边"能自动得到 1？ A. 因为代码里专门写了 if 判断 B. 因为全局数组 dp 默认初始化为 0，dp[i-1][0] 和 dp[i-1][i] 都是 0，0+用于两肩的1 仍是 1 C. 因为 1 被硬编码进去了 D. 因为会数组越界崩溃

逐项分析：A 错，代码没有 if 特判。C 没硬编码。D 错，不越界——因为 j 最多到 i，dp[i-1][i] 是合法位置（不过该位置恰好没被填过，值为 0）。B 正确：全靠"越界区默认 0"这个前提，0 加上合法的 1 仍是 1。所以 B 正确。同理，局部数组必须手动 memset 为 0，否则未初始化值是垃圾，而全局数组默认为 0 正好利用上。

Day05：游游的you（贪心+模拟）・腐烂的苹果（多源 BFS）・孩子们的游戏（约瑟夫环）

第五天终于上"图论 + 数学规律"了。腐烂的苹果是一个很好的多源 BFS 入门，孩子们的游戏则强烈推荐掌握数学解法。

第 1 题：游游的 you（贪心+模拟）

题干游游现在有 a 个 'y'，b 个 'o'，c 个 'u'，他想用这些字母拼成一个字符串。规则：如果在字符串中三个相邻字母是 "you"，可以获得 2 分；两个相邻字母是 "oo"，可以获得 1 分。请问最多能获得多少分？

官方示例 1：输入：1 1 1 输出 2（拼出 you 得 2 分）输入：2 3 2 输出 4（拼出 oyouyou 得 4 分）输入：1 5 2 输出 5（拼出 uooooyou 得 5 分）数据范围：1 <= a,b,c <= 1e9，最多 1e5 组询问。

思路贪心 + 模拟。核心观察：you 和 oo 是"独立"的，但 you 的分值更高，因此要优先拼 you，再考虑 oo。

能拼出的 you 个数 x = min(a, min(b, c))（三种字母中个数最少的那个决定上限）；
每个 you 得 2 分，得到 2 * x 分；
拼完 you 后，'o' 还剩下 b - x 个。这些 'o' 排成一排，可以形成"相邻两两"的 oo。n 个连续的 'o' 能形成 n-1 个"相邻两字母对"（例如 ooo 可看作 oo + oo 重叠计 2 分）。所以若 b - x >= 2，还能加 (b - x - 1) 分。

代码（C++）

#include <iostream>
using namespace std;
int main()
{
    int q;
    int a, b, c;
    cin >> q;
    while(q--)                 // a,b,c 分别代表 'y','o','u' 的个数
    {
        cin >> a >> b >> c;
        int x = min(a, min(b, c));         // 最多能拼出的 "you" 个数
        // 每个 you 得 2 分；剩 b-x 个 'o' 连续排列最多得到 b-x-1 对 "oo"（各 1 分）
        cout << (x * 2 + max(b - x - 1, 0)) << endl;
    }
    return 0;
}

运行结果（用官方示例输入三组：2 3 2 / 5 6 5 / 1 5 2）

4
10
5

详解：

第一组 a=2,b=3,c=2：x = min(2,3,2) = 2，得 4 分；剩 o 为 3-2=1，b-x-1 = 0。结果 4。
第二组 a=5,b=6,c=5：x=5，得 10 分；b-x=1，再加不了。结果 10。
第三组 a=1,b=5,c=2：x=1，得 2 分；b-x=4，4-1=3，再加 3 分。2+3=5，对应示例的 uooooyou（1个you=2分，4个连续o有3个oo=3分）。

注意必须用 long long 吗？数据到 1e9，2*x 可能到 2e9 刚好卡在 int 上限边缘；稳妥起见竞赛里我会建议开 long long（源码这里用 int，是因为按平台数据范围尚可，但你自己写时最好 long long 保险）。每组询问 O(1)，总复杂度 O(q)。

讲师加餐・选择题精讲

13. ooo（三个连续的 o）能获得多少分？ A. 1 分　B. 2 分　C. 3 分　D. 0 分

逐项分析：两个相邻字母是 oo 得 1 分。ooo 可以看作位置 (1,2) 是一对、位置 (2,3) 是另一对（允许重叠），所以得 2 分。A、C、D 都错，选 B。这正是一般化结论"n 个连续 o 得 n-1 分"的来源。

第 2 题：腐烂的苹果（NC398，多源 BFS）

题干给定一个 n x m 的网格，grid 中每个格子的值为 0（空）、1（完好的苹果）或 2（已经腐烂的苹果）。腐烂的苹果每分钟会向上下左右四个相邻格子传播一次，导致相邻的完好苹果腐烂。请问经过多少分钟，网格中不再存在完好苹果；如果有的苹果永远不会腐烂，则返回 -1。

思路这是多源 BFS 的标准题目（区别于单个起点的 BFS，这里所有初始烂苹果都是"源"）。用队列装载所有初始 2 的位置，然后按"分钟"分层扩散：

记录当前队列大小 sz（这一轮要处理的量）；
对这 sz 个坐标逐个向四个方向扩展，能感染（是 1）就标记 vis 并入队；
每处理完一整层，ret++（表示过了 1 分钟）。

BFS 结束后，再扫一遍网格：如果还存在值为 1 且从未被感染（!vis）的完好好苹果，说明不可能全腐烂，返回 -1；否则返回 ret - 1（去掉初始那一轮计数）。

代码（C++）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution
{
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[1010][1010] = { 0 };
public:
    int rotApple(vector<vector<int> >& grid)
    {
        m = grid.size(); n = grid[0].size();
        queue<pair<int, int> > q;
        for(int i = 0; i < m; i++)            // 多源：所有初始腐烂苹果入队
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 2) q.push({i, j});
 
        int ret = 0;
        while(q.size())                       // 按"分钟"分层扩散
        {
            int sz = q.size();
            ret++;
            while(sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
                    {
                        vis[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }
        for(int i = 0; i < m; i++)            // 有没有"永远烂不完"的好苹果
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 1 && !vis[i][j]) return -1;
        return ret - 1;                       // 去掉初始那一轮
    }
};
 
int main()   // 演示包装
{
    Solution s;
    vector<vector<int> > grid = {{2, 1, 1}, {1, 0, 1}, {1, 1, 1}};
    cout << s.rotApple(grid) << endl;
    return 0;
}

运行结果

详解：网格

2 1 1
1 0 1
1 1 1

初始腐烂源头在 (0,0)（下标从 0 计）。逐分钟向上下左右扩散：

第 1 分钟：感染 (0,1)、(1,0)；
第 2 分钟：感染 (0,2)、(2,0)；
第 3 分钟：感染 (1,2)、(2,1)；
第 4 分钟：感染 (2,2)。

此时所有值为 1 的完好苹果都已腐烂，共需 4 分钟，程序返回 4。这道题最容易漏掉的是右下角 (2,2)——它直到第 4 分钟才被波及，手算时稍不留意就可能漏数。这也正是"多源 BFS + 分层扩散"必须逐层推进、全程不跳步的价值所在：只有老老实实按分钟扩散，才能把"定格几分钟"数得精确，避免漏格子导致结果偏小。

复杂度：每个格子最多入队一次，O(mn)，空间 O(mn)。

讲师加餐・选择题精讲

14. 多源 BFS 中，返回 ret - 1 而不是 ret，根本原因是？ A. 因为烂苹果第一分钟就把周围传染了 B. 因为初始那些"已经是 2"的源并不消耗分钟，ret 从 0 起每层 +1，第一次累加对应的是"第 0 分钟" C. 因为答案刚好比最大层数少 1 D. 因为 ret 是从 1 开始数的

逐项分析：A 表述不准确。细看代码 ret 初始为 0，每进入一层 while 就 +1；第一层 while 处理的恰恰是初始源 sz=1（(0,0)）这一层，此时并没有真正"消耗"满一分钟去传播（它自己就是源）。要表达"新被传染的层数"，得把这第一次+1去掉，故 ret-1。C 大约对但理由没说清，B 最准确。所以 B 正确。

第 3 题：孩子们的游戏 / 约瑟夫环（JZ62）

题干每年六一儿童节都会玩一个游戏：让 n 个小朋友围成一个大圈，编号 0 ~ n-1。随机指定一个数 m，然后编号为 0 的小朋友开始报数，每次数到 m-1 的那个小朋友出列且不再回到圈中，从他的下一个小朋友重新从 0 开始报数。请求出最后一个留在圈里的小朋友的编号。

思路题目标准解法有两种：

解法一（模拟）：用数组/链表模拟逐个删除。直观但时间复杂度 O(n*m)，数据量大时可能会超时。
解法二（数学递推）：这是本题经典的最优解法。设 f(i) 表示"i 个人围成圈、报数到 m-1 出列时，最后剩下的人在下标为 0~(i-1) 的新环中的编号"。可以推导出递推式：

f(i) = (f(i-1) + m) % i，初始 f(1) = 0。

从 i=2 迭代到 n，最后 f(n) 就是答案。代码极短，时间复杂度 O(n)。

代码（C++，数学优解）

#include <iostream>
using namespace std;
class Solution
{
public:
    int LastRemaining_Solution(int n, int m)
    {
        int f = 0;                       // n=1 时剩下编号 0
        for(int i = 2; i <= n; i++)      // 逆推：从 2 个人推到 n 个人
            f = (f + m) % i;
        return f;
    }
};
 
int main()   // 演示包装
{
    Solution s;
    cout << s.LastRemaining_Solution(5, 3) << endl;   // n=5, m=3
    cout << s.LastRemaining_Solution(1, 10) << endl;  // 只有 1 个人，直接返回 0
    return 0;
}

运行结果

3
0

详解：n=5, m=3。手动走一遍：编号 0 1 2 3 4，从 0 开始数到 2（m-1=2）出列的是 2；剩下 0 1 3 4，从 3 开始数到 2，是 0；剩下 1 3 4，从 1 数到 2，是 4；剩下 1 3，从 1 数到 2，是 1；最后剩 3。答案是 3，程序第一行输出 3。n=1 时直接剩编号 0，程序第二行输出 0。

一题多解（模拟版，供对比）：用 std::list 或 vector 模拟删除，代码直观但慢：

// 模拟版（数据量大时可能超时，仅作对照理解）
#include <iostream>
#include <list>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    list<int> ring;
    for(int i = 0; i < n; i++) ring.push_back(i);
    auto cur = ring.begin();
    while(ring.size() > 1)
    {
        for(int i = 0; i < m - 1; i++)       // 数 m-1 步
        {
            cur++;
            if(cur == ring.end()) cur = ring.begin();  // 成环
        }
        cur = ring.erase(cur);               // 删除并回到下一个
        if(cur == ring.end()) cur = ring.begin();
    }
    cout << *ring.begin() << endl;
    return 0;
}

模拟版复杂度 O(n*m)，在 n、m 很大时明显逊于 O(n) 的数学版。纸上容器图一轮，递推式就一目了然：删除后的环重新编号，剩余问题规模减一，原有结果下标和新下标相差 m（模新的 i）。

讲师加餐・选择题精讲

15. 关于约瑟夫环的数学递推 f = (f + m) % i，下列说法正确的是？ A. i 应该从 2 循环到 n，f 初值为 0 B. 该递推可以顺推，也能逆推；代码里从 i=2 逐步累加到 n 是"从小到大还原规模" C. n=0 时答案是 -1 D. 以上都对

逐项分析：A 对（f(1)=0，从 2 到 n）。B 对。"逆推"通常指从已知小规模反推大规模，这里是正着用小规模推大规模，本质是从 f(1) 逐步推到 f(n)。C 对：原题若 n=0（没有人）一般约定返回 -1。三者均成立，选 D。

Day06：大数加法（高精度）・链表相加(二)・大数乘法（高精度）

第六天正式进入高精度运算，是"模板型"题目，把竖式模拟做成代码即可，但坑也不少。这三题几乎就是面试/笔试里高精度加乘的题库。

第 1 题：大数加法（NC1）

题干以字符串形式读入两个非常大正整数（长度可达上千甚至上万位，远超任何内置整数类型），请计算它们的和并作为字符串返回。输入不含前导 0，输出也不含前导 0。

思路模拟"列竖式"加法。因为要从个位对齐，我们从两个字符串的末尾（个位）往前逐位相加，同时维护一个进位 tmp。核心循环条件 while(i >= 0 || j >= 0 || tmp) 意思是"只要还有数位没加完、或还有进位没处理完就要继续"。每一轮把两个当前位和进位加起来，结果的当前位 = 和 % 10，进位 = 和 / 10。由于是从低位往高位拼进 ret，最终结果低位在前，需要 reverse 回来。

代码（C++）

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Solution
{
public:
    string solve(string s, string t)
    {
        string ret;
        int tmp = 0;                            // 进位 + 本次累加和
        int i = s.size() - 1, j = t.size() - 1; // 从个位（末尾）开始
        while(i >= 0 || j >= 0 || tmp)          // 还有数位或进位就继续
        {
            if(i >= 0) tmp += s[i--] - '0';
            if(j >= 0) tmp += t[j--] - '0';
            ret += '0' + tmp % 10;              // 取当前位的值
            tmp /= 10;                          // 保留进位
        }
        reverse(ret.begin(), ret.end());        // 别忘逆序
        return ret;
    }
};
 
int main()   // 演示包装
{
    Solution s;
    cout << s.solve("999", "1") << endl;      // 大数 + 1，测试连续进位到最高位
    cout << s.solve("123", "359") << endl;     // 普通进位
    return 0;
}

运行结果

1000
482

详解：

"999" + "1"：从末尾加，9+1=10，本位 0，进位 1；9+进位1=10，本位 0，进位 1；9+1=10，本位 0，进位 1；最后进位不为 0，再补一位 1。结果拼出 0001，reverse 后 1000。这个用例专门考验进位连续传播到最高位。
"123" + "359"：3+9=12，本位 2 进 1；2+5+1=8，本位 8 进 0；1+3=4。结果 482。

复杂度：O(|s| + |t|)，空间 O(1)（不计返回串）。

讲师加餐・选择题精讲

16. 大数加法里 reverse 是必须的，原因正确的是？ A. 因为 while 是从个位加起，往 ret 拼接的是"低位在前"，不反转则输出反了 B. 因为 reverse 能把数字变大 C. 因为字符数组必须反转才能运算 D. 因为要处理前导零时才需要反转

逐项分析：A 完全正确——循环从个位开始，先拼出的是结果的个位，整个 ret 是"低位在前"，而正常的十进制输出要"高位在前"，所以必须 reverse。B、C、D 都不成立。选 A。

第 2 题：链表相加(二)（NC40）

题干两个链表分别代表两个大整数，每个节点的值是一个数字（0~9）。链表的头代表该数的最高位（例如 9->3->7 表示 937）。请计算这两个数的和，返回同样格式的链表（头为最高位）。

思路和"大数加法"一个道理，但载体换成了链表，且数值是高位在前（和我们竖式习惯相反）。套路是三步：逆序让个位对齐 → 高精度相加（从低位即逆序后的头部开始）→ 把结果再逆序回来。

逆序用头插法即可。相加时维护进位 t，把每个节点的值加到 t 上，新建节点存 t % 10，进位 t /= 10。

代码（C++）

#include <iostream>
using namespace std;
struct ListNode {
    int val; ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};
class Solution
{
public:
    // 逆序链表（头插法）
    ListNode* reverse(ListNode* head)
    {
        ListNode* newHead = new ListNode(0);   // 哨兵
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newHead->next;   // 头插
            newHead->next = cur;
            cur = next;
        }
        cur = newHead->next;
        delete newHead;                  // 释放哨兵
        return cur;
    }
 
    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        // 1. 两个链表都逆序，让低位对齐
        head1 = reverse(head1);
        head2 = reverse(head2);
        // 2. 高精度加法（从低位开始）
        int t = 0;                              // 进位 + 当前累加和
        ListNode* cur1 = head1, *cur2 = head2;
        ListNode* ret = new ListNode(0);        // 哨兵
        ListNode* prev = ret;
        while(cur1 || cur2 || t)
        {
            if(cur1){ t += cur1->val; cur1 = cur1->next; }
            if(cur2){ t += cur2->val; cur2 = cur2->next; }
            prev = prev->next = new ListNode(t % 10);
            t /= 10;
        }
        cur1 = ret->next;
        delete ret;                              // 释放哨兵
        // 3. 结果再逆序回来
        return reverse(cur1);
    }
};
 
// —— 以下是本地演示用的辅助代码 ——
ListNode* build(int a[], int n){
    ListNode* head = new ListNode(0); ListNode* p = head;
    for(int i = 0; i < n; i++) p = p->next = new ListNode(a[i]);
    return head->next;
}
void print(ListNode* h){
    while(h){ cout << h->val << " "; h = h->next; }
    cout << endl;
}
int main()
{
    // 9 -> 3 -> 7 表示 937；6 -> 3 表示 63；和为 1000
    int a[] = {9, 3, 7}; int b[] = {6, 3};
    ListNode* h1 = build(a, 3); ListNode* h2 = build(b, 2);
    Solution s;
    ListNode* ret = s.addInList(h1, h2);
    print(ret);
    return 0;
}

运行结果

1 0 0 0

详解：937 + 63 = 1000。逆序后个位对齐相加，得低位在前的结果 0001，再逆序为 1000，输出链表 1 -> 0 -> 0 -> 0。程序输出 1 0 0 0。

时间复杂度 O(n+m)（三次遍历各 O(长度)），空间 O(1) 额外（不计算结果链）。

易错点：一是别忘了最高位进位（这里 999+1=1000 就靠循环条件里的 || t 兜住）；二是别忘最后把结果再逆序回来（我们最初逆序了，算完必须逆序回去）；三是用哨兵 ret 简化头插，记得 delete 防泄漏（OJ 一般不管，本地演示要规范）。

第 3 题：大数乘法（NC10）

题干以字符串形式读入两个非负整数（可能达到几十万位），计算它们的乘积并作为字符串返回。输入保证不含前导 0（单个 0 除外）。

思路经典竖式模拟，但要改进：不逐位立即进位，而是分两步——

无进位相乘相加：一位一位交叉相乘，把相同"权重位"（对应 tmp[i+j]）的结果累加到一起（先不去进位的净乘积累加）。
统一处理进位：从低位到高位扫 tmp，c += tmp[i]，当前位 c % 10 写进结果，进位 c /= 10。

之后处理前导零（比如 0 * 99 = 000...，要多位拼接后删除前面多余的 0），最后 reverse 得到正确顺序。

之所以先"无进位"再做进位，是把乘法的两次嵌套循环和进位的处理彻底解耦，代码更清晰，也不容易在进位乱掉。

代码（C++）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    string solve(string s, string t)
    {
        reverse(s.begin(), s.end());   // 低位对齐
        reverse(t.begin(), t.end());
        int m = s.size(), n = t.size();
        vector<int> tmp(m + n);        // 无进位乘积累加结果
        // 1. 无进位相乘相加
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                tmp[i + j] += (s[i] - '0') * (t[j] - '0');
        // 2. 统一处理进位
        int c = 0;
        string ret;
        for(auto x : tmp)
        {
            c += x;
            ret += c % 10 + '0';
            c /= 10;
        }
        while(c)                        // 可能还有更高位的进位
        {
            ret += c % 10 + '0';
            c /= 10;
        }
        // 3. 处理前导零（如 0 * 任何数）
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
 
int main()   // 演示包装
{
    Solution s;
    cout << s.solve("123", "45") << endl;    // 5535
    cout << s.solve("999", "999") << endl;   // 998001
    cout << s.solve("0", "9999") << endl;    // 0（前导零测试）
    return 0;
}

运行结果

5535
998001
0

详解：

123 * 45：拆分成 123*5 + 123*40 的竖式，最终 5535。
999 * 999 = 998001，验证大数乘法的进位链。
0 * 9999：无进位相乘后 tmp 全 0，若不处理前导零会输出 0000，代码里 while(ret.size() > 1 && ret.back() == '0') pop_back() 把多余的 0 删掉，只留一个 0。程序输出 0。

复杂度：双重循环 O(|s| * |t|)，空间 O(|s|+|t|)。这是朴素高精度乘法，大数场景下已是常见板子。

补充一个知识点：大数乘法还有更快的算法（如 FFT/NTT 优化的卷积乘法，复杂度可从 O(n²) 降到 O(n log n)），那是竞赛高级话题，本届笔试到"无进位相乘 + 统一进位"这一版就足够覆盖绝大多数题。

讲师加餐・选择题精讲

17. 上面"先无进位相乘相加，再统一进位"的版式中，tmp[i+j] += (s[i]-'0')*(t[j]-'0') 中 i+j 的含义是？ A. 两个数字相乘后所在的结果权重位 B. 两个下标的和 C. 相乘后进位的个数 D. 一个任意的临时变量

逐项分析：s 和 t 都已反转（个位在 0 号位），所以 s[i] 是 10^i 位、t[j] 是 10^j 位，乘积自然是 10^(i+j) 位，累加到 tmp[i+j]。A 正确。B、C、D 不对。选 A。同理前导零的删除条件是"size()>1 且末尾是 '0'"——注意不能把唯一的 0 也删掉。

本周复盘（一图流）

一周 18 题，其实可以用一张表收拢"题型 -> 核心套路 -> 复杂度"：

Day	题目	核心套路	时间复杂度
1	数字统计	逐位取数 `%10` `/10`	O((R-L)·logR)
1	两个数组的交集	哈希标记 + 去重	O(n+m)
1	点击消除	栈 / 相邻匹配	O(n)
2	牛牛的快递	分情况 + `ceil`	O(1)
2	最小花费爬楼梯	线性 DP `dp[i]=min(...)`	O(n)
2	两字符串最小距离	贪心 + 最近前驱	O(n)
3	简写单词	流式读词 `cin>>s`	O(单词总长)
3	dd爱框框	同向双指针（滑动窗口）	O(n)
3	除2!	贪心 + 大根堆	O((n+k)log n)
4	Fibonacci	递推找最近两项	O(log n)
4	单词搜索	DFS + 回溯	O(mn·4^L) 最坏
4	杨辉三角	二维 DP	O(n²)
5	游游的you	贪心优先拼 you	O(q)
5	腐烂的苹果	多源 BFS	O(mn)
5	孩子们的游戏	约瑟夫环数学递推	O(n)
6	大数加法	模拟竖式 + 进位	O(len)
6	链表相加(二)	逆序 + 加法 + 逆序	O(n+m)
6	大数乘法	无进位乘加 + 统一进位	O(n·m)

最后几句话给你三个"本周围绕的共性提醒"：

别丢了边界：区间含不含端点、while 进不进得去、进位有没有传到最后、最高位加出来没——第四、第六天几乎每道题都在考这个。
选择合适的容器/数据结构：去重可用数组哈希但要看值域；维护动态最值用优先队列；相邻消除用栈；分层扩散用 BFS + 依层计数。
"先推演，后编码"：高精度三连最能体现这一点——先在纸上把竖式/链路画清楚，代码只是把过程翻译一遍。

这一周的内容到此收尾。建议你把每道题亲手敲一遍、跑一遍，再用我给的"选择题精讲"自测一遍易错点。下周我们继续往更难的坑里走。欢迎在评论区把你不确定的题目发出来一起讨论。

我是资深 C/C++ 笔试强训讲师，如果你在读这篇文章时发现任何表述或代码可以改进的地方，欢迎随时指出 —— 我们把每一周的强训都做到"全世界最详尽"。