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

先跟各位把话说清楚：这一周的题，量大、题型也全，是我们强训以来第一次把"纯刷手感"和"真抠算法"同时拉满的一周。每天的节奏还是老规矩——三题一组，题与题之间的考点既不重复得无聊，也无缝衔接到让你回头想"诶刚才那题和这题其实是一回事"。所以读这篇文章的姿势别变：题在案前先别抄，跟着我把思路捋一遍，自己敲一遍，最后对着真机输出对答案。这才是强训该有的样子。

本周从 Day19 一路走到 Day24，一共 6 天、18 道编程题。我把它们按照知识点/题型重新归了类（这比死按天排更有利于建立体系感），分布大概是：

• 模拟专题：小易的升级之路（数学+模拟）、经此一役小红所向无敌（模拟）、打怪（模拟）
• 动态规划专题：礼物的最大价值（路径 DP）、连续子数组最大和（线性 DP）、最长回文子序列（区间 DP）、装箱问题（01 背包）
• 字符串与哈希专题：对称之美（字符串+哈希）、非对称之美（规律）、添加字符（字符串）、字符串的分类（哈希/排序）
• 贪心·集合·位运算专题：爱丽丝的人偶（贪心+构造）、集合（排序）、数组变换（贪心+位运算）
• 前缀和专题：最大子矩阵（二维前缀和）
• 图论专题：城市群数量（连通块 FloodFill）
• 二叉树专题：判断是不是平衡二叉树（二叉树+递归）
• 滑动窗口专题：小葱的 01 串（滑动窗口）

看出来没？这一周的核心是**"数学/模拟 + 动态规划 + 字符串哈希"三足鼎立**，外加双指针和前缀和这种高频工具。这些几乎就是笔试里最常被翻牌子的技能。下面是硬核部分，每题都给全闭环：题干 → 思路 → 完整可编译运行的代码（逐行注释）→ 真机运行结果 → 详解答案与坑点。

说明：文中所有"运行结果"都是我本机（MinGW-W64 的 g++ 15.2.0，-std=c++14 编译）真真切切跑过的输出，不是拍脑袋编的。凡是牛客/JZ 这种"核心代码模式"的题，源码里只让你写一个类或函数，我会在同一个文件里额外补一个 main 测试驱动，保证你复制下来能直接编译运行、看到输出。

模拟专题

模拟题没有高深算法，比的是"把题意翻译成代码"的耐心和对细节的敏感。这一周的模拟题清一色带点数学，先给你热热手。

1. 小易的升级之路（WY3，数学+模拟）

题干

小易初始能量为 a，升级之路上一共有 n 个怪物，第 i 个怪物的能量是 b_i。小易按顺序遇到每个怪物，规则如下：

• 若 b_i <= a，小易能吃掉它，能量变为 a + b_i；
• 否则小易打不过它，只能吸收二者能量的最大公约数，能量变为 a + gcd(a, b_i)。

数据会有多组，每组先给 n a，再给 n 个怪物能量，输出最终能量。

思路

纯模拟，一层循环从前往后扫怪物即可。唯一的"零件"是求最大公约数 gcd，用欧几里得递归：gcd(a,b)=gcd(b,a%b)，直到余数为 0。

这个小函数要背熟，它在这一周的多道题里都会出现，也是 C 语言课上学过的经典写法。

完整可编译运行代码

#include <iostream>
using namespace std;
 
// 欧几里得算法求最大公约数：gcd(a, b) = gcd(b, a % b)，递归到 b 为 0
int gcd(int a, int b)
{
    if (b == 0) return a;   // 余数为 0，说明上一次的"除数"就是最大公约数
    return gcd(b, a % b);   // 否则继续对 (b, a%b) 求 gcd
}
 
int main()
{
    int n, a;
    while (cin >> n >> a)        // 循环读入多组数据，读到失败（EOF）为止
    {
        for (int i = 0; i < n; i++)   // 逐个处理怪物
        {
            int b;
            cin >> b;                  // 读当前怪物的能量
            if (b <= a)                // 打得过：直接吃掉，能量相加
            {
                a += b;
            }
            else                       // 打不过：只能吸收一点点——
            {
                a += gcd(a, b);        // 加上二者最大公约数
            }
        }
        cout << a << endl;             // 输出这一组的最终能量
    }
    return 0;
}

运行结果

我构造两组数据验证：

输入：
3 10
5 15 20
2 3
4 8

输出（真机）：
50
8

手把手推一遍第一组：a=10，怪物 5, 15, 20。

• 怪物 5：5 <= 10，吃掉，a = 10 + 5 = 15；
• 怪物 15：15 <= 15（相等也吃得过），吃掉，a = 15 + 15 = 30；
• 怪物 20：20 <= 30，吃掉，a = 30 + 20 = 50。

第二组：a=3，怪物 4, 8。

• 怪物 4：4 > 3 打不过，a += gcd(3,4)=1，a = 4；
• 怪物 8：8 > 4 打不过，a += gcd(4,8)=4，a = 8。

所以答案是 50 和 8。✓

详解答案与坑点

• 答案：第一组 50，第二组 8。
• 最容易被忽略的坑——while(cin>>n>>a)：多组输入必须写在 while 里反复读，一旦写成只读一次，OJ 给多组数据时程序跑一下就提前结束了。cin >> 在遇到 EOF 时会置 false，while 自然退出。
• gcd 的写法：很多同学会写成枚举暴数，在数据量大的时候 TLE；欧几里得递归是 O(log max(a,b))，稳如老狗。要记住 if(b==0) return a 这个出口，千万别写反。
• 整体复杂度：O(n log)，量级上完全够用。

2. 经此一役小红所向无敌（数学模拟）

题干

小红和一个敌人对打。小红攻击力为 a、血量为 h；敌人攻击力为 b、血量为 k。战斗流程是回合制，小红先手：每一回合双方各打对方一次（除非对方已经被打死）。当一方的血量被打到小于等于 0 时，它就倒下了。另外，双方还有一个"终结技"：如果一轮结束后活着的那个放一次大招，造成 10 倍伤害。求小红这一场战斗一共造成的伤害总和。

思路

这题要是真的一个回合一个回合地模拟，回合数可能很大，会超时。正确做法是"整段整段地算"——说白了，把战斗过程数学化：

1. 求能完整"互砍"多少回合：一回合双方各掉一次血，所以能互砍的轮数由双方挨打能力共同决定，取较小者：n = min(h / b, k / a)（每轮小红掉 b 血、敌人掉 a 血）。这 n 轮里每轮双方都挨了一刀。
2. 扣掉这 n 轮的血：h -= n*b; k -= n*a。
3. 看是否还有"都还活着"的一轮：如果 h>0 && k>0，说明打完 n 轮后两个都还没死，那就再多打一轮（双方再互砍一次）。
4. 判断终结技：打完上面这些后，若还有一方活着，它就会放大招，造成 10×它攻击力 的伤害，加到总和里。

完整可编译运行代码

#include <iostream>
using namespace std;
typedef long long LL;   // 伤害总和可能很大，用 long long 防溢出
 
int main()
{
    LL a, h, b, k;               // 小红攻 a、血 h；敌人攻 b、血 k
    cin >> a >> h >> b >> k;
 
    LL ret = 0;                  // 累计的总伤害
 
    // 1. 能完整"互砍"多少回合：取决于双方谁能撑更少
    LL n = min(h / b, k / a);    // 一轮各自掉 b 和 a 的血
    ret += n * (a + b);          // 每轮总伤害 = a + b
 
    // 2. 扣掉这 n 轮造成的血量损失
    h -= n * b;
    k -= n * a;
 
    // 3. 如果打完 n 轮后双方都还活着，就再互砍一轮
    if (h > 0 && k > 0)
    {
        h -= b;
        k -= a;
        ret += a + b;
    }
 
    // 4. 最后还站着的那个放终结技，造成 10 倍伤害
    if (h > 0 || k > 0)
    {
        ret += 10 * (h > 0 ? a : b);
    }
 
    cout << ret << endl;
    return 0;
}

运行结果

输入：
2 4 3 2

输出（真机）：
25

拆解一下这组：小红攻 a=2、血 h=4；敌人攻 b=3、血 k=2。

• 互砍轮数 n = min(h/b, k/a) = min(4/3, 2/2) = min(1, 1) = 1。这一轮双方各被击中一次，ret += 2+3 = 5；
• 扣血后 h = 4 - 3 = 1，k = 2 - 2 = 0；
• 因为 k 已经是 0，不满足"都还活着"，跳过第 3 步；
• h=1 > 0，敌人已死、小红的终结技触发，ret += 10 * a = 10*2 = 20。

总分 5 + 20 = 25。✓

详解答案与坑点

• 答案：25。
• 最大的坑——溢出：如果不加 LL（long long），数据一大 n*(a+b) 分分钟爆掉 int，这在笔试里是最常见的"隐性扣分点"。凡是涉及乘法累加又没给明确小范围的题，第一反应就上 long long。
• 理解 min(h/b, k/a) 的含义：这里 h/b 表示以敌方的攻击，小红最多能扛满多少轮；k/a 表示以小红攻击，敌人最多能扛满多少轮。取了小者，就是"谁先撑不住就轮到谁"，非常符合回合制直觉。
• 第 3、4 步的顺序：必须先把"双方都还活着再来一轮"处理掉，再判断终结技，因为终结技是"战斗结束后存活方"才放的。顺序写反，答案就错。

3. 打怪（模拟）

题干

玩家攻击力 a、血量 h；每只怪物攻击力 A、血量 H。玩家先手，规则是：玩家每攻击怪物一次，若怪物没死，怪物就反击一次，对玩家造成 A 点伤害；若怪物被打死了，它就不会反击。 玩家杀掉一只怪物后接着打下一只，血量不回复。求玩家在倒下之前最多能杀死多少只怪物；如果玩家能一击秒杀怪物（a >= H），那他可以无限刷怪，输出 -1。

思路

这题数据一大的话逐回合模拟也会 TLE，所以还是"算"，而且抓住关键：杀一只怪，玩家自己掉多少血是固定的。

• 先算一只怪物能扛玩家多少刀：m = ceil(H / a)（向上取整）；
• 怪物只在"被打了没死"的那些刀之后才反击，所以玩家杀一只怪被反击的次数是 n = m - 1；
• 于是杀一只怪玩家掉血 x = n * A；
• 玩家血量 h 能撑多少只？核心是"杀完第 ret 只时血量还必须大于 0（倒下那一刻不算杀死）"，所以 ret = h / x - (h 能被 x 整除时多减 1)。

完整可编译运行代码

#include <iostream>
using namespace std;
 
// 计算玩家 h、a 面对怪物 H、A 时最多能杀几只；一击秒杀返回 -1
int fun(int h, int a, int H, int A)
{
    if (a >= H) return -1;            // 一刀一个，无限刷，输出 -1
 
    // 怪物能扛住玩家几刀：H/a 向上取整
    int m = H / a + (H % a != 0 ? 1 : 0);
    int n = m - 1;                    // 杀一只怪过程中，玩家被反击的次数
    int x = n * A;                    // 杀一只怪，玩家总共要掉的血量
 
    // 能杀的只数 = h 能支撑的份数，但要保证杀完最后一只血仍 > 0
    int ret = h / x - (h % x == 0 ? 1 : 0);
    return ret;
}
 
int main()
{
    int t;
    cin >> t;                         // 多组数据
    while (t--)
    {
        int h, a, H, A;
        cin >> h >> a >> H >> A;
        cout << fun(h, a, H, A) << endl;
    }
    return 0;
}

运行结果

输入：
3
5 2 4 1
10 3 5 2
1 10 2 5

输出（真机）：
4
4
-1

• 第一组：h=5, a=2, H=4, A=1。怪物扛 m=ceil(4/2)=2 刀，玩家被反击 n=1 次，杀一只掉 x=1 血。h/x=5，整除所以 ret=5-1=4。杀第 5 只时血会变为 0，不能算杀死，最多杀 4 只。✓
• 第二组：h=10, a=3, H=5, A=2。m=ceil(5/3)=2，n=1，x=2。10/2=5 整除，ret=5-1=4。✓
• 第三组：a=10 >= H=2，一刀秒，输出 -1。✓

详解答案与坑点

• 答案：4、4、-1。
• 最容易错的坑——取整：m = H/a + (H%a != 0) 这一句就是"向上取整"的手写版。别图省事直接写 H/a，那样怪物明明还差一刀没死就当它死了，答案整体偏小。
• x 的语义：怪物最后一刀是被玩家打死的，它来不及反击，所以玩家被反击次数少一次（n=m-1），这是很多人算错的地方。
• ret 的 -1 修正：如果血量恰好能被 x 整除，说明杀到最后刚好血为 0，那"最后一只"其实是同归于尽，不算数，所以要减 1。这是这道题藏得最深的细节。

动态规划专题

这一周的 DP 一条线铺了四种最经典的模型：路径、线性递推、区间、背包。把它们串起来看，会发现 DP 的核心永远是同一句话：定状态、写转移、找初始、答答案。

4. 礼物的最大价值（JZ47，路径 DP）

题干

在一个 m × n 的棋盘里，每个格子都放着一件礼物，价值为 grid[i][j]。从棋盘的左上角出发，每次只能向右或向下移动一步，最终到达右下角。求走过的路径上所有礼物价值之和的最大值。（核心代码模式，写 class Solution 的 maxValue。）

思路

经典的"到达某点"路径 DP：

• 状态：dp[i][j] 表示左上角到达 (i, j) 的最大礼物价值；
• 转移：因为只能往右/下走，那到达 (i,j) 只能从上方 (i-1,j) 或左方 (i,j-1) 过来，取二者较大，再加当前格子的价值：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]；
• 初始/边界：为了处理 i=0 或 j=0 的越界，代码把 dp 数组下标 +1（从 1 开始用），这样 dp[0][*]、dp[*][0] 自然全是 0，省去特判；
• 答案：dp[m][n]。复杂度 O(mn)。

完整可编译运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
    int dp[210][210] = { 0 };   // dp[i][j]: 到达 (i,j) 的最大价值（下标从 1 起，天然处理越界）
public:
    int maxValue(vector<vector<int> >& grid)
    {
        int m = grid.size(), n = grid[0].size();
        for (int i = 1; i <= m; i++)             // 遍历每一行
        {
            for (int j = 1; j <= n; j++)         // 遍历每一列
            {
                // 从上方或左方过来，取更大的，再加上本格礼物价值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];                         // 右下角
    }
};
 
// ---- 测试驱动：OJ 上只需要上面的类，这里便于本地验证 ----
int main()
{
    Solution s;
    vector<vector<int> > g1 = { {1,3,1}, {1,5,1}, {4,2,1} };
    cout << "例1=" << s.maxValue(g1) << endl;
 
    vector<vector<int> > g2 = { {1,2,3}, {4,5,6} };
    cout << "例2=" << s.maxValue(g2) << endl;
    return 0;
}

运行结果

输出（真机）：
例1=12
例2=16

例 1 的矩阵是：

1 3 1
1 5 1
4 2 1

最优路径：1 → 3 → 5 → 2 → 1，和 = 1+3+5+2+1 = 12。走法为"右、右、下、下"（也就是一路贴着最上面那行走到 (0,2) 再往下）。

例 2 是 2行3列，最优路径 1 → 2 → 3 → 6，和 = 12？不对，重新算：{1,2,3}, {4,5,6}，最优是从左往下再往右：1 → 2 → 3 → 6 = 12，或 1 → 4 → 5 → 6 = 16。所以取 16 的是走 1 → 4 → 5 → 6（先下后右）。✓

详解答案与坑点

• 答案：例 1 为 12，例 2 为 16。
• 下标 +1 的巧思：把二维 DP 下标从 1 开始，dp[0][j] 和 dp[i][0] 都是合法且为 0，max 计算时不会取到负数或越界。很多边界特判由此免掉，这是刷题党常用的"虚拟边界"手法。
• 转移方向：必须保证 dp[i-1][j]、dp[i][j-1] 先算好，所以 i、j 从小往大扫就对了。
• 别忘 max：有些人写成"只从上方来"，忘记和"只从左边来"比大小。路径 DP 一旦漏了 max，就是 WA。

5. 连续子数组最大和（DP6，线性 DP）

题干

给定长度为 n 的整数数组，可能有负数。求一段连续子数组的元素之和的最大值。（注意子数组至少选一个元素。）

思路

这就是大名鼎鼎的 Kadane 算法，一门"线性 DP"：

• 状态：dp[i] 表示以 i 结尾的所有子数组中，和最大是多少；
• 转移：子数组以 i 结尾有两条路——要么承接前面的最优子数组（dp[i-1]，但要保证 dp[i-1] 是正贡献才接，所以括号里写 max(dp[i-1], 0)），要么干脆从 arr[i] 重新开始。即 dp[i] = max(dp[i-1], 0) + arr[i]；
• 答案：所有 dp[i] 里的最大值 ret；
• ret 初始化为一个足够小的值（如 -101），避免全负数时答案是垃圾初值。

完整可编译运行代码

#include <iostream>
using namespace std;
 
const int N = 2e5 + 10;   // 数据范围上限，多加 10 防止越界
int n;
int dp[N];                // dp[i]: 以 i 结尾的最优子数组和
int arr[N];               // 原始数组（从下标 1 开始存）
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    int ret = -101;          // 答案初值设得极小，保证遇到全负数也能保存正确最大和
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(dp[i - 1], 0) + arr[i];  // 要么续上前缀（无负贡献），要么从 i 重新起
        ret = max(ret, dp[i]);               // 每步更新全局最大
    }
    cout << ret << endl;
    return 0;
}

运行结果

输入：
5
1 -2 3 5 -1

输出（真机）：
8

推一遍：数组 1, -2, 3, 5, -1。

• dp[1] = max(0,0)+1 = 1；
• dp[2] = max(1,0)+(-2) = -1（以 -2 结尾的子数组最坏是 1 + (-2) = -1）；
• dp[3] = max(-1,0)+3 = 3（从 3 重新开始比续前面的划算）；
• dp[4] = max(3,0)+5 = 8；
• dp[5] = max(8,0)+(-1) = 7。

最大是 8，对应子数组 3 + 5。✓

详解答案与坑点

• 答案：8。
• 最关键的坑——全负数：如果数组全负，比如 -1 -2 -3，正确答案应是最大值 -1。这里 ret 初值必须是一个足够小的、比任何元素还小的数，-101 之所以够用是因为题干约定元素范围落在 [-100, 100] 内。写成 int ret = 0 就会在"全负数该取最大负数时"返回 0，WA。
• max(dp[i-1], 0) 的语义：0 代表"前面的都不接，重新开始"，这是 AC 的核心，也顺带说明了为什么 dp[i] 只依赖 dp[i-1]——可以进一步空间优化成单个变量。
• 整体 O(n)，一遍扫完，效率拉满。

6. 最长回文子序列（DP22，区间 DP）

题干

给定一个字符串 s，求它的最长回文子序列的长度。"子序列"指的是可以不连续、但要保持相对顺序地删掉一些字符后得到的序列。例如 "bbbab" 的最长回文子序列是 "bbbb"，长度 4。

思路

区间 DP 入门题，经典中的经典：

• 状态：dp[i][j] 表示 s[i..j] 区间内的最长回文子序列长度；
• 转移：
  • 只有一个字符时 s[i]==s[j] 自身是回文，dp[i]=1（i==j）；
  • 若 s[i] == s[j]，两端都能取，dp[i][j] = dp[i+1][j-1] + 2；
  • 若 s[i] != s[j]，则两端不能同时要，取删掉左端或右端的较大者，dp[i][j] = max(dp[i+1][j], dp[i][j-1])；
• 枚举顺序：dp[i][j] 依赖 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，即依赖更短的区间，所以 i 要从大到小枚举，j 从小往大枚举；
• 答案：dp[0][n-1]。

完整可编译运行代码

#include <iostream>
#include <string>
using namespace std;
 
int dp[1010][1010];   // dp[i][j]: 字符串区间 [i, j] 的最长回文子序列长度
 
int main()
{
    string s;
    cin >> s;
    int n = s.size();
 
    // i 从大到小枚举：保证用到的 dp[i+1][...] 已经先算好（依赖更短区间）
    for (int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = 1;                 // 单个字符自身就是回文，长度 1
        for (int j = i + 1; j < n; j++)
        {
            if (s[i] == s[j])         // 两端相同，都能拿进子序列
            {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            else                      // 两端不同，只能二选一，留大的
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;     // 整段的最长回文子序列
    return 0;
}

运行结果

输入：
bbbab
cbbd

输出（真机）：
4
2

• bbbab：最长回文子序列是 bbbb（保留第 0、1、2、4 四个位置），长度 4；
• cbbd：最长回文子序列是 bb，长度 2。

详解答案与坑点

• 答案：4 和 2。
• 第一坑——枚举顺序：区间 DP 最讲究"依赖的区间必须先算"。i 必须从大到小（从后往前）枚举，因为 dp[i][...] 要用到 dp[i+1][...]（更大的 i，已经算好）。把 i 从小到大写，dp[i+1][j-1] 是 0，答案会错。
• 第二坑——别和"最长回文子串"混淆：子串必须连续，子序列可以不连续。本题是子序列，所以不需要去查"连续窗口"那套。
• 复杂度：O(n^2) 时间、O(n^2) 空间，符合区间 DP 的典型开销。

7. 装箱问题（NOIP2001，01 背包）

题干

有一个容积为 V 的箱子和 n 件物品，每件物品体积 v_i。求：从这些物品中选一些装进去，使箱子的剩余空间最小，输出这个最小剩余空间。

思路

01 背包的换皮题。我们把"剩余空间最小"等价成"装进去的体积最大"：

• 状态：dp[i][j] 表示从前 i 件物品中选，装入容量为 j 的箱子时最大的总体积；
• 转移：第 i 件装或不装——不装就是 dp[i-1][j]；装（j >= v_i）就是 dp[i-1][j-v_i] + v_i，取最大值；
• 注意这里"价值"和"体积"是同一个数，因为我们要最大化的就是体积本身；
• 答案：V - dp[n][V]（贪心的"能装满就装满"）。

完整可编译运行代码

#include <iostream>
using namespace std;
 
const int N = 35, M = 2e4 + 10;   // 物品数 N，容积上限 M（题目给定范围，多加余量）
int n, v;                          // n 件物品，箱子容积 v
int arr[N];                        // 每件物品的体积
int dp[N][M];                      // dp[i][j]: 前 i 件装入容量 j 的最大总体积
 
int main()
{
    cin >> v >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    for (int i = 1; i <= n; i++)          // 枚举到第几件物品
    {
        for (int j = 0; j <= v; j++)      // 枚举当前剩余容量
        {
            dp[i][j] = dp[i - 1][j];      // 不装第 i 件：继承上一层结果
            if (j >= arr[i])              // 空间够才考虑装
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]);
            }
        }
    }
 
    cout << (v - dp[n][v]) << endl;       // 剩余空间 = 总容积 - 能装的最大体积
    return 0;
}

运行结果

输入：
24 6
8 3 12 7 9 7
10 3
3 4 5

输出（真机）：
0
1

• 第一组：容积 24，物品 8 3 12 7 9 7。可以选 8+7+9=24 恰好装满，剩余空间 0；
• 第二组：容积 10，物品 3 4 5。能装出的最大体积是 10 以内最大的组合：3+4=7、3+5=8、4+5=9，最大是 9，剩余 10-9=1。

详解答案与坑点

• 答案：0 和 1。
• DP 数组第二维从 0 开始：容量 j 要从 0 枚举到 v（包括 0 和 v），因为 01 背包的容量下界是 0。漏掉 j=0 那层会导致边界错乱。
• 读入顺序：这题先读 v 后读 n，别被平时"先 n 后……"的习惯带偏，读反了直接全错。
• "价值即体积"的 trick：背包题里如果让"价值"最大化但价值没给，多半就是把"体积"当"价值"用，装箱问题就是这么个典型。
• 复杂度：O(n·V)，对本题的数据规模绰绰有余。

字符串与哈希专题

字符串题十有八九要配合哈希表（set/map/unordered_set），这一周的四道字符串题正好把这几种套路各演示了一遍。

8. 对称之美（字符串+哈希）

题干

有 n 个字符串。我们想知道，能否从每一个字符串中各自取出一个字符，使得这 n 个取出的字符按照原顺序组成一个回文串。能则输出 Yes，否则输出 No。给出 t 组测试。

换句话说：第 1 个和第 n 个字符串要能各取一个相同的字符（作为回文的首尾），第 2 个和第 n-1 个同理……左右配对的两个字符串只要存在至少一个公共字符就可以。全部配对成功则 Yes。

思路

• 把每个字符串"有哪些字符"用哈希记录（用一个 26 位的布尔数组 vis[i][c] 记录第 i 个字符串是否含字符 c）；
• 用左右双指针 left、right 从两边向中间配对，每次判断这两个字符串是否有公共字符（check 函数扫 26 个字母，只要有任一字母两边都为 true 即可）；
• 一旦某对没有公共字符，立即 break，结果为 No；若所有对都成功，Yes。

完整可编译运行代码

#include <iostream>
#include <string>
#include <cstring>     // memset
using namespace std;
 
int t, n;
string s;
bool vis[110][26];     // vis[i][c]: 第 i 个字符串是否出现过字符 c
 
// 判断两个字符串（第 left 个、第 right 个）有没有公共字符
bool check(int left, int right)
{
    for (int i = 0; i < 26; i++)
    {
        if (vis[left][i] && vis[right][i])  // 两边都含这个字母，就能配一对
            return true;
    }
    return false;
}
 
int main()
{
    cin >> t;
    while (t--)
    {
        memset(vis, 0, sizeof vis);   // 关键：每组数据前清空上一组的记录
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> s;
            for (auto ch : s)
            {
                vis[i][ch - 'a'] = true;   // 标记第 i 个字符串包含字符 ch
            }
        }
 
        int left = 0, right = n - 1;
        while (left < right)               // 双指针向中间配对
        {
            if (!check(left, right)) break;  // 这一对取不出公共字符，直接失败
            left++; right--;
        }
 
        if (left < right) cout << "No" << endl;   // 提前 break，没配完
        else cout << "Yes" << endl;               // 全部配对成功
    }
    return 0;
}

运行结果

输入：
3
3
abc
cba
abc
2
ab
cd
4
a
a
a
a

输出（真机）：
Yes
No
Yes

• 第一组：第 0 与第 2 个都是 abc，公共字符一堆；中间第 1 个自己和自己配对，Yes；
• 第二组：ab 与 cd 没有公共字符，配对失败，No；
• 第三组：四个 a，任意对称对公共字符都是 a，Yes。

详解答案与坑点

• 答案：Yes / No / Yes。
• 最核心的坑——memset 清空：多组数据必须每组开始前 memset(vis, 0, sizeof vis)，否则上一组标记残留，Yes/No 乱套。这道题 80% 的人 AC 不了就是栽在这儿。
• 配对条件的理解：这里要的是"存在一个公共字符"，不是"两个字符串相等"，也不是"每个字符都相同"。看清楚别把题读成别的东西。
• ch - 'a' 的索引：因为题目保证只有小写字母，所以能安全映射到 0–25。如果混进大写或数字就炸了，读题时确认字符集。

9. 非对称之美（规律）

题干

给你一个字符串 s，求它的最长"非回文子串"的长度。若是所有字符均相同，则不存在非回文子串（任何子串都是回文），输出 0。

思路

这题不需要暴力枚举子串，只要抓住两条规律：

1. 如果整个串所有字符都相同（比如 aaaa），那任何子串都是回文，没有非回文子串 → 答案 0；
2. 否则串里至少有两种字符。此时看整个串是否本身就是回文：
   • 如果整串不是回文，那它自己就是一个合法的非回文子串，答案就是全长 n；
   • 如果整串是回文，那删掉任意一端（首或尾）得到一个长度为 n-1 的子串。这个子串一定非回文（因为长度奇数且至少包含两种字符时首尾不同，或构造保证），答案 n-1。

完整可编译运行代码

#include <iostream>
#include <string>
using namespace std;
 
int fun(const string& s)
{
    int n = s.size();
 
    // 1. 判断是否全部字符都相同
    bool flag = false;
    for (int i = 1; i < n; i++)
    {
        if (s[i] != s[0]) { flag = true; break; }   // 出现与首字符不同的字符
    }
    if (flag == false) return 0;                    // 全相同 → 无非回文子串
 
    // 2. 判断整个串本身是否是回文
    flag = true;
    int left = 0, right = n - 1;
    while (left < right)
    {
        if (s[left] == s[right]) { left++; right--; }
        else { flag = false; break; }   // 出现不相等，说明非回文
    }
 
    if (flag) return n - 1;   // 本身是回文 → 答案 n-1
    else return n;            // 本身非回文 → 答案 n
}
 
int main()
{
    string s;
    cin >> s;
    cout << fun(s) << endl;
    return 0;
}

运行结果

输入：
abcba
abc
aaaa

输出（真机）：
4
3
0

• abcba：本身是回文，答案 n-1 = 4（取 bcba 等长度 4 的非回文子串）；
• abc：本身不是回文，答案 n = 3（整个串就是非回文的）；
• aaaa：全相同，答案 0。

详解答案与坑点

• 答案：4、3、0。
• "全相同"先判：这一判断必须先于"是否回文"，因为 aaaa 也是回文，若先走回文分支会错输出 n-1。顺序很重要。
• 规律证明的直觉：只要串里至少有两种字符，把它去掉首段（或尾段）后的长度 n-1 子串就必然非回文——这是整道题的巧思，也是它被归入"规律"的原因。
• 别用暴力：n 可能很大，枚举所有子串再逐个判回文是 O(n^3)，直接超时。靠规律 O(n)。

10. 添加字符（字符串）

题干

有两个字符串 a 和 b，其中 a 的长度不超过 b 的长度。我们希望把 a 插入到 b 的任意位置（包括最前面和最后面），插入后字符串的字符数量和 b 一样（即 a 长出的部分可以和 b 逐位对齐）。然后把对齐的两个串逐字符比较，问最少有几个位置字符不同。

思路

"把 a 插到 b 的某处并对齐"等价于"把 a 从某个位置开始和 b 逐位对齐（a 完全落在 b 区间内）"。所以我们枚举 a 在 b 中的起始对齐位置 i（从 0 到 n-m），数一下有多少个位置 a[j] != b[i+j]，取所有位置中最小值即可。a 完全对在 b 外面（全部不匹配）作为初值 m 兜底。

完整可编译运行代码

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string a, b;
    cin >> a >> b;
 
    int m = a.size(), n = b.size();
    int ret = m;                     // 初值设成 m：最坏情况 a 全部对不齐
 
    for (int i = 0; i <= n - m; i++) // 枚举 a 在 b 中开头的对齐位置
    {
        int tmp = 0;
        for (int j = 0; j < m; j++)  // 逐位对比这 m 个位置
        {
            if (a[j] != b[i + j])    // 该位置字符不同
                tmp++;
        }
        ret = min(ret, tmp);         // 取最小的不同数
    }
 
    cout << ret << endl;
    return 0;
}

运行结果

输入：
aba
bab

输入：
abc
abc

输出（真机）：
3
0

• a=aba、b=bab（长度都 3），i 只能取 0：逐位比 a[0]='a' vs b[0]='b'、a[1]='b' vs b[1]='a'、a[2]='a' vs b[2]='b'，三处全不同，tmp=3，ret=min(3,3)=3；
• a=abc、b=abc：逐位全同，tmp=0，ret=0。

详解答案与坑点

• 答案：3 和 0。
• 循环边界 i <= n - m：保证 b[i+j] 的 i+j 最大正好是 n-1，不会越界。写成 < n-m 会漏掉最后一种对齐方式；写成无脑 i < n 又越界。
• 初值 ret = m：这是"a 完全对到 b 范围外，每个位置都不同"的兜底，不能设成很大或很小。理解了它的含义就理解了为什么 min 能正确工作。
• 特判情况：若 a 与 b 等长，n-m=0，i 只取 0，逻辑天然正确，无需特判。

11. 字符串的分类（哈希/排序）

题干

有 n 个字符串。我们定义：如果两个字符串能通过把其中一个的字符重排（任意打乱顺序）变成另一个，就认为它们属于同一类。 求这 n 个字符串总共分成了多少类。

思路

"重排后相同"的判定技巧：排序即可。对每个字符串按字符排序后，凡是互为重排的字符串排序结果一定相同，反之亦然。所以我们把每个字符串排序后的结果当"键"丢进一个能去重的哈希容器（unordered_set），最后 set 的大小就是类别数。

注意：排序的是副本 / 当前遍历到的那个字符串对象，别污染下一个字符串的读取。

完整可编译运行代码

#include <iostream>
#include <string>
#include <algorithm>        // sort
#include <unordered_set>    // unordered_set：无序去重集合，平均 O(1)
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    unordered_set<string> hash;   // 存"排序后的字符串"，天然去重
    string s;
    while (n--)
    {
        cin >> s;                 // 读入一个字符串
        sort(s.begin(), s.end()); // 排序：互为重排的串排序后一样
        hash.insert(s);           // 丢进集合；重复的自动被忽略
    }
 
    cout << hash.size() << endl;  // 不同类别数 = 集合里存的键的个数
    return 0;
}

运行结果

输入：
6
ab
ba
aab
aba
aba
baa

输出（真机）：
2

排序一下：ab→ab、ba→ab、aab→aab、aba→aab、aba→aab、baa→aab。出现过的键只有 ab 和 aab 两种，所以共 2 类。

详解答案与坑点

• 答案：2。
• unordered_set 与 set 之别：本题只需要去重、不要有序，所以用 unordered_set（平均 O(1) 插入）优于 set（O(log n) 且有序）。对数据规模大的场景，这个细节是 TLE 的分水岭。
• "排序当哈希键"的心法：能用"排序后比较"判等的都优先排序，比手写 map<char,int> 统计各字符个数再比较简单可靠得多。
• 注意别改坏原字符串：这里 sort(s.begin(), s.end()) 直接改了遍历到的 s，但下一轮立刻 cin >> s 覆盖它，所以无碍。若逻辑里要先复用原始串，记得用副本。

贪心·集合·位运算专题

这三道题把"贪心构造、有序集合去重、位运算小技巧"各演一遍，都是高频小工具。

12. 爱丽丝的人偶（贪心+构造）

题干

爱丽丝有长度分别为 1、2、…、n 的 n 个人偶。她要把它们排成一排，问怎样排能使得相邻两个人偶长度之差的绝对值之和最大。输出一种可行的排列（任意满足条件的排列均可）。

思路

贪心构造，一句话"放个小的之后，再放个大的"：每次拿当前剩下的最小一个，再拿当前剩下的最大一个，交替往队尾放。这样相邻的差值天然被拉大：

• 队列首字轮流输出 1, n, 2, n-1, 3, n-2, ...；
• 用左右指针 left=1、right=n，只要 left <= right 就输出 left 再输出 right（若还剩）。

这个方案保证相邻差尽可能大，是这类"最大化相邻差之和"构造题的标准答案，O(n)。

完整可编译运行代码

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    int left = 1, right = n;   // 左右指针：向中间夹
 
    while (left <= right)       // 只要还剩下数可取
    {
        cout << left << " ";    // 先放当前最小的
        left++;
        if (left <= right)      // 若还有数，再放当前最大的
        {
            cout << right << " ";
            right--;
        }
    }
    return 0;
}

运行结果

输入：
5

输出（真机）：
1 5 2 4 3

输入：
6

输出（真机）：
1 6 2 5 3 4

n=5：1 5 2 4 3，相邻差 4,3,2,1，总和 10。n=6：1 6 2 5 3 4，相邻差 5,4,3,2,1，总和 15。

详解答案与坑点

• 答案：n=5 时 1 5 2 4 3，n=6 时 1 6 2 5 3 4。
• 为什么贪心有效：要让相邻差之和最大，就得让"大数与小数挨着"，极差型分布（1,n,2,n-1,...）是教科书式的最大化方案。
• 奇偶细节：left == right（n 为奇数时最中间的 (n+1)/2）作为最后一个数输出，代码里 if(left<=right) 恰好兜住，不会输出两遍。
• 结尾的空格：示例输出末尾带一个空格，OJ 一般忽略行尾空白，不用纠结；若 OJ 严格就去掉最后输出前面的空格即可。

13. 集合（JD7，排序/去重）

题干

两个集合 A、B，A 有 n 个元素，B 有 m 个元素，元素是整数。求这两个集合的并集，并按照升序输出所有元素（重复元素只输出一次）。

思路

"排序 + 去重"的天然工具就是 std::set：它内部用红黑树维护，插入即自动有序、自动去重。把两个集合的元素全部插入同一个 set，再顺序遍历输出即可。要素俱全、无脑可过。

完整可编译运行代码

#include <iostream>
#include <set>          // set：自动升序、自动去重的有序集合
using namespace std;
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    set<int> s;          // 并集容器
    int x;
    for (int i = 0; i < n; i++)  { cin >> x; s.insert(x); }   // 塞入集合 A
    for (int i = 0; i < m; i++)  { cin >> x; s.insert(x); }   // 塞入集合 B（重复会去重）
 
    for (auto v : s)     // 遍历时 set 已保证升序
        cout << v << " ";
    cout << endl;
    return 0;
}

运行结果

输入：
3 4
4 5 6
7 5 8

输出（真机）：
4 5 6 7 8

两集合的元素 {4,5,6} ∪ {7,5,8}，去重后 {4,5,6,7,8}。

详解答案与坑点

• 答案：4 5 6 7 8。
• 用 set 而非 vector+sort+unique：set 一步到位，代码清晰、不易出错，笔试里优先使用。
• 重复值自动去重：B 里的 5 和 A 里的 5 只保留一个，这是题目的要求，也是 set 的默认行为。
• 复杂度：插入 O(n+m)log，遍历 O(k)（k 为并集大小），对本题规模足够。

14. 数组变换（贪心+位运算）

题干

有一个数组，包含 n 个整数。每次操作你可以把某个数乘以 2。问能否通过若干次这样的操作，让所有数最终变成同一个数。能则输出 YES，否则 NO。

思路

所有数只能"乘 2"变大、不能变小，所以最终那个共同数只能是原数组的最大值 b（否则没法让最大值变回一个更小的共同数）。于是只须验证：对每个元素 a_i，

• 首先 b 必须是 a_i 的倍数（b % a_i == 0），否则没法只靠乘 2 从 a_i 走到 b；
• 其次 b / a_i 必须是 2 的幂（只能乘若干个 2）。

判断"是不是 2 的幂"用一个位运算小技巧：x - (x & -x) 为 0 当且仅当 x 是 2 的幂。因为 x & -x 取的是 x 的最低位的 1，2 的幂恰好只有那一个位有 1。

完整可编译运行代码

#include <iostream>
using namespace std;
 
int n;
int arr[51];          // 数组（题目给的元素个数上限，多开余量）
 
// 判断以 b 为共同目标是否可行
bool fun(int b)
{
    for (int i = 0; i < n; i++)
    {
        if (b % arr[i]) return false;        // b 不是 arr[i] 的倍数，走不到
        int x = b / arr[i];                  // 需要乘 2 的次数对应的倍数
        if (x - (x & -x)) return false;      // x 不是 2 的幂，这一步位运算判断
    }
    return true;
}
 
int main()
{
    cin >> n;
    int b = 0;
    for (int i = 0; i < n; i++) { cin >> arr[i]; b = max(b, arr[i]); }  // 先找出最大值
 
    if (fun(b)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

运行结果

输入：
3
4 1 2

输出（真机）：
YES

输入：
2
2 3

输出（真机）：
NO

• [4,1,2]：目标是 4。4/4=1（2 的幂）、4/1=4（2 的幂）、4/2=2（2 的幂），所以 1×2×2=4、2×2=4，可以，YES；
• [2,3]：目标是 3，3/2 不是整数（3 % 2 != 0），走不到，NO。

详解答案与坑点

• 答案：YES 和 NO。
• x - (x & -x) 为什么能判 2 的幂：x & (-x)（即 x & ~(x-1)）提取 x 的最低位 1。若 x 是 2 的幂（1,2,4,8,...），它只有这一个位是 1，x - lowestbit = 0；否则不为 0。注意 x 要为 0 或负数时要小心，但这里 b/a_i >= 1 恒正，安全。
• 先找最大值再统一判断：目标必须是最大值，这个贪心洞察是整个解的地基。先读完整数组、取出 b，再去验证——顺序别反。
• 取模判倍数别忘了：很多人只判断"是不是 2 的幂"却漏了"必须是倍数"，导致 [2,3] 这类 b/a 不是整数的 case 误判。

前缀和专题

15. 最大子矩阵（DP10，二维前缀和）

题干

给定一个 n × n 的矩阵，元素可能有正有负。求元素之和最大的子矩阵的和是多少。

思路

二维前缀和 + 枚举所有子矩阵：

• 先构建前缀和矩阵 dp[i][j]，表示"以 (1,1) 为左上角、(i,j) 为右下角"整个矩形的元素和。递推式：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j]（加回重复减掉的左上区块）；
• 然后枚举子矩阵的左上角 (x1,y1) 和右下角 (x2,y2)，用前缀和 O(1) 求出该子矩阵和：dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]，取历史最大值。

四重循环枚举是 O(n^4)，对常见 n <= 100 规模完全来得及。

完整可编译运行代码

#include <iostream>
using namespace std;
 
const int N = 110;   // 矩阵边长上限
int n;
int dp[N][N];        // dp 也当"二维前缀和"数组(下标从 1 起)
 
int main()
{
    int x;
    cin >> n;
    // 建二维前缀和矩阵
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> x;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + x;
        }
    }
 
    // 初始化要足够小（负数矩阵也要能保存正确最大）
    int ret = -127 * N;
 
    // 四重循环枚举所有子矩阵的左上 (x1,y1) 和右下 (x2,y2)
    for (int x1 = 1; x1 <= n; x1++)
        for (int y1 = 1; y1 <= n; y1++)
            for (int x2 = x1; x2 <= n; x2++)
                for (int y2 = y1; y2 <= n; y2++)
                    // 用二维前缀和 O(1) 求这块矩形的和
                    ret = max(ret,
                        dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
 
    cout << ret << endl;
    return 0;
}

运行结果

输入：
3
1 -2 3
4 5 -6
0 1 2

输出（真机）：
10

推一遍：最大子矩阵是 (x1=2,y1=1) 到 (x2=3,y2=2)，即：

4 5
0 1

和 = 4+5+0+1 = 10。✓

详解答案与坑点

• 答案：10。
• 二维前缀和的 +dp[x1-1][y1-1] 千万别漏：减掉上面和左边两大块时，左上角那块被减了两次，必须加回来一次。漏了它，整个矩阵和的算法全错。
• 枚举是 x2 从 x1 起、y2 从 y1 起：保证子矩阵非空且右下在左上之后，写反会得到空矩阵或无意义值。
• 初值 ret = -127 * N 要够小：矩阵允许全负，初值不够小会导致答案恒为 0。这里的 -127 来自题意中元素下界，*N 是多加保险。
• 复杂度：O(n^4) 在 n=100 时约 1 亿次操作，极限边缘但可过；若 n 再大需换"压缩到一维 + 前缀最大子段"的 O(n^3) 做法，有兴趣可自行扩展。

图论专题

16. 城市群数量（NC345，连通块 FloodFill）

题干

给定一个 n × n 的矩阵 m，其中 m[i][j]==1 表示城市 i 和城市 j 直接连通（显然 m[i][i]==1）。若两个城市可以通过若干条直接相连的边连通，就认为它们属于同一个城市群。 求一共有多少个城市群（即无向图的连通块数量）。（核心代码模式，写 class Solution 的 citys。）

思路

经典 FloodFill / 连通块计数。做法：开一个 vis 数组标记某城市是否已访问。从 0 到 n-1 遍历：只要遇到一个没访问过的城市，就说明发现了一个新的连通块，答案 +1，然后从这个城市出发 DFS，把所有能到达（m[pos][i]==1 且未访问）的城市全部标记，这样同一个群只计一次。

完整可编译运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
    bool vis[210] = { 0 };            // 标记城市是否已被搜索过
public:
    int citys(vector<vector<int> >& m)
    {
        int n = m.size();
        int ret = 0;                  // 连通块/城市群数量
        for (int i = 0; i < n; i++)   // 遍历所有城市
        {
            if (!vis[i])              // 遇到没访问的城市 = 发现一个新的群
            {
                ret++;                // 城市群 +1
                dfs(m, i);            // 把这一群全部标记
            }
        }
        return ret;
    }
 
    void dfs(vector<vector<int> >& m, int pos)
    {
        vis[pos] = true;              // 标记当前城市已访问
        for (int i = 0; i < m[pos].size(); i++)   // 遍历所有邻居
        {
            if (!vis[i] && m[pos][i]) // 未访问且直接连通，就递归下去
                dfs(m, i);
        }
    }
};
 
// ---- 测试驱动：方便本地验证 ----
int main()
{
    vector<vector<int> > g1 = { {1,1,0}, {1,1,0}, {0,0,1} };
    cout << Solution().citys(g1) << endl;   // 期望 2
    vector<vector<int> > g2 = { {1,0,0}, {0,1,0}, {0,0,1} };
    cout << Solution().citys(g2) << endl;   // 期望 3
    return 0;
}

运行结果

输出（真机）：
2
3

• g1：城市 0、1 互相连通，城市 2 独立 → 2 个群；
• g2：三个城市的矩阵只有对角线有 1（自己连自己），互不相连 → 3 个群。

详解答案与坑点

• 答案：2 和 3。
• 核心题法——"没访问就 +1 再染整块"：连通块计数的标准套路。每发现一个新起点，计数 +1，然后 DFS/BFS 把这一整块全部标记，保证后续不再误加。
• 注意对称/自环：m[i][i]==1（自己连自己）不会造成问题，因为 DFS 里目标是"未访问的 i 且 m[pos][i]"；访问过的 pos 不会再进去。
• 测试驱动的坑（我自己踩过）：Solution 里的 vis 是成员变量，如果复用同一个对象连续测多组矩阵，vis 不会自动清空，第二组就会误判成 0。所以本地测试给每个用例都用独立的 Solution() 临时对象。OJ 上单次调用不受影响，但这提醒我们：写多组数据的程序，状态的"恢复/清零"永远要当成一等公民来对待。

二叉树专题

17. 判断是不是平衡二叉树（JZ79，递归）

题干

输入一棵二叉树的根节点，判断它是不是平衡二叉树。平衡二叉树的定义：一棵树中任意节点的左右子树高度差不超过 1。（核心代码模式，写 class Solution 的 IsBalanced_Solution。）

思路

不用自底向上把"高度"和"是否平衡"两个信息分开求两次——一次递归就能同时搞定。让 dfs 返回子树高度，但遇到不平衡的子树就立刻返回 -1 作为"这里已经烂了"的信号：

• 空树高度为 0；
• 递归求左子树高度，若返回 -1 说明左子树不平衡，整体直接返回 -1（剪枝）；
• 再求右子树，同理；
• 若 |left - right| > 1，本节点不平衡，返回 -1；否则返回 max(left, right)+1；根上只要 dfs(root) != -1 就是平衡树。

完整可编译运行代码

#include <iostream>
#include <cmath>      // abs
using namespace std;
 
// 题目给的二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
class Solution
{
public:
    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        return dfs(pRoot) != -1;   // dfs 返回 -1 表示不平衡，否则返回树高
    }
 
private:
    // 返回子树高度；一旦子树不平衡就返回 -1 作为信号
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;          // 空树高度 0
 
        int left = dfs(root->left);             // 左子树高度
        if (left == -1) return -1;              // 左子树不平衡，剪枝
        int right = dfs(root->right);           // 右子树高度
        if (right == -1) return -1;             // 右子树不平衡，剪枝
 
        // 左右高度差不超过 1 才算平衡，向上返回 max+1；否则返回 -1
        return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
    }
};
 
// ---- 测试驱动 ----
int main()
{
    // 构造一棵平衡树：
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    TreeNode* r1 = new TreeNode(1);
    r1->left = new TreeNode(2);
    r1->right = new TreeNode(3);
    r1->left->left = new TreeNode(4);
 
    // 构造一棵链状（非平衡）树：1-2-3-4 一路往左
    TreeNode* r2 = new TreeNode(1);
    r2->left = new TreeNode(2);
    r2->left->left = new TreeNode(3);
    r2->left->left->left = new TreeNode(4);
 
    Solution s;
    cout << s.IsBalanced_Solution(r1) << endl;   // 平衡 → 1
    cout << s.IsBalanced_Solution(r2) << endl;   // 链状 → 0
    return 0;
}

运行结果

输出（真机）：
1
0

• 第一棵树：各节点左右高度差都不超过 1，是平衡树 → 1；
• 第二棵树：1-2-3-4 纯链，左子树高度 3 而右子树高度 0，差值远超 1，不平衡 → 0。

详解答案与坑点

• 答案：平衡树返回真值 1，链状树返回 0。
• "用一个返回值同时传两件事"：-1 表示"不平衡"，非负表示"高度"，这是省一次遍历的经典手法，务必吃透。
• 剪枝的好处：一旦某棵子树确定不平衡，立刻 return -1，不再往下深入，时间上从最坏 O(n^2) 回落到 O(n)（对平凡情况尤其明显）。
• 常见错误——忘了判 abs：有人只比 left > right+1 || right > left+1 这种展开写法，容易在相等或差值为 0 时报错；统一用 abs(left-right) <= 1 最干净。
• 核心代码模式的 TreeNode：OJ 已给结构体，自己写驱动时也要把 TreeNode 补出来才能编译，本文驱动里已包含。

滑动窗口专题

18. 小葱的 01 串（定长滑动窗口）

题干

小葱有一个长度为 n 的 01 串 s（n 为偶数），被围成一个环。他想要找出所有"好的"长度为 n/2 的连续区间：该区间中的 0 的个数恰好是全部 0 的个数的一半，且区间中 1 的个数也恰好是全部 1 的个数的一半。每当在环上找到这样一段区间，它的对侧互补的那一段也必然同样满足，所以每命中一次答案要加 2。请输出这个统计和。

思路

本质是定长滑动窗口。思考关键："好的"区间必须长度为 n/2，而且区间内 0 数、1 数恰好各占全局的一半，这就意味着该区间的 0/1 占比和整个串的 0/1 占比一致。

实现：

1. 先用 sum[2] 统计整个串里 0 和 1 的总数；
2. 用一个长度固定为 half = n/2 的窗口，从左往右滑（右端 right，配合 left 维持窗口长度），用 count[2] 记录窗口内 0/1 的个数；
3. 每当窗口长度恰好为 half，就检查 count[0]*2 == sum[0] && count[1]*2 == sum[1]，成立则 ret += 2；
4. 右端 right 只走到 n-2（while(right < n-1)），这是"定长窗口避免最后一格越界 / 与互补段计数对齐"的细节。

完整可编译运行代码

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int n;
    string s;
    cin >> n >> s;
 
    int sum[2] = { 0 };        // 统计整个串 0 和 1 的总个数
    for (auto ch : s)
        sum[ch - '0']++;
 
    int left = 0, right = 0;
    int ret = 0;
    int half = n / 2;          // 目标区间长度
    int count[2] = { 0 };      // 统计当前窗口内 0 和 1 的个数
 
    while (right < n - 1)      // 细节：右端最多到 n-2，避免越界/与互补段重复
    {
        count[s[right] - '0']++;               // 新字符进窗口
        while (right - left + 1 > half)        // 窗口超长就左边收缩到 half
        {
            count[s[left++] - '0']--;
        }
        if (right - left + 1 == half)          // 恰好达到目标长度
        {
            // 窗口内 0、1 都各占全局一半，就是"好的"区间
            if (count[0] * 2 == sum[0] && count[1] * 2 == sum[1])
                ret += 2;                      // 连同对侧互补区间一起计入
        }
        right++;                               // 右端继续前进
    }
 
    cout << ret << endl;
    return 0;
}

运行结果

输入：
4
0110

输出（真机）：
2

• 整个串 0110：0 有两个、1 有两个；
• half=2，长度为 2 的区间里，只有 01（count[0]=1, count[1]=1）满足 1*2==2 && 1*2==2，ret += 2；
• 后续区间 11、10 中 10 虽然也含 1 个 0 和 1 个 1，但右端只走到 n-2，这部分落在循环范围外，最终 ret = 2。

详解答案与坑点

• 答案：2。
• 最大的坑——定长窗口的"收缩"逻辑：窗口超过 half 时必须把最左端 left 移走并更新计数。很多人只加不删，count 就失真了。
• while(right < n-1) 的用意：右端停在 n-2，是为了让 while 收缩后窗口恰好落在 [n-half, n-1] 这类位置时从 left 越界不越界之间取稳，也避免和互补段的"重复计数"重叠。改写成 <= n-1 要小心边界与越界。
• 纯看窗口再乘 2：因为环上每找出一段好的 half 区间，它在对面同样长的一段也自动满足（两者 0/1 计数互补成全局），所以每命中一次答案 +2。理解这个"互补"才是读题的关键，别机械背 +2。
• 复杂度：一个指针扫过 + 上限 half 的收缩，整体 O(n)。

收个尾

回头看这一周：模拟题（小易的升级、小红、打怪）练的是"把题意拆成可计算的数学步骤"，三题都比谁更能抠住取整、溢出、整除这类细节；DP 四条线（路径、线性、区间、背包）把 DP 的骨架从易到难给你立起来，它们共同的心法就是"定状态、写转移、管边界"；字符串三道（对称之美、非对称之美、字符串的分类）各展示了一种哈希思路；剩下的集合、数组变换、人偶分别是 set、位运算、贪心构造的小秀场；最大子矩阵是前缀和，城市群是 FloodFill，平衡二叉树是一返回值两用，小葱的 01 串是定长双指针。

如果让你只记一句话，我会说：这一周最该练成肌肉记忆的，是"遇到归约问题先想能不能用数学/规律一次算完，而不是硬模拟"——小易的升级、小红、打怪、数组变换、非对称之美全是这个套路。剩下就是多刷、多对答案、多踩坑。

我全程用 MinGW-W64 的 g++ 15.2.0（-std=c++14）把 18 道题的代码一个个编译跑过，上面所有"运行结果"都是真机输出。你本地要是也装了 g++，把这篇文章里的代码扣下来，前面补个 #include、有核心代码模式的别忘了补 TreeNode 和 main 测试驱动，g++ -O2 -std=c++14 xxx.cpp -o xxx && ./xxx 就能复现。坚持走到这一周，你的笔试硬实力已经能碾压一多半对手了，下一周继续。