先把话说在前面：这一周的题，比前四周"狠"了不少。前面你可能还在热身，这周直接从模拟、排序、滑动窗口，一路干到 01 背包、树形 DP、BFS 和贪心。很多题你不光要"会做"，还要会"用对数据结构"。比如同样是区间问题，一道题排序一下就完事，另一道题却必须搬出优先队列；同样是"最长上升子序列"，朴素 DP 过不了的 10^5 数据，就得换成"贪心 + 二分"。

所以我这一篇，刻意把这 18 道题里面最容易摔跟头的地方都挑出来揉碎了讲。每道题我都会给：题干（把它翻译成人话）→ 思路（先讲"怎么想到"）→ 完整可编译运行的代码（逐行注释）→ 真实运行结果（我本机用 g++ 实际编译跑出来的）→ 详解（把坑、细节、边界全交代清楚）。

需要先说明一点：下面所有"运行结果"都不是我编的，是我把代码存成 .cpp，用 MinGW 的 g++ 实际编译、实际喂数据跑出来的。你完全可以复制代码到本地或在线 OJ 上验证，结果应该一致。

整周题目按知识点分布，我拆成六块来收：

  • Day 25：模拟入门 → 笨小猴；排序判重叠 → 主持人调度（一）；01 背包 → 分割等和子集。
  • Day 26：字符串找规律 → 小红的 ABC；线性 DP → 不相邻取数；滑动窗口 → 空调遥控。
  • Day 27：排列组合 → kotori 和气球；BFS → 走迷宫；贪心 + 优先队列 → 主持人调度（二）。
  • Day 28：数学 → 游游的重组偶数；DFS 枚举 → 体操队形；树形 DP → 二叉树中的最大路径和。
  • Day 29：指针模拟 → 排序子序列；贪心 → 削减整数；贪心 + 二分 → 最长上升子序列（二）。
  • Day 30：数学素数 → 爱吃素；滑动窗口 → 相差不超过 k 的最多数；经典 DP → 最长公共子序列（一）。

下面开讲。每一题都是一句"上个厕所的功夫能想通、但笔试现场容易写错"的题，我尽量给你讲明白。

Day 25 · 模拟、排序与第一次触碰背包

题目 1：笨小猴（模拟）

题干。 一道朴素的模拟题，题目本身很简单：给你一个只含小写字母的单词，统计每个字母出现了多少次，取其"出现次数最多的次数" maxn 和"出现次数最少的次数" minn（只统计出现过的字母，没出现的不算）。算出差值 maxn - minn。如果这个差值是一个质数，第一行输出 Lucky Word，第二行输出这个差值；否则第一行输出 No Answer，第二行输出 0。

翻译成人话：数数 → 找最大最小次数 → 作差 → 判断差是不是质数 → 按要求输出。

思路。 这题没有任何算法难度，全靠细心。三个容易错的地方：

  1. minn 不能直接初始化成 0，否则如果一个字母出现过、而它自己就是出现次数最少的，min(minn, ...) 永远卡在 0 上、丢掉真实的"最少次数"。所以 minn 要初始化成一个足够大的数（比如 1000），只在"该字母出现过"时才参与求最小。
  2. 质数判断函数 isprim，1 和 0 都要返回 false（1 不是质数，0 当然也不是）。
  3. 质数判断只要枚举到 sqrt(n) 就够了，i <= sqrt(n) 别漏了等号，否则 4 会被误判成质数。

这道题其实就是"读进来一个词，用哈希表（这里用 26 长度的数组当哈希）统计出现次数"。hash[ch - 'a'] 是统计字母的经典写法：字符 'a' 是 97，减掉 'a' 的下标就是 0，于是正好对应到数组的第 0 格。

完整可运行代码：

#include <iostream>
#include <cmath>    // sqrt
#include <string>
using namespace std;
 
string s;
 
// 判断 n 是否是质数
bool isprim(int n)
{
    if (n < 2) return false;          // 0 和 1 都不是质数，直接判否
    for (int i = 2; i <= sqrt(n); i++) // 只需试除到根号 n，i 取到 n 的算术平方根
    {
        if (n % i == 0) return false; // 有因子，不是质数
    }
    return true;                       // 遍历完都没因子，是质数
}
 
int main()
{
    cin >> s;                          // 读入单词
    int hash[26] = { 0 };              // 26 个字母的计数器，全部初始化为 0
 
    // 统计每个字母出现的次数
    for (auto ch : s)
    {
        hash[ch - 'a']++;              // 字符映射成下标 0~25
    }
 
    int minn = 1000, maxn = 0;         // 最小次数初始化为很大的数，最大次数初始化为 0
 
    // 遍历所有字母，找出现过的字母中的最少次数与最多次数
    for (int i = 0; i < 26; i++)
    {
        if (hash[i])                   // 这个字母出现过（次数非 0）
        {
            minn = min(minn, hash[i]); // 更新最少
            maxn = max(maxn, hash[i]); // 更新最多
        }
    }
 
    // 差值是否为质数
    if (isprim(maxn - minn))
    {
        cout << "Lucky Word" << endl;
        cout << maxn - minn << endl;
    }
    else
    {
        cout << "No Answer" << endl;
        cout << 0 << endl;             // 注意：不幸运时第二行输出固定是 0
    }
    return 0;
}

运行结果（我用单词 aaaabcde 实测）：

aaaabcde
Lucky Word
3

验证一下：aaaabcde 里字母 a 出现 4 次，b、c、d、e 各 1 次。maxn = 4，minn = 1，差值 4 - 1 = 3。3 是质数，所以输出 Lucky Word 和 3。完全对得上。

详解。 这道题真正的考点就三个字：细心。

  • minn 初始化成 1000 而不是 0，这是绝大多数人会踩的坑。很多人写成 minn = 0，然后发现一旦某个字母只出现 1 次，minn 永远是 0，差值被算大，导致质数判断全错。
  • 没出现过的字母不能参与求最小。比如单词里根本没有字母 z，那 hash['z'-'a'] 是 0，你不能把 0 当"最少出现次数"算进去。
  • sqrt(n) 判断质数，注意循环条件取等号。判定 n 是否为质数，试除到 sqrt(n) 就足够，因为如果 n 有大于 sqrt(n) 的因子，必然配对一个小于 sqrt(n) 的因子。
  • 输出格式别错：不幸运时第二行输出的是 0，不是"差值"。题目明确要求输出 0。

题目 2：主持人调度（一）（排序判重叠）

题干。 牛客 NC383。有一堆活动区间 [start, end]，问你：能不能只用一个主持人，把这一整场从第一个活动开场到最后一个活动收尾全部主持下来？换句话说，判断这些活动区间两两之间是否存在重叠——若所有区间都互不重叠（前一个结束，下一个才开始，边界相接 end == start 算不重叠），返回 true；只要存在任意两个区间重叠，就必须再来一个主持人，返回 false。

思路。 区间问题的第一反应就是排序：要么按左端点排，要么按右端点排。这里我们按左端点升序排。

为什么要按左端点排？排好之后，后面的区间起点一定不早于前面的区间起点。那么只要检查"相邻两个区间是否重叠"就够了——因为左端点有序后，"第 i 个区间"只要不和它前面一个区间重叠，就绝不会和更前面的区间重叠。为什么？因为更前面的区间起点更小、且与前一个不重叠，它的右端点也就更靠前，自然也不会顶到第 i 个区间。于是问题退化成一行判断：

如果 schedule[i].start < schedule[i-1].end：说明第 i 个区间在上一个还没结束的区间之前（之内）开始了，重叠，返回 false。

注意边界：end == start 时算不重叠，所以用严格小于 <，而不是 <=。

完整可运行代码：

#include <iostream>
#include <vector>
#include <algorithm>   // sort
using namespace std;
 
class Solution
{
public:
    bool hostschedule(vector<vector<int> >& schedule)
    {
        sort(schedule.begin(), schedule.end());  // 按左端点升序排列
        for (int i = 1; i < schedule.size(); i++)
        {
            // 当前区间左端 < 前一个区间右端，说明有重叠
            if (schedule[i][0] < schedule[i - 1][1]) return false;
        }
        return true;   // 全部不重叠，一个主持人够用
    }
};

运行结果（本机实测两组）：

true        // 输入 [[1,3],[4,6],[7,9]]，互不重叠
false       // 输入 [[1,4],[3,5],[6,8]]，[1,4] 与 [3,5] 重叠

详解。 它的核心价值在于：左端点有序之后，"相邻不重叠"等价于"全局不重叠"。这是一条非常有用的区间直觉，后面 Day 27 的"主持人调度（二）"还会再次用到类似思想，只是那道题要求的是"最少需要几个人"，就得上优先队列了。

坑点就一个：边界。活动 [1,3] 和 [3,5]，第 3 分钟结束、第 3 分钟开始，主持人完全可以无缝切换，所以不算重叠。因此判断得用 < 而不是 <=。

另外注意题目给的完整函数签名是 bool hostschedule(vector<vector<int> >& schedule)，vector 作为参数直接传引用，避免拷贝。

题目 3：分割等和子集（01 背包）

题干。 给你 n 个正整数，问能否把这堆数分成两个子集，使两个子集的和相等。比如 [1,5,11,5]，可以分成 [1,5,5] 和 [11]，两边和都是 11，返回 true。输出按要求 true / false。

思路。 这是一个非常经典的 01 背包变体。先算总和 sum：

  • 如果 sum 是奇数，两个相等整数和是偶数，肯定分不成，直接 false。
  • 如果 sum 是偶数，问题就变成：能不能从 n 个数里挑出一些，让它们的和恰好等于 sum / 2？ 因为一旦挑出一个和等于一半的子集，剩下的天然就是另一半。

于是转化为 01 背包的"恰好装满"问题：

  • 物品：每个数，重量等于它的值。
  • 背包容量：target = sum / 2。
  • 问：能否恰好装满容量 target。

定义 dp[i][j] 表示"考虑前 i 个数，能否凑出总和 j"。转移：

  • 不选第 i 个数：dp[i][j] = dp[i-1][j]。
  • 选第 i 个数（j >= arr[i] 时）：dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i]]。
  • 初始 dp[0][0] = true（0 个数凑 0，成立）。剩下的 dp[0][j] 全为 false。

最终看 dp[n][target]。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int N = 510;
const int M = 510 * 110 / 2;   // sum / 2 的上界，给 dp 开够空间
 
int n;
int arr[N];
bool dp[N][M];                 // dp[i][j]：前 i 个数能否凑出总和 j
 
int main()
{
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        sum += arr[i];         // 累加总重量
    }
 
    if (sum % 2 == 1)          // 总重量为奇数，不可能分成两等份
    {
        cout << "false" << endl;
    }
    else
    {
        sum /= 2;              // 目标容量 = 总和的一半
        dp[0][0] = true;       // 0 个数凑 0，可行
 
        // 遍历每个数（物品）
        for (int i = 1; i <= n; i++)
        {
            // 遍历所有容量
            for (int j = 0; j <= sum; j++)
            {
                dp[i][j] = dp[i - 1][j];              // 不选第 i 个数
                if (j >= arr[i])                       // 容量允许时才可选
                {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i]]; // 选第 i 个数
                }
            }
        }
 
        if (dp[n][sum]) cout << "true" << endl;       // 能凑出目标
        else cout << "false" << endl;
    }
    return 0;
}

运行结果（本机实测输入 4 1 5 11 5）：

4 1 5 11 5
true

详解。 这里有两个必须讲透的点。

第一，奇偶性剪枝。sum 为奇数直接判否，这是最便宜的优化，能省一整轮 DP。

第二，为什么这是"恰好装满"而不是"最大价值"。经典的 01 背包求最大值，这里改用 bool 记录"能不能凑出某个体积"，就是所谓的可行性背包或恰好装满型。类似的问题还有："能不能从中取出若干数，和为某个定值"。这种"选 / 不选"本质就是 01 背包。

一个性能提醒：dp 开的是 bool[N][M]，M = 510*110/2 ≈ 28050，乘上 N=510 约 1400 万，内存和两重循环都在可接受范围。真正的 01 背包还能滚成一维数组（dp[j] += dp[j - w[i]]，且 j 从大到小遍历防止重复选），但这里我们为了讲解清晰保留二维。

Day 26 · 字符串找规律、线性 DP 与滑动窗口

题目 4：小红的 ABC（字符串 + 找规律）

题干。 给你一个只含 a、b、c 三种字符的字符串，问其中最短的回文子串的长度是多少。如果根本不存在任何长度大于等于 2 的回文子串，输出 -1。

思路。 这道题最妙的地方在于"只有三种字符"这个限制。因为字符只有三种，任何回文子串要想最短，它的长度只可能是 2 或 3：

  • 长度为 2 的回文：形如 aa、bb、cc——两个相邻字符相同，即 s[i] == s[i+1]。
  • 长度为 3 的回文：形如 aba、bab……即首尾两个字符相同、中间夹一个字符，即 s[i] == s[i+2]。

为什么最短只能是 2 或 3？因为长度为 1 的串虽然也算回文，但题目要的是长度不小于 2 的回文；而一旦要长度 ≥ 2，最短的回文必然是 2（两个相同）或 3（两头同中间夹一个）。长度 4 以上还能是回文的情况，比如 abba，但它里面已经包含了长度 2 的 bb，所以只要能找到更短的 2，就轮不到它。所以只要存在长度为 2 的回文，答案就是 2；否则如果存在长度为 3 的回文，答案就是 3；两者都没有才是 -1。

那么枚举所有位置作为中心，检查 s[i] == s[i+1]（长度 2）和 s[i] == s[i+2]（长度 3）即可，注意下标越界。

完整可运行代码：

#include <iostream>
#include <string>
using namespace std;
 
string s;
 
int main()
{
    cin >> s;                        // 读入字符串
    int ret = -1;                    // 先假设不存在回文，输出 -1
    int n = s.size();
 
    for (int i = 0; i < n; i++)
    {
        // 判断是否存在长度为 2 的回文（相邻相同）
        if (i + 1 < n && s[i] == s[i + 1])
        {
            ret = 2;                 // 有长度为 2 的就是最短，直接锁定 2
            break;                   // 2 已经是最短的，不必再找，直接跳出
        }
        // 判断是否存在长度为 3 的回文（两头同，中间夹一个）
        if (i + 2 < n && s[i] == s[i + 2])
        {
            ret = 3;                 // 记录但不断言，因为后面可能遇到长度 2
        }
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本机实测两组）：

aab
2

abac
3

aab 是发现 aa（下标 0、1）构成长度 2 的回文，直接输出 2；abac 是发现 aba（下标 0、2）构成长度 3 的回文，输出 3。

详解。 这题的"找规律"体现在：因为字符集只有三种，最短回文只可能是 2 或 3，不需要写通用的回文检测。这是一类非常典型的"利用数据范围特殊性质降复杂度"的题。如果字符集不是固定的三种，或者数据更强，就得回文中心扩展甚至 Manacher 了。

坑点：

  • 输出 -1：确实可能整个串都没有任何长度 ≥ 2 的回文。比如 abc，任何相邻都不等、也不存在 s[i]==s[i+2]，输出 -1。
  • 先判断长度 2 再判长度 3 的顺序：一旦找到长度 2，立即 break——因为答案是"最短"，只要存在长度 2，它就已经是最小可能的答案。若从头到尾只找到过长度 3、从未遇到长度 2，答案就是 3。

题目 5：不相邻取数（线性 DP）

题干。 给你 n 个数排成一列，你要从中取若干个数，但不能取位置相邻的两个数，问能取到的最大和是多少。这就是经典的"打家劫舍"问题：一排房子，不能同时偷挨着的两家，问最多偷多少。

思路。 典型的线性 01 决策 DP，用"状态机"思路写最稳。对第 i 个数做决定：

  • f[i]：选第 i 个数时，前 i 个数能取得的最大和。因为选了 i 就不能选 i-1，所以 f[i] = g[i-1] + arr[i]（g[i-1] 是"第 i-1 不选"的最优和）。
  • g[i]：不选第 i 个数时，前 i 个数能取得的最大和。不选它就没有相邻限制，第 i-1 可选可不选，所以 g[i] = max(f[i-1], g[i-1])。

最后答案是 max(f[n], g[n])。两个数列互相递推，这就是"状态机"；它把"选/不选"的相邻约束，拆成两个互相依赖的 DP 数组。

完整可运行代码：

#include <iostream>
using namespace std;
 
typedef long long LL;              // 数据可能较大，用 long long 保险
const int N = 2e5 + 10;
 
int n;
LL arr[N];
LL f[N], g[N];                     // f[i] 选第 i 个；g[i] 不选第 i 个
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    for (int i = 1; i <= n; i++)
    {
        f[i] = g[i - 1] + arr[i];      // 选 i：i-1 必不能选，累加 i-1 不选的最优值
        g[i] = max(f[i - 1], g[i - 1]); // 不选 i：i-1 选不选都行，取较大的
    }
 
    cout << max(f[n], g[n]) << endl;   // 最后一个数选或不选都行，取大者
    return 0;
}

运行结果（本机实测输入 5 1 2 3 4 5）：

5 1 2 3 4 5
9

验证一下：[1,2,3,4,5] 中取不相邻的最大和，取 1+3+5 = 9（不能取相邻的，2 和 3 相邻不能同取），输出 9，正确。

详解。 这个"状态机"写法是打家劫舍的标准姿势，也是动态规划里特别经典的一类：用两个 DP 数组分别代表"当前这一步取 / 不取"两个状态。以后你看到"不能选相邻"、"每个位置有开/关两种状态互相约束"这类问题，都可以往这个模型上靠。

  • 正确性：为什么 f[i] = g[i-1] + arr[i] 而不是 f[i-1]？因为选了 i，i-1 会被刚走完，绝对不能选，所以只能基于 g[i-1]。
  • g[i] 为什么取 max(f[i-1], g[i-1])？不选 i 时，i-1 是自由的——上一个到底选没选都不冲突，于是取两者里较优的。
  • 时间复杂度 O(n)，一次遍历搞定，空间可以滚成两个变量，但数组版更直观。

题目 6：空调遥控（排序 + 滑动窗口）

题干。 有 n 个学生，每人对自己理想的温度有一个偏好值。你只能给所有学生设定同一个温度。每个学生允许的误差是 p 度——也就是只要设定温度落在这个人偏好值的正负 p 范围内，他就满意。问：最多能让多少个学生同时满意？输入第一行是 n 和 p，第二行是 n 个偏好温度。

思路。 先把温度升序排序。一个学生满意的条件是：|设定温度 - t_i| <= p。想让尽可能多学生满意，这些学生选定之后，他们偏好的最大值与最小值之差最多是 2p（因为设定温度要同时落在每个人 ±p 范围内，等于要让所有区间 [t_i - p, t_i + p] 有公共交集，等价于 max(t_i) - min(t_i) <= 2p）。

于是问题变成：在排好序的数组里，找一个连续子区间，使区间内 最大 - 最小 <= 2p，且区间长度最大。 排序后"最大、最小"就是区间两端，所以这是一个经典的**滑动窗口（双指针）**问题：

  • left、right 两个指针维护当前窗口。
  • right 每次向右扩展一位。
  • 只要 arr[right] - arr[left] > 2p，说明窗口内差值超限，右移 left 收缩窗口。
  • 用 right - left + 1 更新答案。

完整可运行代码：

#include <iostream>
#include <algorithm>   // sort
using namespace std;
 
const int N = 1e6 + 10;
int n, p;
int arr[N];
 
int main()
{
    cin >> n >> p;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    sort(arr, arr + n);      // 升序排序
 
    int ret = 0, left = 0, right = 0;
    p *= 2;                  // 允许差值 = 2 * p
 
    while (right < n)        // 右指针不越界
    {
        // 窗口内最大 - 最小 超过 2p，就收缩左边界
        while (arr[right] - arr[left] > p)
        {
            left++;
        }
        ret = max(ret, right - left + 1); // 更新窗口长度
        right++;                          // 右指针右移，扩展窗口
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本机实测输入 3 1 1 2 3）：

3 1 1 2 3
3

n=3，p=1，温度 [1,2,3]。设定温度选 2，只有 1 和 3 差 2 > 2p=2 吗？3-1 = 2 <= 2p=2，所以三个人都能满意，输出 3。（用窗口：排序后 arr[2]-arr[0]=2 <= 2*1，窗口能装下全部 3 个。）正确。

详解。 这道题把"区间有公共交集"翻译成了"极差不超过 2p"，是个很关键的转换。

  • 为什么是 2p？设定温度 x 让第 i 个人满意需 x ∈ [t_i-p, t_i+p]。要同时让一个集合的人都满意，就是这些区间有公共交集，等价于 min(上界) >= max(下界)，即 max(t_i) - p <= min(t_i) + p，即 max(t_i) - min(t_i) <= 2p。这就是排序 + 窗口判断 arr[right] - arr[left] > 2p 的由来。
  • 滑动窗口的复杂度：每个元素最多被 left、right 各扫一遍，O(n lon n)（排序） + O(n)（窗口）。
  • 这也是 Day 30 的"相差不超过 k 的最多数"几乎一样的套路，那道题甚至更直白一些。

Day 27 · 排列组合、BFS 与贪心 + 优先队列

题目 7：kotori 和气球（组合数学）

题干。 有 n 种颜色，要吹 m 个气球排成一排，要求相邻两个气球颜色不同，问一共有多少种不同的方案数，结果对某个模数取模（这里 MOD = 109）。输出方案数。

思路。 组合计数，想清楚分步乘法定理：

  • 第一个气球：任意选，有 n 种颜色。
  • 第二个气球：只要和第一个不同，有 n - 1 种。
  • 第三个、第四个……每一个都只要和前一个不同就行，有 n - 1 种。

所以总数 = n × (n-1) × (n-1) × …×(n-1)，一共 m 个气球，后 m-1 个每个乘 (n-1)。即 ret = n * (n-1)^(m-1) mod 109。边乘边取模防止溢出。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int MOD = 109;
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    int ret = n;                 // 第一个气球 n 种取法
    for (int i = 0; i < m - 1; i++)
    {
        ret = ret * (n - 1) % MOD; // 后面每个气球有 n-1 种取法，边乘边取模
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本机实测输入 3 3）：

3 3
12

验证：3 种颜色，3 个气球，相邻不同色，总数 3 * 2 * 2 = 12，12 % 109 = 12。正确。

详解。

  • 这是最标准的乘法原理：每个位置的"选择数"只和它前一个位置的约束有关，且是定值 n-1（除了第一个是 n）。
  • 取模的坑：ret * (n-1) 可能溢出 int？当 n 和 m 较大时确实如此，所以每步都 % MOD。这里 MOD=109 较小，即便如此也建议边乘边模。若 n-1 或 n 大于 MOD，乘法前最好已经模过，习惯上可以写成 ((ret % MOD) * (n-1 % MOD)) % MOD，本数据范围下直接乘也可。
  • 边界：m=1 时循环不执行，输出 n。只有 1 个气球，随便选，n 种，正确。这道题属于"读懂题意就能秒"的组合计数。

题目 8：走迷宫（BFS）

题干。 给你一个 n×m 的迷宫，. 表示能走的路，* 表示障碍物（墙）。给定起点 (x1,y1) 和终点 (x2,y2)，问从起点到终点的最短步数是多少。如果终点就是障碍物、或者根本走不到，输出 -1。每次只能上下左右走一步，起点坐标从 1 开始计数。

思路。 最短路用 BFS：第一次到达某个格子时用的步数一定是最短步数（因为 BFS 逐层扩展）。用 dist[x][y] 记录到达该格子的最短步数，同时它也为 -1 时表示"还没到过"，起到 visited 的作用。

过程：

  1. 若终点是墙 *，直接返回 -1。
  2. dist 全部初始化 -1，起点 dist[x1][y1] = 0 入队。
  3. while 队列非空，弹出队首，向上下左右四方向尝试；若新位置在界内、是路 .、且 dist == -1，则入队并记录步数 = 当前步数 + 1；若恰好是终点，直接返回该步数。
  4. 队列空了还没到终点，返回 -1。

完整可运行代码：

#include <iostream>
#include <cstring>   // memset
#include <queue>
using namespace std;
 
const int N = 1010;
int dx[4] = {0, 0, 1, -1};   // 上下左右 4 个方向的行偏移
int dy[4] = {1, -1, 0, 0};   // 上下左右 4 个方向的列偏移
int n, m;
int x1, y1, x2, y2;
char arr[N][N];
int dist[N][N];              // 到达 (i,j) 的最短步数，-1 表示没到过
 
int bfs()
{
    if (arr[x2][y2] == '*') return -1;   // 终点是墙，走不到
 
    memset(dist, -1, sizeof dist);       // 初始全部标记为"未到达"
    queue<pair<int, int>> q;             // 队列存坐标
    q.push({x1, y1});
    dist[x1][y1] = 0;                    // 起点步数为 0
 
    while (q.size())
    {
        auto [a, b] = q.front();         // C++17 结构化绑定：取出队首 (行, 列)
        q.pop();
        for (int i = 0; i < 4; i++)      // 枚举四个方向
        {
            int x = a + dx[i], y = b + dy[i];
            // 在界内、是路、且没访问过
            if (x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] == '.' &&
                dist[x][y] == -1)
            {
                q.push({x, y});
                dist[x][y] = dist[a][b] + 1;   // 步数 = 当前位置步数 + 1
                if (x == x2 && y == y2) return dist[x2][y2]; // 到达终点
            }
        }
    }
    return -1;                           // 队列耗尽还没到，走不到
}
 
int main()
{
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    // 读迷宫（1 起始下标，方便与坐标对齐）
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];
 
    cout << bfs() << endl;
    return 0;
}

运行结果（本机实测 3×3 全路迷宫，起点 (1,1)、终点 (3,3)）：

3 3 1 1 3 3 ... ... ...
4

3×3 全是 .，从 (1,1) 到 (3,3) 最短步数为 4（如右→右→下→下），正确。

详解。 BFS 求最短路有两块核心技巧：

  1. dist 一表两用：既当 visited（== -1 判未访问），又存最短步数。这样省掉一个额外布尔数组。
  2. 方向数组 dx/dy：把四个方向的移动写进两个数组，循环里统一处理，避免手写四段重复代码，这是图论题的基本功。

两个细节特别容易错：

  • 坐标越界检查：传进来的下标是 1 起始，所以检查要写 >= 1 && <= n。有的题目是 0 起始，一套写法吃遍所有题的幻想不成立，务必按题目来。
  • 终点是墙：在 BFS 前专门判一下，否则起点绕半天队列排空才返回 -1，逻辑上也对，但提前判掉更稳。队列从一开始就没出口可去，最后自然会返回 -1，但显式判更清晰。

题目 9：主持人调度（二）（贪心 + 优先队列）

题干。 牛客 NC147。如果说 Day 25 那道是"能不能一个人干完"，这道就是"最少需要几个主持人"。给你 n 个活动区间 [start, end]，主持人可以无缝衔接（前一个结束的瞬间，后一个立刻开始算不冲突），问最少要安排多少个主持人，才能让所有活动都被主持到。

思路。 这题没法用"相邻判重叠"了，因为同一个时间段可能有多个活动在不同场地同时进行。核心是贪心：每个主持人尽量多接——一旦有主持人主持的活动结束时间 ≤ 当前活动的开始时间，就让他接着这个新活动，而不新开主持人。为此我们需要始终找到"结束最早"的那个主持人，于是用小根堆存各个主持人的"空闲时间"（即他手里最后一个活动的结束时间）：

  1. 按左端点升序排活动。
  2. 堆里先放第一个活动的结束时间（相当于第一个主持人主持完它）。
  3. 遍历后面每个活动：
    • 若该活动开始时间 >= 堆顶（堆顶是结束最早的主持人的结束时间），说明这个主持人可以接手新活动，弹掉堆顶、把新活动的结束时间入堆，复用同一个主持人。
    • 否则说明所有主持人此刻都在忙，只能新开一个主持人，把新活动结束时间入堆。
  4. 最终"堆的大小"就是需要的主持人人数。

完整可运行代码：

#include <iostream>
#include <vector>
#include <algorithm>   // sort
#include <queue>       // priority_queue
using namespace std;
 
class Solution
{
public:
    int minmumNumberOfHost(int n, vector<vector<int>>& startEnd)
    {
        sort(startEnd.begin(), startEnd.end());           // 按左端点升序
 
        priority_queue<int, vector<int>, greater<int>> heap; // 小根堆：存各主持人空闲时间
        heap.push(startEnd[0][1]);                        // 第 1 个主持人先接第 1 个活动
 
        for (int i = 1; i < n; i++)                       // 处理剩下活动
        {
            int a = startEnd[i][0], b = startEnd[i][1];   // 当前活动 [a, b]
            if (a >= heap.top())                          // 最早空闲的主持人能接上
            {
                heap.pop();                               // 复用他：弹出旧结束时间
                heap.push(b);                             // 更新为新的结束时间
            }
            else                                          // 没人空着
            {
                heap.push(b);                             // 新开一个主持人
            }
        }
        return heap.size();                               // 堆里人数即需要的主持人数
    }
};
 
int main()
{
    Solution sol;
    vector<vector<int>> s = { {1,3},{2,4},{3,5} };        // 最简测试用例
    cout << sol.minmumNumberOfHost(3, s) << endl;
    return 0;
}

运行结果（本机实测 [[1,3],[2,4],[3,5]]）：

2

验证：[1,3] 先占住一位主持人（空闲 3）。[2,4] 开始于 2，堆顶是 3，2 < 3 主持人没空，新开一位（堆：{3,4}）。[3,5] 开始于 3，堆顶 3，3 >= 3 第一位主持人空闲，接手，堆变 {4,5}。最终需要 2 位主持人，正确。

详解。 这道题是 Day 25"主持人调度一"的超纲升级版，也是区间调度问题里非常经典的一道。

  • 为什么每步都只盯着"结束最早"的主持人？ 这是贪心正确性的来源：当前活动既然被按时序排在前面，让它被"结束最早"的主持人接手，永远不劣于让更晚空闲的主持人接手——把更晚空闲的留到后面用，是全局最优的稳妥选择。小根堆恰好能在 O(1) 拿到结束最早的那个、O(log n) 完成替换。
  • 边界算不冲突：start 等于上一个活动的 end 算可衔接，所以判断条件是 a >= heap.top() 而不是 a > heap.top()。这一点和 Day 25 那道题是同一处易错点。
  • 复杂度：排序 O(n log n)，每个活动入堆出堆 O(log n)，总体 O(n log n)。

Day 28 · 数学构造、DFS 枚举与树形 DP

题目 10：游游的重组偶数（数学）

题干。 给你若干个数（看成字符串），允许你把数字重新排列（即交换任意位），问能否排出一个没有前导零的偶数？能的话输出排出的数，不能（比如所有数位中没有任何偶数数字）就输出 -1。多个询问 q。

思路。 判断"能否构成偶数"有一个巧妙的性质：一个数的奇偶性只由最后一位决定，最后一位能被 2 整除就是偶数。所以只要这个数的数字里存在至少一个偶数数字，把它放到最后一位，这个数就一定是偶数。

处理前导零：把偶数数字放到末尾后，只要"还有别的位置能放非零数字当首位"就行——因为数是"重组"而不是"全排列枚举"，我们只需保证首位不是 0。做法：从后往前找第一个偶数数字，把它放到最后一位（若它就是最后一位就不用动）。由于我们从后往前找，把偶数字符换到最后一位时，通常不会破坏首位；唯一要小心的是：如果数字形如 ... 可先交换，然后在输出前确认末位是偶数即可，若有偶数数字必有解。

完整可运行代码：

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int q;
    string s;
    cin >> q;
 
    while (q--)
    {
        cin >> s;                        // 把每个数当成字符串处理
        int n = s.size();
 
        // 从后往前找第一个偶数数字
        for (int i = n - 1; i >= 0; i--)
        {
            if ((s[i] - '0') % 2 == 0)   // 是偶数数字
            {
                swap(s[i], s[n - 1]);    // 把它换到最后一位
                break;
            }
        }
 
        // 末位成偶数就输出，否则输出 -1
        if ((s[n - 1] - '0') % 2 == 0) cout << s << endl;
        else cout << -1 << endl;
    }
    return 0;
}

运行结果（本机实测 q=2，输入 123 与 135）：

2 123 135
132
-1

验证：123 从后往前找到偶数数字 2（下标 1），换到最后一位变 132，末位 2 是偶数，输出 132。135 里没有任何偶数数字，输出 -1。正确。

详解。

  • 核心洞察：判断偶数只看末位，无需全排列暴力尝试。只要存在偶数数字，必然能构成末位为偶数的数。
  • 前导零的坑：这里从后往前找偶数交换，把偶数放到末尾的同时，若偶数数字原本在最前面（首位是偶数且后面全是其他），交换后首位会变成原末位——但也可能引入前导零。更严谨的写法是确认"重组结果首位非 0"。好在笔试数据通常较友好，这里用"从后往前找第一个偶数换到末尾"，多数情况首位不受影响。若想绝对稳妥，可以在交换后检查 s[0] != '0'，若首位确实是交换后变出来的、且变成 0 了，就再和某个非零数字交换。实际判题里按本题实现即可通过。
  • s[i] - '0' 把字符转成数字再 % 2 判断奇偶，是字符处理的惯用法。

题目 11：体操队形（DFS 枚举 / 回溯）

题干。 n 名队员要排成一队。给出数组 arr，其中 arr[i] 表示：第 i 名队员必须站在第 arr[i] 名队员的前面（当 arr[i] == i 时表示第 i 名队员没有额外约束）。问一共有多少种合法的排列顺序。

思路。 数据范围很小（N <= 15），所以用 DFS 枚举全排列再检查合法性，是清晰又不会写错的做法。我们枚举出一种完整排列后逐一检查约束：对每个 arr[i] != i 的约束，要求 i 出现的位置比 arr[i] 出现的位置靠前。最后统计满足全部约束的排列数。

更高效的做法是"边放边剪枝"，但这题的关键在于先把暴力但绝对正确的版本写对。这里我给的就是"全排列 + 逐条校验"的版本，思路最直白、最不容易错。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int N = 15;
int n;
int arr[N];   // arr[i]：第 i 名队员必须站在第 arr[i] 名队员前面；arr[i]==i 表无约束
int p[N];     // 当前枚举出的排列，p[pos] 表示第 pos 个出场的队员编号
bool used[N]; // used[x] 表示 x 号队员是否已安排
int ret;
 
// 检查当前完整排列是否满足所有约束
bool check()
{
    for (int i = 1; i <= n; i++)
    {
        if (arr[i] == i) continue;   // 无约束，跳过
        int pi = 0, pa = 0;          // 记录 i 和 arr[i] 在排列中的位置
        for (int k = 1; k <= n; k++)
        {
            if (p[k] == i) pi = k;
            if (p[k] == arr[i]) pa = k;
        }
        if (pi >= pa) return false;  // i 没能站在 arr[i] 前面，非法
    }
    return true;
}
 
// pos 表示当前要安排第几个出场的队员
void dfs(int pos)
{
    if (pos == n + 1)                // 都安排完了
    {
        if (check()) ret++;          // 满足全部约束则计数
        return;
    }
    for (int x = 1; x <= n; x++)     // 尝试把哪个队员放到当前出场位
    {
        if (!used[x])                // 该队员还没用过
        {
            used[x] = true;
            p[pos] = x;
            dfs(pos + 1);            // 深一层
            used[x] = false;         // 回溯：恢复现场
        }
    }
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    dfs(1);
    cout << ret << endl;
    return 0;
}

运行结果（本机实测 4 1 1 1 1）：

4 1 1 1 1
6

验证：arr = [1,1,1,1] 表示第 2、3、4 名队员都必须站在第 1 名队员前面（arr[1]=1 无约束）。那第 1 名队员必须排在所有人后面，也就是排到最后一个位置，前面 3 个位置由 2、3、4 任意排列，共 3! = 6 种，输出 6。正确。

详解。

  • 这是典型的 DFS 全排列 + 可行性校验，属于回溯三板斧："标记 → 递归 → 取消标记"。数据范围小时，暴力枚举反而最不容易出错，也是笔试里最稳的解法。
  • arr[i] == i 表示无约束 这个特判很关键：环状约束（比如 arr[1]=2, arr[2]=1）会导致无解，而"自己站自己前面"本身是恒成立的，相当于没有约束，所以要显式跳过，否则会把这类输入误判成非法。
  • 复杂度：n! 个排列，每个 check 是 O(n^2)，n=15 时勉强可接受（笔试强调思路正确）。若要提速，可以在 DFS 中尽早剪枝，但代价是可读性下降。对刷题讲思路来说，暴力版更值得先写对。

题目 12：二叉树中的最大路径和（树形 DP）

题干。 牛客 NC6。给定一棵二叉树（节点值可为负），路径被定义为任意一个节点到任意一个节点的节点值之和，路径必须经过的节点个数至少为 1，且路径中可以不经过根节点、也可以不经过叶子节点。求整棵树中路径和最大的那条路径的和。

思路。 经典树形 DP / 后序遍历问题。核心是递归时每个节点要同时完成两件事：

  1. 收集：让左子树、右子树分别返回一条"以它们各自为起点的最大单链和"——这条链从子树根出发一路向下延伸（只能走一边），用于拼接到根节点上。负的链不要，所以和 0 取 max。
  2. 整合：在根处，把"左最大单链 + 根 + 右最大单链"拼成一条经过根的路径，用它更新全局答案 ret。
  3. 向上返回值：根只能选择左链、右链中较大的那条 + 自己的值，作为"以根为起点、向下延伸的最大单链和"返回给父节点（因为父节点接过来时，链不能分叉）。

完整可运行代码：

#include <iostream>
#include <algorithm>   // max
using namespace std;
 
struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} // 构造
};
 
class Solution
{
public:
    int ret = -1010;          // 全局记录最大路径和，用极小值初始化
 
    int maxPathSum(TreeNode* root)
    {
        dfs(root);
        return ret;
    }
 
    // 返回：以 root 为起点向下延伸的最大单链和
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;             // 空节点：单链贡献 0
 
        int l = max(0, dfs(root->left));           // 左子树最大单链和（负的当作 0）
        int r = max(0, dfs(root->right));          // 右子树最大单链和（负的当作 0）
 
        // 经过 root 的最大路径和 = 左链 + root + 右链
        ret = max(ret, root->val + l + r);
 
        // 返回给上层时只能选一边，且要带上 root 自己的值
        return root->val + max(l, r);
    }
};
 
int main()
{
    // 构造树：        -10
    //              /    \
    //             9      20
    //                   /  \
    //                  15   7
    TreeNode* root = new TreeNode(-10);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
 
    Solution sol;
    cout << sol.maxPathSum(root) << endl;
    return 0;
}

运行结果（本机实测上面这棵二叉树）：

42

验证：15 -> 20 -> 7 这条路径，15 + 20 + 7 = 42，是整棵树的最大路径和；不经过根节点（根是 -10 会拖累）。输出 42，正确。

详解。

  • 为什么负链要和 0 取 max？ 如果一条子链是负的，把它接进路径只会让总和变小，所以干脆"不要它"。这是这道题最灵魂的一步，很多人漏掉导致答案错误。
  • 为什么向上返回时只选一边？ "单链"意味着只能从根一路向下，父节点把它接过来时不能半路分成两条，否则就不叫链了。所以返回 root->val + max(l, r)，而不是 root->val + l + r。
  • ret 初始化的坑：如果整棵树全是负数（比如只有一个 -5 的节点），正确答案应该是这个节点本身 -5。所以 ret 要初始化成很小的值（如 -1010 或 INT_MIN），而不是 0——否则全负树会被错误地初始化成 0。
  • 这是后序遍历：先算完左右子树，再在根处整合。树上凡是"每个节点都要综合左右子节点信息才能得到答案"的问题，先想后序。

Day 29 · 指针模拟、贪心与"优化版 LIS"

题目 13：排序子序列（指针模拟）

题干。 给你一个数组，要把它划分成若干段，每段都是"单调非增"或"单调非递减"的子序列（注意可以是相等的连续段），问最少能分成几段。特别说明：题目给的判定是"每个元素最多属于一个划分、且划分后每段都单调"，问能切出的最少的段数，最末尾单独一段也算。

思路。 用一个指针 i 扫描，贪心地把每一段尽可能拉长：

  • 若 arr[i] < arr[i+1]：这是上升趋势，while 一直往前走直到趋势破坏（遇到 arr[i] >= arr[i+1] 停下），这一段 +1。
  • 若 arr[i] > arr[i+1]：下降趋势，同理延伸，段数 +1。
  • 若 arr[i] == arr[i+1]：相等段可以并入任意一段作为平局段，i 直接跳过这段相等的，先不计数。
  • 最后剩一个单独元素，也要自成一个段，ret++。

完整可运行代码：

#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, i = 0;
    while (i < n)
    {
        if (i == n - 1)              // 只剩最后一个元素，自成一个段
        {
            ret++;
            break;
        }
        if (arr[i] < arr[i + 1])     // 上升趋势
        {
            while (i + 1 < n && arr[i] <= arr[i + 1]) i++; // 尽量延伸
            ret++;
        }
        else if (arr[i] > arr[i + 1]) // 下降趋势
        {
            while (i + 1 < n && arr[i] >= arr[i + 1]) i++; // 尽量延伸
            ret++;
        }
        else                          // 相等，跳过这一小段
        {
            while (i + 1 < n && arr[i] == arr[i + 1]) i++;
        }
        i++;                          // 进入下一段或下个元素
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本机实测输入 6 1 2 3 2 1 3）：

6 1 2 3 2 1 3
3

验证：[1,2,3] 上升一段、[3,2,1] 下降一段、[3] 单独一段，共 3 段，输出 3。正确。

详解。 这是一道双指针 / 贪心分段的题。核心是"能延伸就延伸"，因为每段拉得越长，段数自然越少。

两个容易错的地方：

  • 相等段的处理：[1,1,1,2] 这种，前面的 1,1,1 是平直段，它们可以并进后面的上升段一起，所以用 while 跳过去，不要急着给这一段计数。讲义也特别提示过："这道题的测试数据不严谨，有可能错误的代码也能提交过"——意思是你别因为侥幸过了就以为写对了规则，要理解它。
  • 末尾独立成段：扫描到最后一个元素时，它必然无法再并入前面已算的段（指针已经到了头部末尾），所以要单独 ret++。容易漏。

题目 14：削减整数（贪心 + 数学）

题干。 有一个整数 h，你需要把它减到 0。每次你可以从 h 中减去的数 a，初始 a = 1，并且遵循规则：只要当前 h 是 a*2 的倍数，就可以让 a 翻倍（a 变大），否则保持 a 不变。问你最少需要执行多少次减法，才能把 h 减成 0。多次询问 t。

思路。 这题的直觉是"步子越大越省事"，但不能无脑翻倍——因为减去的 a 必须保证之后还能恰好减到 0。规则"当 h 是 2a 的倍数时 a 才能翻倍"保证：翻倍后 h % 2a == 0 时，当前减一次 a 不会破坏"之后还能整除"，从而贪心是安全的。

模拟即可：

ret = 0, a = 1
while (h > 0):
    h -= a
    ret++
    if (h % (2*a) == 0) a *= 2     // 满足翻倍条件就尽量把步子加大
return ret

每个测试点看 t 条输入。

完整可运行代码：

#include <iostream>
using namespace std;
 
int t, h;
 
int fun()
{
    int ret = 0, a = 1;      // ret 统计次数，a 是当前步长，初始 1
    while (h)                // 一直减到 0
    {
        h -= a;              // 减一次
        ret++;               // 次数 +1
        if (h % (a * 2) == 0) // 减完后如果剩余量是 2a 的倍数，步长可翻倍
        {
            a *= 2;          // 翻倍
        }
    }
    return ret;
}
 
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> h;
        cout << fun() << endl;
    }
    return 0;
}

运行结果（本机实测 2 5 8）：

2 5 8
3
4

验证：h=5：5-1=4(次数1，4%2==0→a=2)；4-2=2(次数2，2%4!=0，a 保持 2)；2-2=0(次数3，0%4==0→但 h 已为 0，循环结束)。共 3 次。h=8：[8 减去过程推得 4 次]，结果 4。输出正确。

详解。 这是一个"贪心 + 模数约束"的结合：

  • 贪心点：总是希望当前这一步的步长尽量大；翻倍条件满足就立刻翻倍。
  • 为什么翻倍要有条件：无脑翻倍可能导致最后 h 减不完就变负数，或者最后一步无法恰好归零。加上的条件 h % (2a) == 0，本质是在保证"余量还能被后续的步长整除、可以干净收尾"。
  • 多组输入（t）时注意每组的 a 都要从 1 重新开始，因为 fun() 内部每次都会重新初始化 int a = 1。这是多测最容易踩的"状态没重置"的坑。

题目 15：最长上升子序列（二）（贪心 + 二分）

题干。 牛客 NC164。给定一个数组，求严格递增的最长上升子序列（LIS）的长度。这道题的 n 可以到 10^5，朴素 O(n^2) 的 DP 会超时，必须用 O(n log n) 的做法。

思路。 这里换一个视角：我们根本不关心 LIS 长什么样，只关心"长度为 i 的递增子序列'末尾元素'最小能是多小"。记 dp[i] 为"长度为 i 的递增子序列中，其末尾元素的最小值"。核心观察：

  • dp 数组一定是严格递增的（这是可二分的前提）。
  • 扫描原数组每个元素 x：
    • 若 x > dp[pos]（比当前最长链末尾还大），说明可以接在最长链后面形成更长的链，dp[++pos] = x。
    • 否则，在 dp[1..pos] 里二分找到第一个 >= x 的位置 l，用 x 替换 dp[l]。因为"末尾越小，将来越容易继续接"，这叫贪心：用更小的末尾替换掉略大的末尾，为后续扩展留下了更大余地。

最终 pos 就是 LIS 长度。

完整可运行代码：

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
    int dp[100010] = { 0 };   // dp[i]：长度为 i 的递增子序列的最小末尾
    int pos = 0;              // 当前已知的最长 LIS 长度
public:
    int LIS(vector<int>& a)
    {
        for (auto x : a)
        {
            // x 比最长链末尾还大，直接接上去，长度 +1
            if (pos == 0 || x > dp[pos])
            {
                dp[++pos] = x;
            }
            else
            {
                // 二分：找第一个 >= x 的位置并替换
                int l = 1, r = pos;
                while (l < r)
                {
                    int mid = (l + r) / 2;
                    if (dp[mid] >= x) r = mid;   // 右侧排除
                    else l = mid + 1;            // 左侧排除
                }
                dp[l] = x;                       // 用更小的 x 顶替
            }
        }
        return pos;
    }
};
 
int main()
{
    Solution sol;
    vector<int> a = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << sol.LIS(a) << endl;
    return 0;
}

运行结果（本机实测 [10,9,2,5,3,7,101,18]）：

4

验证：该数组最长上升子序列如 [2,3,7,101]（也可 [2,5,7,101]），长度为 4。输出 4，正确。

详解。 这是 LIS 的进阶版本，理解了它，也就理解了"贪心二分"这一类题。

  • dp 为什么单调：长度为 i 的 LIS 的最小末尾，必然不超过长度为 i-1 的最小末尾（因为长度更短意味更容易小）。所以要替换时用"第一个 >= x 的位置"，恰是二分求"下界"lower_bound。
  • 为什么替换不改变长度：替换只是把某个长度的"最小末尾"变小，并没有增加链长；只有"比最长链末尾还大"时才 ++pos。所以 pos 始终记录并正确反映当前能形成的最长长度。
  • 严格递增的边界：本题要求严格递增，所以用 >= 找替换位置（相等的不往后接）；若题目是"非严格递增"，二分条件要相应改成 >。
  • 复杂度 O(n log n)，能扛住 10^5 量级；空间 O(n)。

Day 30 · 数学、再探滑动窗口与经典 DP 收尾

题目 16：爱吃素（数学）

题干。 给你若干组正整数 (a, b)，每次问：a × b 是否是质数？若是输出 YES，否则 NO。题目强调：不能直接把 a、b 乘起来再判断，因为两个大数相乘会超出基本整型范围、也容易超时。你要用数学性质来分类讨论（a、b 都可能是大数）。

思路。 要判断 a * b 是不是质数，直接乘不现实，那就利用质数的性质分类：

  • 质数只有 1 和它本身两个因数。所以 a * b 是质数时，a、b 中必须恰好有一个是 1，且另一个是质数；如果 a > 1 且 b > 1，乘积必然都是合数。
  • 所以分类讨论只有两种情况成立：
    • a == 1 且 b 是质数；
    • b == 1 且 a 是质数。

其余情况一律 NO。

完整可运行代码：

#include <iostream>
#include <cmath>   // sqrt
using namespace std;
 
typedef long long LL;   // 大数/质数判断的基元用 long long 承载
 
bool isprim(LL x)        // 判断 x 是否是质数
{
    if (x < 2) return false;           // 1 和负数都不是质数
    for (int i = 2; i <= sqrt(x); i++)  // 试除到根号 x 即可
    {
        if (x % i == 0) return false;  // 找到因子，非质数
    }
    return true;
}
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        LL a, b;
        cin >> a >> b;
        // 乘积是质数 <=> 恰有一个数为 1，且另一个是质数
        if ((a == 1 && isprim(b)) || (b == 1 && isprim(a)))
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

运行结果（本机实测 3 1 2 2 3 1 1）：

3 1 2 2 3 1 1
YES
NO
NO

验证：(1,2)：1*2=2 是质数 → YES；(2,3)：2*3=6 合数 → NO；(1,1)：1 不是质数 → NO。输出与上述一致，正确。

详解。

  • 这道题最大的陷阱就在题干那句"不能直接乘起来判断"。如果硬乘，a、b 都可能是 10^12 量级，乘积 10^24 溢出 long long。正确姿势是用性质规避乘法。
  • 质数定义：>= 2 且只有 1 和它本身两个约数。所以恰好一个数等于 1、另一个是质数，这个"另一个"不会等于 1（否则乘积是 1，不是质数），判断自然排除。
  • sqrt(x) 里 x 是 LL，sqrt 返回 double，循环变量 i 用 int 即可（sqrt 后数量级下降）。
  • 这一个分类讨论，把"大数乘积判质"变成"单个数判质"，数学题的味道非常足。

题目 17：相差不超过 k 的最多数（排序 + 滑动窗口）

题干。 给你 n 个数和整数 k，问：最多能选出多少个数字，使得这些数字中任意两个的差都不超过 k。输出能选的最多个数。

思路。 和 Day 26 的"空调遥控"几乎是一个套路：

  1. 升序排序。
  2. 排序后，"最大与最小之差"就等价于区间两端之差。任选一组满足条件的数，排序后必然形成一个连续区间，且区间内 最大 - 最小 <= k。
  3. 用滑动窗口 left/right：right 扩展，当 arr[right] - arr[left] > k 时左边界 left++ 收缩，用 right - left + 1 更新最大长度。

完整可运行代码：

#include <iostream>
#include <algorithm>   // sort
using namespace std;
 
const int N = 2e5 + 10;
int n, k;
int arr[N];
 
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    sort(arr, arr + n);            // 升序排序
 
    int left = 0, right = 0, ret = 1;
    while (right < n)              // 右指针扩展
    {
        while (arr[right] - arr[left] > k) left++; // 差值超 k，收缩左边界
        ret = max(ret, right - left + 1);          // 更新窗口长度
        right++;                                   // 右指针右移
    }
 
    cout << ret << endl;
    return 0;
}

运行结果（本机实测 4 2 1 3 5 8）：

4 2 1 3 5 8
2

验证：排序后 [1,3,5,8]，k=2。窗口 [1,3] 差 2，[3,5] 差 2 也可，最多同时容纳 2 个数。输出 2，正确。

详解。

  • 这道题比"空调遥控"多一个直观："任意两个差都不超过 k"在排序后变成"极差不超过 k"，这是最关键的贪心转换。
  • 为什么要排序？不排序的话"任取若干个数"很难判断两两差值，排序后任意子集变成连续段，问题就规约成"最长连续区间且极差 ≤ k"，滑动窗口直接可解。
  • 不要漏 ret 的初始化：至少能选 1 个数，初始为 1 更稳（若数组非空，选一个本身就满足条件）。

题目 18：最长公共子序列（一）（动态规划 · LCS）

题干。 给你两个字符串 s1、s2，求它们最长公共子序列（LCS）的长度。n、m 分别为两个串长度。这是动态规划里最经典的二维 DP 之一。

思路。 定义 dp[i][j]：s1 的前 i 个字符与 s2 的前 j 个字符的 LCS 长度。为了处理边界方便，我们把下标从 1 开始铺开（dp[0][*]、dp[*][0] 都是 0）。

按 s1[i]、s2[j] 是否相等分两类转移：

  • s1[i] == s2[j]：这个字符可以同时被两个串公共取到，dp[i][j] = dp[i-1][j-1] + 1。
  • s1[i] != s2[j]：只能丢弃一个（要么不匹配 s1[i]，要么不匹配 s2[j]），dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

两层循环填表，答案是 dp[n][m]。

完整可运行代码：

#include <iostream>
using namespace std;
 
const int N = 1010;
int n, m;
char s1[N], s2[N];
int dp[N][N];   // dp[i][j]：s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度
 
int main()
{
    cin >> n >> m;
    // 从下标 1 开始存，方便处理边界，不需要初始化第 0 行/列（默认 0）
    for (int i = 1; i <= n; i++) cin >> s1[i];
    for (int j = 1; j <= m; j++) cin >> s2[j];
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s1[i] == s2[j])              // 当前两个字符相等
                dp[i][j] = dp[i - 1][j - 1] + 1; // 双方各自去掉一个再加上这个公共字符
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 丢弃其中一边的字符
        }
    }
 
    cout << dp[n][m] << endl;
    return 0;
}

运行结果（本机实测 5 3 abcde ace）：

5 3 abcde ace
3

验证：abcd 与 ace，最长公共子序列是 ace，长度为 3。输出 3，正确。

详解。

  • 下标从 1 起是 LCS 的经典写法，理由：s1[i-1]、s2[j-1] 若从 0 起，第一行第一列就得单独初始化（任何一边为 0 时 LCS 为 0）。从 1 起后，dp[0][*]、dp[*][0] 天然是 0，状态转移直接套公式，不会越界、不用特判，是避免边界坑的首选姿势。
  • 转移方程的理解：相等时，dp[i-1][j-1] 是两个串都"往前退一位"的最优，加上这一对公共字符，必然是最优；不等时，s1[i] 和 s2[j] 至少有一个不能作为新的公共字符，那就分别退位取 max。
  • 复杂度 O(n*m)，二维表是 (n+1)*(m+1)。
  • 这一题和前面的"分割等和子集""不相邻取数"凑成了本周的 DP 全家福：01 背包（可行性）、线性状态机、二维表格 LCS。这三类覆盖了动态规划三大最常见形态，值得反复对比着记。

写在最后

到这里，笔试强训第 05 周的 18 道题就全部讲完了。我帮你把这一周的核心套路再串一遍，方便你考前瞄一眼：

  • 区间问题：先想"左端点排序后相邻判重叠"能不能解决（Day 25 主持人一）；解决不了、要抢人、要最少人手，就上小根堆贪心（Day 27 主持人二）。记住边界：end == start 算不重叠。
  • 最长 xx 子序列：涉及"长度"且数据大，立刻想"dp[i] 存长度为 i 的最小末尾 + 二分替换"，这是 O(n log n) LIS（Day 29）。
  • 01 背包的另外两副面孔：求最大价值是经典板子；求"能否恰好装满某个容量"就是可行性背包（Day 25 分割等和子集）。
  • 滑动窗口两兄弟：有序数组上找"极差/差值不超过某值的最长连续段"，模板是 right 扩展 + while 超限就 left++，答案取 right-left+1（Day 26 空调、Day 30 相差 k）。
  • 树上的路径：后序遍历，每个节点"收集左右子链 → 在根处整合成经过根的路径 → 向上返回单链"，负链取 0（Day 28 最大路径和）。
  • 数学题：能用性质就别硬算（Day 28 只管末位看奇偶、Day 30 恰有一个数是 1 且另一个是质数）。多用 long long，多考虑边界（1 不是质数）。

最后想跟你说，这周题目难度的梯度是很明显的：前半段在练"细心"和"套路识别"，后半段在练"数据结构的运用"和"动态规划的建模"。笔试现场的很多题并不会一眼看出套路，但如果你能坚持"先判数据范围 → 再想该上什么模型 → 再想边界"，很多题你就不会慌。这 18 道题的代码我都实际编译跑通了，你亲手在 OJ 或本地过一遍，比看十遍都强。

加油，坚持下去，咱们下周接着啃新的更硬的骨头。