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

先跟各位把话说在前面：这一周是六天、十八题的硬仗，考点横跨概率、排序、双指针、二分、动态规划、DFS、BFS、贪心、哈希、区间DP、栈……几乎把笔试里"中高难度"的板斧都抡了一遍。和前面几周一样，我不会只丢给你一个能 AC 的代码，而是把每一道题的"题干 → 思路 → 完整可运行代码 → 真机运行结果 → 详解答案与易错坑"完整闭环做完。

说到运行结果，必须跟你强调：下面的所有输入输出，都是我拿本机 g++ 15.2.0 真正编译运行过的，不是脑内手算的"口算答案"。你看到哪个数字，那就是编译产物吐出来的真东西。你照这个流程在自己机器上 Build & Run 一遍，输入同样的数据，应该得到一模一样的输出。这样你的"对答案"才对得上号。

这一周十八题，分布大概是这样：

• Day01：kotori和抽卡（二）（概率）、ruby和薯条（排序＋双指针）、循环汉诺塔（动态规划）
• Day02：差值（排序）、kotori和素因子（DFS）、dd爱科学1.0（最长非降子序列）
• Day03：kanan和高音（双指针）、拜访（BFS）、买卖股票的最好时机(四)（动态规划）
• Day04：AOE还是单体？（贪心）、kotori和n皇后（哈希表）、取金币（区间DP）
• Day05：矩阵转置（模拟）、四个选项（DFS＋剪枝）、接雨水（预处理双数组）
• Day06：疯狂的自我检索者（贪心）、栈和排序（栈＋贪心）、加减（前缀和＋滑动窗口）

你会发现，这一周和前几周最大的不同是：几乎没有"白给送分题"，每道题都得真刀真枪过一遍算法。废话不多说，直接开干。

Day01：概率、双指针、递推动态规划

Day01 从三门课入手：概率期望、排序后的双指针、以及一个需要自己推递推式的 DP。节奏是从数学到代码再到数学，热身刚刚好。

1. kotori和抽卡（二）（概率 · 数学期望）

题干

kotori 在玩一个抽卡游戏，每次抽到想要的那张卡的概率是 0.8。她一共抽了 n 次，题目给两个数 n、m，请你算出"恰好抽中 m 张想要的卡"的概率。结果保留 4 位小数输出。（牛客题号 500566）

思路

这是高中数学里最标准的二项分布：n 次独立重复试验，每次成功概率 p = 0.8，恰有 m 次成功的概率是

P = C(n, m) · 0.8^m · 0.2^(n - m)

其中 C(n, m) = n! / (m! · (n-m)!)。剩下的全是体力活：把组合数算出来，再乘上概率的幂。为了避免大数溢出，我们边乘边除，先把 C(n, m) 的分子 n·(n-1)···(n-m+1) 乘进去，再把分母 m! 除掉，最后分别乘 m 个 0.8 和 n-m 个 0.2。

完整可运行代码

#include <iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    double ret = 1.0;
    for(int i = n; i >= n - m + 1; i--) ret *= i;          // C(n,m) 的分子部分
    for(int i = m; i >= 2; i--) ret /= i;                  // C(n,m) 的分母 m!
    for(int i = 0; i < m; i++) ret *= 0.8;                 // 抽中 m 张的概率贡献
    for(int i = 0; i < n - m; i++) ret *= 0.2;             // 没抽中 n-m 张的概率贡献
    printf("%.4lf\n", ret);
    return 0;
}

运行结果

输入：
5 3
2 1

输出（真机 g++ 15.2.0）：
0.2048
0.3200

手动复核第一组 5 3：C(5,3)=10，0.8^3=0.512，0.2^2=0.04，10 × 0.512 × 0.04 = 0.2048。✓

详解答案与坑点

• 答案：5 3 输出 0.2048，2 1 输出 0.3200。
• 思路核心：一眼认出二项分布公式，别去死磕"期望"两个字，这里的"数学期望"是题型标签，实际考的就是组合概率。
• 坑一（最重要）：中间值用 double，别用 int。 组合数计算过程中 n! / (m!(n-m)!) 如果不及时相除，n! 很可能溢出 int（甚至 long long）。教材的写法是"乘分子、除分母、再乘概率"，让值始终维持在 1 附近，既稳又不溢出。顺序不能乱。
• 坑二：保留 4 位小数。用 printf("%.4lf", ...) 而不是默认精度，也不要把 %lf 错写成 %f（在 printf 里两者对 double 都合法，但养成 %lf 的习惯更稳）。
• 坑三：n - m 可能等于 0（即抽 n 次全中）。此时第二个 for 循环自然不执行，ret 就只含 0.8^n，公式依然正确，不用特判。
• 一句话：把"每次成功 p、总次数 n、成功 m 次"翻译成组合数公式，然后边乘边除防溢出，这道送分题就吃下了。

2. ruby和薯条（排序 ＋ 双指针／二分）

题干

ruby 有一包薯条，第 i 根的长度是 a[i]。她想挑两根薯条，使得它们的长度之差落在闭区间 [L, R] 内。问一共有多少对薯条满足要求。数据范围很大，普通枚举会超时。（牛客题号 375038）

思路

无序的数对"差值在区间内"最怕排序后还是混乱，所以我们先排序，把问题规约成"已排序数组里有多少对下标 (i<j) 满足 L ≤ a[j] - a[i] ≤ R"。

核心技巧是容斥：

差值在 [L, R] 的对数 = 差值在 [0, R] 的对数 - 差值在 [0, L-1] 的对数

而"差值在 [0, x] 的对数"可以用一对双指针快速统计：枚举右端点 right，让 left 一直右移直到 a[right] - a[left] ≤ x，此时以 a[right] 作为较大那一端的合法数对就有 right - left 个（因为 a[left..right-1] 里任意一个和 a[right] 的差都 ≤ x）。累加即可。

这里我给出实现清晰、不易错的双指针 + 前缀容斥解法，同时也把"排序 + 二分"的思路在详解里点给你，两条路都能过。

完整可运行代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, l, r;
int arr[N];
 
// 找差值在 [0, x] 之间一共有多少对（双指针滑动）
long long find(int x)
{
    int left = 0, right = 0;
    long long ret = 0;
    while(right < n)
    {
        while(arr[right] - arr[left] > x) left++;  // left 右移，让差落到 <= x
        ret += right - left;                        // 以 right 为较大端的对数
        right++;
    }
    return ret;
}
 
int main()
{
    cin >> n >> l >> r;
    for(int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    cout << find(r) - find(l - 1) << endl;          // 容斥：减掉差值 < L 的部分
    return 0;
}

运行结果

输入：
5 2 4
1 3 5 7 9

输出（真机 g++ 15.2.0）：
7

手动复核：排序后 1 3 5 7 9，差在 [2,4] 的对有 (1,3)(1,5)(3,5)(3,7)(5,7)(5,9)(7,9)，恰好 7 对。✓

详解答案与坑点

• 答案：样例输出 7。
• 复杂度：O(n log n) 排序 + O(n) 双指针，空间 O(1)（不算排序栈）。
• 坑一（核心）：区分"差在区间"和"差不超过某值"。直接求 [L,R] 不好做，转成两个 [0,x] 相减，这是这类"区间内计数"题的常用容斥手法，务必吃透。
• 坑二：双指针的收敛方向。 while(arr[right]-arr[left]>x) left++; 只往一个方向移 left，right 只增不减，整体 O(n)。千万别写成"每次从 0 重新扫"，那就退化回 O(n²) 了。
• 坑三：数据范围开 long long。 ret += right - left 累加的是 O(n²) 量级的数对个数，n 到 2e5 时中间值可能超 int，必须 long long。
• 一题多解（排序＋二分）：枚举较大值 arr[i]，在 [1, i-1] 里用二分找"最后一个满足 差≤R"的下标做右端点、"第一个满足 差≥L"的下标做左端点，两者相减再加一。注意这里有个细节：找左端点时用 lower_bound(arr[i]-R)，找右端点时用 upper_bound(arr[i]-L)-1。两条路本质同一件事：已排序就用值域二分定位区间。
• 一句话：先排序，再用"[0,R] 减 [0,L-1]"的容斥＋双指针，一次扫描把计数做出来，这是标准答案。

3. 循环汉诺塔（动态规划 · 递推）

题干

三根柱子 A、B、C 围成一圈排列，圆盘一次只能搬到相邻的那根柱子（沿圈单向还是双向不限制，关键是一步只能到邻居）。求：把 n 个圆盘从一根柱子全部移到旁边那根（相邻）需要的最少步数记为 x，以及移到需要绕过去的那根（次相邻）需要的最少步数记为 y。结果对 1e9+7 取模，输出 x 和 y。（牛客题号 AB27 / 1116945）

思路

这题的难点在于自己推递推式，而不是套模板。我们用两个量来表示状态：

• x[i]：把 i 个盘从一根柱子搬到相邻柱子的最少步数；
• y[i]：把 i 个盘从一根柱子搬到次相邻柱子（也就是"越过一根"）的最少步数。

手工推导（以"从 A 搬到相邻的 B"为例）可以得出递推：

• 要把 n 个盘搬到相邻柱子 B，需要先把上面 n-1 个盘搬到次相邻的柱子 C（用 y[n-1] 步），再把最大的盘搬到 B（1 步），最后把 n-1 个盘从 C 搬到 B——但 C 到 B 是搬回"相邻"柱，又要 x[n-1]？不对，这里需要仔细考究方向。教材给出的成品递推是：

x[i] = 2 * y[i-1] + 1
y[i] = 2 * y[i-1] + 2 + x[i-1]

初值：x[1] = 1（一个盘移到相邻柱，1 步），y[1] = 2（一个盘移到次相邻柱，得先到相邻再绕一下，2 步）。

这个递推是对的（它是"循环/圆周汉诺塔"的标准递推）——考的并不是你会不会背公式，而是你能不能盯着它想通"搬盘必须借用中间盘"。我们直接把它写进 DP（只需滚动两个变量，空间 O(1)），每一步对 MOD 取模。

完整可运行代码

#include <iostream>
using namespace std;
const int MOD = 1e9 + 7;
int n;
int main()
{
    cin >> n;
    int x = 1, y = 2;                        // n = 1 的答案
    for(int i = 2; i <= n; i++)
    {
        int xx = x, yy = y;                  // 保存上一轮的旧值
        x = (2 * yy + 1) % MOD;              // x[i] = 2*y[i-1] + 1
        y = ((2 * yy) % MOD + 2 + xx) % MOD; // y[i] = 2*y[i-1] + 2 + x[i-1]
    }
    cout << x << " " << y << endl;
    return 0;
}

运行结果

输入：
3

输出（真机 g++ 15.2.0）：
15 21

输入：
4

输出：
43 59

手动核验 n=3：从 x=1,y=2 推 n=2 得 x = 2*2+1 = 5、y = 2*2+2+1 = 7；再推 n=3 得 x = 2*7+1 = 15、y = 2*7+2+5 = 21。✓

详解答案与坑点

• 答案：n=3 输出 15 21，n=4 输出 43 59。
• 复杂度：O(n)，滚动两个变量所以空间 O(1)。
• 坑一（核心）：递推里必须用"上一轮"的旧值。 x 的转移用 y[i-1]、y 的转移用 y[i-1] 和 x[i-1]。如果直接写 x = 2*y+1; y = 2*y+2+x;，第二句里的 x 已经是这一轮刚更新过的新值了，全错。所以代码里先用 xx = x; yy = y; 存旧值，再算——这是滚动数组最常见的翻车点。建议每次写这种滚动递推都先存旧值。
• 坑二：取模时机。 每一步都对 MOD 取模；y 的式子里的 2*yy 也要先取模再参与加法，防止溢出（虽然这里 n 小时无妨，属于良好习惯）。
• 坑三：初值。 x=1（移到相邻柱一档），y=2（移到次相邻柱两档）。把初值设错，整个递推会系统性偏移。
• 一句话：这不是"看图背模板"的题，是"自己要能推出相邻/次相邻两种最少步数的递推"。遇到这种题，先小规模手工算 n=1,2,3 找规律，再写滚动 DP，十拿九稳。

Day02：排序的变奏、DFS 枚举、最长非降子序列

Day02 的三道题，讲的是同一个主题的不同侧面：排序之后，问题就变了味道。最小差值靠排序；素因子组合要靠排序式枚举；"改字符串"则是把最长非降子序列当靶子。

1. 差值（排序）

题干

给定一个长度为 n 的数组，请你求出任意两个数之差的绝对值的最小值。如果数字可以相同（差为 0 也算），输出 0 也是合法的。（牛客题号 2156174，核心代码模式：写 minDifference 方法）

思路

这题几乎就是"排序的意义"本义：如果两个数要离得最近，它们在原数组中未必相邻，但在排序后的数组里必然相邻。所以排序后，只要扫一遍相邻元素之差取最小值即可。

证明一句话：若存在两个不相邻的数 (a[i], a[j]) 的差比某对相邻差还小，那么它们之间那个中位数一定夹在两者之间，导致 (a[i], 中间数) 或 (中间数, a[j]) 更近，矛盾——所以最小值一定出现在某对相邻元素之间。

完整可运行代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class Solution
{
public:
    int minDifference(vector<int>& arr)
    {
        sort(arr.begin(), arr.end());
        long long ret = 1e16 + 10;                  // 一个足够大的初始值
        for(int i = 1; i < arr.size(); i++)
        {
            // 相邻元素之差取最小；用 long long 防减法溢出
            ret = min(ret, (long long)arr[i] - arr[i - 1]);
        }
        return (int)ret;
    }
};
 
// ---- 本地测试驱动 ----
int main()
{
    int n; cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    Solution so;
    cout << so.minDifference(v) << endl;
    return 0;
}

运行结果

输入：
5
5 3 1 8 9

输出（真机 g++ 15.2.0）：
1

输入：
3
3 5 5

输出：
0

第一组排序得 1 3 5 8 9，相邻差依次 2 2 3 1，最小值 1。第二组 3 5 5 有两个 5，差 0。✓

详解答案与坑点

• 答案：第一组 1，第二组 0。
• 复杂度：O(n log n)（排序），空间 O(1)。
• 坑一：用 long long 做减法。 题目注释也提示了 INT_MIN ~ INT_MAX，arr[i] - arr[i-1] 在 int 下可能溢出（负大数减正大数）。先转 long long 再减最稳。
• 坑二：初始值要足够大。 用 1e16+10 这种"大过任何可能差"的初始化，保证第一对相邻差必然刷新 ret。写成 INT_MAX 也行。
• 坑三：是不是一定要绝对值？ 排序后 arr[i] >= arr[i-1]，差天然非负，不需要 abs。别画蛇添足。
• 一句话：最小差值的归宿永远是"排序后看相邻"，这是核心洞察，背下来。

2. kotori和素因子（DFS · 枚举＋回溯）

题干

kotori 手里有 n 个数字，每个数字都有若干不同的素因子。她希望从每个数字里恰好选出一个素因子，使得选出的 n 个素因子互不相同，并让这些素因子的和最小。如果无论如何选都无法做到（无解），输出 -1。n 很小（≤ 15），但每个数字可能较大。（牛客题号 500564）

思路

这是一道排列式 DFS 枚举。因为 n ≤ 15，数字的值域也不大（arr[i] ≤ 1010），我们可以直接暴力：

• dfs(pos)：正在给第 pos 个数字选素因子；
• 用 use[值] 标记"这个素因子是否已经被前面的数字选走"，每个素因子只能被选一次；
• 用 path 记录当前已选素因子的和；
• 逐层枚举第 pos 个数字的所有素因子（能被整除、且是素数、且还没被用过），选进去→递归→回溯恢复现场；
• 走到 pos == n 表示所有数字都选了一个素因子，用当前和 path 更新答案 ret 取最小。
• 若一个可行方案都枚举不到（ret 停留在初始的极大值），说明无解，输出 -1。

素性判断用最简单的试除法即可。

完整可运行代码

#include <iostream>
#include <cmath>
using namespace std;
const int N = 15, M = 1010;
int n, arr[N];
bool use[M];          // use[i]：值 i 这个素因子是否已被选走
int path;             // 当前已选素因子之和
int ret = 0x3f3f3f3f; // 最终结果，初值为无穷大表示"未找到"
 
bool isPrim(int x)    // 试除法判素数
{
    if(x <= 1) return false;
    for(int i = 2; i <= sqrt(x); i++)
        if(x % i == 0) return false;
    return true;
}
 
void dfs(int pos)
{
    if(pos == n) { ret = min(ret, path); return; }   // 所有数字都选好了
    // 枚举 arr[pos] 的所有"没用过的素因子"
    for(int i = 2; i <= arr[pos]; i++)
    {
        if(arr[pos] % i == 0 && isPrim(i) && !use[i])
        {
            path += i; use[i] = true;
            dfs(pos + 1);
            path -= i; use[i] = false;   // 回溯，恢复现场
        }
    }
}
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    dfs(0);
    if(ret == 0x3f3f3f3f) cout << -1 << endl;
    else cout << ret << endl;
    return 0;
}

运行结果

输入：
3
5 7 11

输出（真机 g++ 15.2.0）：
23

输入：
2
10 6

输出：
5

第一组 5 7 11 全是素数，选 5+7+11=23。第二组 10 6：10 的素因子 {2,5}、6 的素因子 {2,3}，最优选 2 和 3 之和 5（若 10 选 5、6 选 2 则 7，不是最优；10 的 5 和 6 的 3 则 8）。✓

详解答案与坑点

• 答案：3 / 5 7 11 → 23；2 / 10 6 → 5。
• 复杂度：最坏 O(每个数的因子种数 ^ n)，但 n ≤ 15、值域小、use 剪枝很凶，实际运行飞快。
• 坑一（灵魂）：每个素因子只能被选一次。 这里的"互不相同"指的是数值不同，所以用 use[值] 当桶。同一个数值的素因子即使属于不同数字，一个被选走，后面就不能再选它了。这是"能不能互不相同"的核心约束。
• 坑二：素因子必须是素数。 判断 arr[pos] % i == 0 && isPrim(i) 两个条件都要，别漏掉"是素数"。枚举 i 从 2 到 arr[pos] 是对的范围（1 既非质也非同约定，不需要）。
• 坑三：不可达的 -1。 ret 用 0x3f3f3f3f 初始化充当"无穷大/未赋值"，DFS 结束若它没被更新就输出 -1。这是"是否存在可行方案"类问题的标准初始化手法。
• 坑四：一定要回溯恢复现场。 path 和 use 都是跨分支共享的全局状态，必须"用了再恢复"；漏掉回溯会导致结果错误且难查。
• 一句话：每个数各挑一个互不相同的素因子、求和尽量小 → 就是"DFS 全排列枚举＋use 桶＋回溯取 min"，无解记 -1。

3. dd爱科学1.0（最长非降子序列 · 贪心＋二分）

题干

给一个长度为 n 的字符串（只含小写字母），你可以任意修改其中的字符为任意小写字母，求最少修改多少个字符，使得修改后的字符串是"非递减"的——即对任意位置满足 s[i] <= s[i+1]（'a' < 'b' < ... < 'z'）。（牛客题号 1714894）

思路

"最少修改几个字符让整个串非递减"有个漂亮的转化：

答案 = n - 原串最长非降子序列（LNDS）的长度。

理由：我们想尽量"不动"的那些字符，它们必须组成一个"不用改就合法"的骨架，而这个骨架就是原串里最长的一串"后一个不小于前一个"的子序列；剩下 n - len 个字符，每个都能被改掉来适配这个骨架。所以最小改动数就是 n - LNDS。

因为 n 可以到 1e6，O(n²) 的普通 DP 会超时，得用贪心 + 二分的经典优化：维护 dp[i] 表示"长度为 i 的所有非降子序列中，末尾字符最小的是谁"。因为 dp 数组单调递增，我们可以用二分找到当前字符 ch 该插入的位置：能续在末尾（ch >= dp[ret]）就 ret++；否则用二分找到第一个 > ch 的位置，把这个位置的末尾换成更小的 ch。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10;
int n;
string s;
char dp[N];       // dp[i]：长度为 i 的非降子序列中，最小的末尾字符
int ret;          // 当前最长非降子序列长度
 
int main()
{
    cin >> n >> s;
    for(int i = 0; i < n; i++)
    {
        char ch = s[i];
        if(ret == 0 || ch >= dp[ret]) dp[++ret] = ch;  // 能直接续在末尾
        else
        {
            // 二分找到第一个 > ch 的位置替换（保持 dp 单调递增）
            int left = 1, right = ret;
            while(left < right)
            {
                int mid = (left + right) / 2;
                if(dp[mid] > ch) right = mid;       // 因为是"非降"，用 > 找替换点
                else left = mid + 1;
            }
            dp[left] = ch;                          // 用更小的 ch 更新该长度末尾
        }
    }
    cout << n - ret << endl;                        // 需要改动的最少字符数
    return 0;
}

运行结果

输入：
6
abcabc

输出（真机 g++ 15.2.0）：
2

输入：
3
cba

输出：
2

abcabc 的最长非降子序列长度是 4（比如 aabc），6 - 4 = 2。cba 最长非降子序列长度是 1，3 - 1 = 2。✓

详解答案与坑点

• 答案：abcabc → 2；cba → 2。
• 复杂度：O(n log n)，空间 O(n)。
• 坑一（最容易错）：判断非降条件是 >= 不是 >。 题目要的是"非递减"（允许相等），所以 ch >= dp[ret] 就能续；二分找替换点时也要找"第一个 > ch 的位置"（因为相等时应该允许延续，只有严格大于才被替换）。不少人在 LIS（严格递增）和 LNDS（非降）之间切换时把比较符号搞混，在这里直接送掉。
• 坑二：答案是 n - ret，不是 ret。 题目问最少改几个字符，我们算的是最长能"白留"几个，两者是补集关系。
• 坑三：二分对下标的把握。 dp 已用下标 1 到 ret，二分区间 [1, ret]，注意"切换比较符号后 mid 的收缩方向"：if (dp[mid] > ch) right = mid; else left = mid+1;。
• 一句话：抓住"改最少 = 保留最长合法子序列"这个等价，剩下的就是背"贪心＋二分求 LNDS"模板，注意 >= vs > 的区别。

Day03：双指针、BFS 最短路、股票 DP

Day03 进入"硬菜"区。kanan 的高音是滑动双指针的实战，拜访是 BFS 求最短路条数（易错），买卖股票四是状态机 DP 的骨架题。

1. kanan和高音（模拟 · 双指针）

题干

kanan 在唱歌，声调由一串数字表示（第 i 个数字 a[i] 代表第 i 个音的音高）。她想选一段连续的乐谱来唱，要求这段区间内任意相邻两个音的高度之差不超过 8。求她最多能连续唱多长？（牛客题号 375043）

思路

又是一个"一段连续、相邻满足某条件、求最长"的题——滑动窗口 / 双指针正合适，而且这道题因为"相邻差 ≤ 8"只和相邻两个点有关，贪婪地"每次尽可能往右扩，扩不动就结算这一段的长度，然后跳到下一段起点"即可：

• 固定左指针 i，让右指针 j 一直往右走，只要 a[j+1] - a[j] <= 8 就继续；
• 撞墙（下一个差 > 8）就记录这一段长度 j - i + 1，更新答案；
• 把 i 跳到 j + 1，开下一段。

因为"一整段只要相邻差都 ok"就天然可行（可传递），所以双指针是线性一趟扫完。

完整可运行代码

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n;
int arr[N];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    int ret = 1;                                   // 至少能唱 1 个音
    for(int i = 0; i < n; )
    {
        int j = i;
        while(j + 1 < n && arr[j + 1] - arr[j] <= 8) j++;  // 向右扩到相邻差>8为止
        ret = max(ret, j - i + 1);                 // 结算这一段的长度
        i = j + 1;                                 // 跳到下一段的起点
    }
    cout << ret << endl;
    return 0;
}

运行结果

输入：
5
1 2 3 100 101

输出（真机 g++ 15.2.0）：
3

输入：
5
1 3 5 7 9

输出：
5

第一组 1 2 3（相邻差 1、1）是一段，3→100 差 97 断了；100 101 又是一段，最长 3。第二组相邻差都 2，全段 5。✓

详解答案与坑点

• 答案：第一组 3，第二组 5。
• 复杂度：O(n)，每个位置被 j 扫过至多一次。
• 坑一：越界保护 j + 1 < n。 比较 arr[j+1] - arr[j] 时 j+1 必须合法。写成 j+1 < n，不是 j < n，否则数组尾巴越界。
• 坑二：外层 for(i) 里手动推进 i = j + 1。 我在 for 循环的更新处留空，靠函数体内手动跳。如果你又写了 i++ 或让 for 自动 i++，会和白跳重叠，逻辑错乱。这种"双指针定位连续段"的写法要一次写对。
• 坑三：ret 初值 1。 n 至少 1 时保底能唱 1 个音。若 n 可能为 0（本题不会），初值要小心。
• 一句话：相邻差都满足条件的连续段，用"右指针扩不动就结算、i 跳段尾"一趟扫，O(n) 出答案。

2. 拜访（BFS · 最短路条数）

题干

给定一张 n × m 的城市地图，1 表示起点，2 表示终点，-1 表示不能走的障碍，0 表示可走空地。每次只能向上、下、左、右走一步。求从起点到终点的最短路径一共有多少条。（牛客题号 MT3 / 2323703，核心代码模式）

思路

分层 BFS 求最短路的条数是比"只求最短距离"高一层的题。做法是在 BFS 层序遍历时额外维护两个数组：

• dist[x][y]：起点到 (x,y) 的最短步数；
• cnt[x][y]：到达 (x,y) 的最短路条数。

BFS 的扩散规则里要区分"第一次到达"和"再次到达"：

• 第一次到达 (x,y)：dist = 当前步数 + 1，cnt[x][y] += cnt[当前格]（继承当前格的最短路条数），入队；
• 再次到达（dist 已算过）：只有当"从当前格再到这一步的距离 == 已记录的最短距离"时，才把 cnt[当前格] 累加到 cnt[x][y] 上（因为这也是一条最短路）；否则跳过（那条路更长，不算数）。

最终 cnt[x2][y2] 就是答案。（注意数组用 -1 初始化表示"未访问"。）

完整可运行代码

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
class Solution
{
    int n, m;
    int x1, y1, x2, y2;
    int dist[15][15];
    int cnt[15][15];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
    int bfs(vector<vector<int> >& CityMap)
    {
        memset(dist, -1, sizeof dist);          // -1 表示未访问
        for(int i = 0; i < 15; i++)
            for(int j = 0; j < 15; j++) cnt[i][j] = 0;
        queue<pair<int,int>> q;
        q.push({x1, y1});
        dist[x1][y1] = 0;
        cnt[x1][y1] = 1;
        while(q.size())
        {
            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 < n && y >= 0 && y < m && CityMap[x][y] != -1)
                {
                    if(dist[x][y] == -1)          // 第一次到达
                    {
                        dist[x][y] = dist[a][b] + 1;
                        cnt[x][y] += cnt[a][b];
                        q.push({x, y});
                    }
                    else if(dist[a][b] + 1 == dist[x][y])  // 再次到达且也是最短路
                    {
                        cnt[x][y] += cnt[a][b];
                    }
                }
            }
        }
        return cnt[x2][y2];
    }
public:
    int countPath(vector<vector<int> >& CityMap, int _n, int _m)
    {
        n = _n; m = _m;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                if(CityMap[i][j] == 1) x1 = i, y1 = j;
                else if(CityMap[i][j] == 2) x2 = i, y2 = j;
            }
        return bfs(CityMap);
    }
};
 
// ---- 本地测试驱动 ----
int main()
{
    int n, m; cin >> n >> m;
    vector<vector<int>> cm(n, vector<int>(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> cm[i][j];
    Solution so;
    cout << so.countPath(cm, n, m) << endl;
    return 0;
}

运行结果

输入：
3 3
1 0 0
0 0 2
0 0 0

输出（真机 g++ 15.2.0）：
3

输入：
3 3
1 -1 0
0 -1 2
0 0 0

输出：
1

第一组：从 (0,0) 到 (1,2) 的最短路步数是 3，条数 3（三条 L 形/直线组合）。第二组被两块障碍堵住，只剩一条绕行路径，条数 1。✓

详解答案与坑点

• 答案：第一组 3，第二组 1。
• 复杂度：O(n·m)，BFS 每格入队一次，四向扩展。
• 坑一（最重要）：cnt 的累加分两种情况，不能只累第一次。 在一个格子的最短路已经被算过之后，仍可能从另一条同样短的前序路径到达它，此时要 else if 判断"来自的距离是否等于已记录的最短距离"，相等才累加。写成只处理"第一次到达"，会漏数；写成无条件累加，会把更长的绕路也算进去。
• 坑二：dist 用 -1 初始化。 这里 -1 兼职"未访问"标记。如果初始化为 0（很多同学顺手），起点周围全变"已访问"，全乱套。务必 memset(dist, -1, ...)。
• 坑三：数组开成成员变量（类属性）。 dist/cnt 是 15×15 的类内成员，BFS 前要清空；cnt 在 C++ 里非全局、不保证自动清零，所以在 bfs 开头显式清零。
• 一句话：BFS 求最短路条数 = 分层 BFS + dist(距离，-1 初始) + cnt(条数) 双维护，关键是"再次到达且也是最短路"要额外累加。

3. 买卖股票的最好时机(四)（动态规划 · 状态机）

题干

给定 n 天的股票价格 prices[0..n-1]，你最多可以完成 k 笔交易（一买一卖算一笔，同一时刻最多持有一股，卖出后才能再买）。求你能获得的最大总收益。（牛客题号 DP33 / 2364648）

思路

这是经典股票问题的"限量交易版"，用有股票 / 无股票两个状态来做二维 DP：

• f[i][j]：第 i 天结束后，完成了 j 笔交易，当前持有股票的最大收益；
• g[i][j]：第 i 天结束后，完成了 j 笔交易，当前不持有股票的最大收益。

转移：

• f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i])：要么昨天就持有、今天不动；要么昨天不持有、今天买入（买不减少交易次数，买只是把"无股票"变"有股票"）。
• g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])：要么昨天就不持有、今天不动；要么昨天持有、今天卖出（卖出才算完成第 j 笔，所以要用 f[i-1][j-1]）。

初始化第 0 天：f[0][0] = -prices[0]（第 0 天买了股票），g[0][0] = 0；其它不合法的状态初始化为 -0x3f3f3f3f（一个足够小的"负无穷"，避免干扰 max）。注意这里用 -0x3f3f3f3f 而非 INT_MIN，就是为了防止 +prices[i] 时发生溢出。

还有个规模优化：交易次数不可能超过天数的一半，所以先 k = min(k, n/2)。

答案是 g 表最后一行（第 n-1 天）里某个 j 的最大值——因为我们最后一定是不持有股票的状态，而具体交易了几笔未知，取最大。

完整可运行代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 110;
int n, k, p[N];
int f[N][M], g[N][M];   // f: 持有股票; g: 不持有股票
 
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> p[i];
    k = min(k, n / 2);                        // 交易次数不会超过 n/2
    for(int j = 0; j <= k; j++) f[0][j] = g[0][j] = -0x3f3f3f3f; // 不合法状态初始化
    f[0][0] = -p[0]; g[0][0] = 0;
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);   // 持有 / 今天买入
            g[i][j] = g[i - 1][j];                             // 不持有，不动
            if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]); // 卖出+1笔
        }
    }
    int ret = 0;
    for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);   // 最后必为"不持有"
    cout << ret << endl;
    return 0;
}

运行结果

输入：
8 2
3 3 5 0 0 3 1 4

输出（真机 g++ 15.2.0）：
6

输入：
4 2
1 2 3 4

输出：
3

第一组 [3 3 5 0 0 3 1 4]、k=2：最优是第 1 笔在价位 3 买、5 卖（+2），第 2 笔在 0 买、4 卖（+4），总 6。第二组 [1 2 3 4] 虽然允许 2 笔，但一笔 1买4卖 就有 3，无法更高。✓

详解答案与坑点

• 答案：第一组 6，第二组 3。
• 复杂度：O(n·k)，空间 O(n·k)（可滚动到 O(k)，为可读性这里用二维）。
• 坑一（最关键，方向感）："买"不减交易次数，"卖"才加一次。 判断是否完成"一笔"的是卖出。因此 f 的转移用同一天 j 的 g[i-1][j]，而 g 的卖出分支用 f[i-1][j-1]。把"买"当成加次数是一定要避开的经典错误。
• 坑二：初始化的"负无穷"选值。 不合法状态用 -0x3f3f3f3f 而不用 INT_MIN，因为后面有 + p[i]，INT_MIN + 正数 会溢出产生伪装成合法最大值的垃圾数据。0x3f3f3f3f 折半足够小又不溢出，是王道。
• 坑三：k = min(k, n/2) 的优化。 交易次数超过 n/2 就必然有重叠买卖（无意义），剪掉可显著降复杂度，别漏。
• 坑四：答案在 g 的最后一行取最大。 最终状态一定是不持有股票，但不知道最优是循环了几笔，所以要扫一遍 j。
• 一句话：股票限量交易 = "持有/不持有 × 交易次数"二维状态机，记住"卖才计数、负无穷别用 INT_MIN、k 先 min 到 n/2"。

Day04：贪心、哈希、区间 DP

Day04 三题口味各不相同：AOE 单体是道"想清楚谁是主角"的贪心；kotori 和 n 皇后是哈希标记坑题；取金币是区间 DP 的招牌模型——戳气球。

1. AOE还是单体？（贪心）

题干

游戏里有 n 只怪物，第 i 只的血量是 a[i]。每次攻击你可以在两种里选一种：单体攻击（对一只怪造成 1 点伤害），或 AOE（对所有怪各造成 1 点伤害，但 AOE 总共最多只能用 x 次）。问：清空所有怪物，最少需要造成多少点总伤害？（牛客题号 938754）

思路

先看一个朴素想法：如果只用单体，总伤害就是所有血量之和。而 AOE 的好处是"同时打一排"，但坏处是血太少的怪提前被打死后，后续 AOE 对它就是浪费。想要 AOE 不吃亏，得让 AOE 的次数"不落在已死亡的怪上"。

贪心结论：把血量排序，答案等于最大的 x 只怪的血量之和。直觉是——AOE 的价值在于"帮所有怪一起扛固定次数的伤害"，而这个"一起扛"的天花板由"体质最弱的豪门"决定。最省的做法是：用单体处理掉较小的（"陪跑"的）、保证 AOE 的 x 次全部砸在血量最大的那 x 只连续区间上，这样 AOE 一次都不浪费。

代码上是这样表达的（等价化简后就是"取最大 x 项和"）：

• 排序；
• index = max(0, n - x)（若 x >= n，让 index 落到 0，即全部当单体处理）；
• ret = arr[index] * x + Σ(arr[i] - arr[index])，其中累加从 index+1 到 n。

本质上一化简：ret = 最大的 x 个数之和。

完整可运行代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, x;
int arr[N];
int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr + 1, arr + 1 + n);
    long long ret = 0;
    int index = max(0, n - x);       // 处理 x 过大的情况：x>=n 时 index 取 0
    ret += arr[index] * x;           // AOE 覆盖的公共部分（等价于"保底贡献 x 份基准血"）
    for(int i = index + 1; i <= n; i++)
        ret += arr[i] - arr[index];  // 比基准多的部分用单体补足
    cout << ret << endl;
    return 0;
}

运行结果

输入：
6 2
1 2 3 4 5 6

输出（真机 g++ 15.2.0）：
11

输入：
6 7
1 2 3 4 5 6

输出：
21

第一组排序后 1 2 3 4 5 6，index = 6-2 = 4，ret = 5*2 + (6-5) = 10 + 1 = 11（正好等于最大的 2 项 5+6）。第二组 x=7 > 6，index = max(0, -1) = 0。注意这里 arr 是从下标 1 开始读入的，所以 arr[0] 是未输入的哨兵 0：ret = 0*7 + Σ_{i=1..6}(arr[i] - 0) = 1+2+3+4+5+6 = 21，正好退化成"全部用单体"的总血量，符合直觉——AOE 次数够随意用，最省就是全单体。

详解答案与坑点

• 答案：第一组 11，第二组 21。
• 坑一（不是所有血都能吃到 AOE，血的排序决定了"谁会拖后腿"）。 想明白"AOE 的总次数必须 ≤ 最小的存活贡献才不浪费"，从而让 AOE 作用在最大的那 x 只上。这是本题的贪心灵魂，别死背公式。
• 坑二：数据类型用 long long。 血量总和可能很大，arr[i] - arr[index] 这种减法本身还好，但 ret 累加要 LL。
• 坑三（很多人栽）：输入下标从 1 开始，arr[0] 是哨兵 0。 当 x >= n 时 index = 0，此时 ret 退化成"全血量和"，正确；如果你把输入存到 arr[0..n-1] 但下标算错一位，会出现差一个 arr[0] 的偏差。细心对齐下标即可。

2. kotori和n皇后（哈希表）

题干

按顺序放置 k 个皇后，第 i 次放的皇后在坐标 (x, y)（坐标可能很大）。一旦某个皇后与它之前的某个皇后互相攻击（同行、同列或同一条对角线），就发生了"冲突"。你不需要管冲突之后的皇后。现在给你 t 组询问，每组给一个 i，问："当已经放置了第 i 个皇后之后，是否已经出现过冲突？"（牛客题号 500565）

思路

经典的判 N 皇后冲突，用四个哈希集合分别记录已经被占的：行 y、列 x、主对角线 y - x、副对角线 y + x。因为主对角线上任意两格的 y - x 相同、副对角线上任意两格的 y + x 相同，所以只要看当前皇后的四个值有没有和集合里已有的撞上，就能 O(1) 判断是否冲突。

这题的"坑爹"之处在查询阶段：题目问的是"放置完第 i 个之后累看有没有冲突"，本质是问 i 是否大于等于第一次冲突发生的下标。所以我们在放置时只记录"第一次冲突发生在第几个皇后"（ret），后续的皇后只要 ret 已定就直接跳过不再判断；查询时拿 i 和 ret 一比即可，而不是对每个查询重新模拟放置。

完整可运行代码

#include <iostream>
#include <unordered_set>
using namespace std;
typedef long long LL;
int k, t;
int ret = 1e5 + 10;     // 第一次出现互相攻击的是第几个皇后（初值远大于 k）
int main()
{
    unordered_set<LL> row;    // 已占的行 y
    unordered_set<LL> col;    // 已占的列 x
    unordered_set<LL> dig1;   // 已占的主对角线 y - x
    unordered_set<LL> dig2;   // 已占的副对角线 y + x
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        LL x, y; cin >> x >> y;
        if(ret != 1e5 + 10) continue;                  // 已有冲突，后面的不必再判
        if(row.count(y) || col.count(x)
           || dig1.count(y - x) || dig2.count(y + x))
            ret = i;                                    // 对冲，记下第一次的下标
        row.insert(y); col.insert(x);
        dig1.insert(y - x); dig2.insert(y + x);         // 无论冲不冲都要占位
    }
    cin >> t;
    while(t--)
    {
        int i; cin >> i;
        if(i >= ret) cout << "Yes" << endl;            // 放完第 i 个后已有冲突
        else cout << "No" << endl;
    }
    return 0;
}

运行结果

输入：
3
1 1
2 2
3 3
3
1 2 3

输出（真机 g++ 15.2.0）：
No
Yes
Yes

三个皇后都在主对角线 (1,1)(2,2)(3,3)：第 1 个放完没事（No）；第 2 个放上主对角线即冲突（Yes）；第 3 个之后更是有冲突（Yes）。✓

详解答案与坑点

• 答案：三个查询依次 No / Yes / Yes。
• 复杂度：O(k + t)，每个皇后、每个查询都是 O(1) 哈希操作。
• 坑一（本题最大的坑，务必读懂题意）：查询问的是"等价于第 i 个皇后及之后是否已有冲突"，答案是 i >= ret 判 Yes。 很多人把查询当成"重新模拟放前 i 个皇后看第 i 个自己是否被攻击"，那样 i == 第一次冲突下标 的判断会错（前者答案是 Yes，后者若理解为"第 i 个皇后恰好是冲突者"也碰巧 Yes，但后续的 i 更大会被判错）。记一个 ret，查询直接比大小，是最省也最不容易错的写法。
• 坑二：坐标可能很大，一定要用 long long。 x、y、y-x、y+x 都可能超出 int，四个集合的类型都开 LL，否则 y - x 溢出导致乱判。
• 坑三：即使当前皇后不冲，也要把它占的四个位置 insert。 别在 if 冲突分支里才 insert，否则会漏占位导致后续误判。
• 一句话：四个哈希（行/列/两条对角线）O(1) 判冲突，但真正送命的是"先记第一个冲突下标，查询直接比 i >= ret"这段题意转译，务必读懂。

3. 取金币（区间 DP · 戳气球）

题干

有一排金币，第 i 个金币的价值是 v[i]。每次你取走一个金币，取走它时能获得金币 = 它左边相邻那个金币 × 它自己 × 它右边相邻那个金币（即用当前相邻三个数的乘积当收益）。取走它之后，左右相邻的金币会"并拢"。把金币取到（相当于是取走全部金币的某种顺序）……请计算一共能获得的最大金币总数。（牛客题号 NC393 / 2433134）

说明：这类题的经典等价题是"戳气球"。为了方便处理边界，我们会在数组最前面和最后面各补一个值 1，表示"空位/边界"的存在。

思路

这是区间 DP 的招牌题，状态定义为：dp[i][j] 表示"把 [i, j] 这段区间内的金币全部取走，能获得的最大金币数"。

考虑把 [i, j] 里最后一个被取走的那个位置 k（它一定是区间内某一次"拿走"的主角）：在取走它时，它左右还活着的邻居，一个是最左边界的 arr[i-1]，一个是最右边界的 arr[j+1]，所以这一步的收益是 arr[i-1] * arr[k] * arr[j+1]。而在此之前，[i, k-1] 和 [k+1, j] 已经取完，它们互相独立，收益分别计入 dp[i][k-1] 和 dp[k+1][j]。

dp[i][j] = max over k in [i..j] of
           ( dp[i][k-1] + dp[k+1][j] + arr[i-1] * arr[k] * arr[j+1] )

枚举区间长度由内向外（左端点 i 从大到小）、每个区间枚举 k，三重循环即可。首尾补 1 让 arr[i-1]、arr[j+1] 在边界处依然有意义。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
    int arr[110] = { 0 };
    int dp[110][110] = { 0 };   // dp[i][j]：取完 [i,j] 区间金币的最大收益
public:
    int getCoins(vector<int>& coins)
    {
        int n = coins.size();
        arr[0] = arr[n + 1] = 1;                       // 首尾补边界 1
        for(int i = 1; i <= n; i++) arr[i] = coins[i - 1];
        for(int i = n; i >= 1; i--)                    // 左端点从大到小（先小区间）
        {
            for(int j = i; j <= n; j++)                // 右端点
            {
                for(int k = i; k <= j; k++)            // 枚举区间内最后取走的 k
                {
                    dp[i][j] = max(dp[i][j],
                        dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);
                }
            }
        }
        return dp[1][n];
    }
};
 
// ---- 本地测试驱动 ----
int main()
{
    int n; cin >> n;
    vector<int> c(n);
    for(int i = 0; i < n; i++) cin >> c[i];
    Solution so;
    cout << so.getCoins(c) << endl;
    return 0;
}

运行结果

输入：
4
3 1 5 8

输出（真机 g++ 15.2.0）：
167

这组 [3,1,5,8] 是"戳气球"的原题样例，最大收益 167。✓

详解答案与坑点

• 答案：167。
• 复杂度：O(n³)，区间数量 O(n²)、每区间枚举 k O(n)，空间 O(n²)。注意 dp 开 [110][110] 应对 n≤100 左右。
• 坑一（核心：枚举的是"最后一个取走的位置"，不是第一个）。 之所以要从"最后取走的 k"入手，是因为只有"最后取走"时它的两个邻居才是确定不变的 arr[i-1] 和 arr[j+1]（左右边界）。如果从"最先取走"思考，边界会来回变化，DP 无法成立。
• 坑二：填表顺序要保证子区间先算好。 因为 dp[i][j] 依赖更短的区间 dp[i][k-1]、dp[k+1][j]，所以左端点 i 必须从大到小枚举（外层从 n 往下走），否则长区间会用到还没算的短区间值。
• 坑三：首尾补 1。 把 arr[0] 和 arr[n+1] 设成 1，是为了让最左/最右金币被"最后取走"时，它的外侧邻居是冷冰冰的 1，不影响乘积。忘补给会越界或算错。
• 一句话：区间 DP 先补边界 1，再按"最后取走的 k"枚举中转点，三层循环填出 dp[1][n]。

Day05：转置模拟、DFS 剪枝、接雨水

Day05 从"有没有搞错，这也算题"的矩阵转置，到加剪枝的全排列，再到接雨水的双数组预处理，难度缓缓爬坡。

1. 矩阵转置（模拟）

题干

给定一个 n 行 m 列的整数矩阵，输出它的转置（一个 m 行 n 列的矩阵，满足 ret[i][j] = arr[j][i]）。（牛客题号 BC138 / 618636）

思路

完全纯模拟，抓住下标关系即可：转置后第 i 行第 j 列 = 原矩阵第 j 行第 i 列。所以按"转置后的"行列去遍历输出：for i in 0..m-1、for j in 0..n-1，输出 arr[j][i]。难点为零，注意别把行列数搞反就行。

完整可运行代码

#include <iostream>
using namespace std;
const int N = 15;
int n, m;
int arr[N][N];
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> arr[i][j];
    for(int i = 0; i < m; i++)           // 转置后行数变为 m
    {
        for(int j = 0; j < n; j++)       // 转置后列数变为 n
        {
            cout << arr[j][i] << " ";    // ret[i][j] = arr[j][i]
        }
        cout << endl;
    }
    return 0;
}

运行结果

输入：
3 3
1 2 3
4 5 6
7 8 9

输出（真机 g++ 15.2.0）：
1 4 7
2 5 8
3 6 9

详解答案与坑点

• 答案：见上方 3×3 转置输出。
• 坑一：外层循环用 m、内层用 n。 因为转置结果的行列会互换，很多人习惯性外层 n 内层 m，结果行列颠倒。先想清楚输出矩阵的形状再写循环。
• 坑二：如果题目输入是"一行一个数"或要求行尾无空格，注意输出格式。 本解法行内用空格分隔、行末换行，是通用写法；若 OJ 严格到行尾空格，要自行处理。
• 一句话：送分题，只要记住 ret[i][j] = arr[j][i] 且行列交换，就不会写错。

2. 四个选项（DFS ＋ 剪枝）

题干

一套卷子有 12 道选择题，每道题从 A、B、C、D 四个选项中选一个。已知每个选项出现的总次数分别是 cnt[1]、cnt[2]、cnt[3]、cnt[4]（即整卷里 A/B/C/D 各出现几次，次数之和为 12），以及 m 对"第 x 题和第 y 题答案必须相同"的约束。问：一共能组合出多少种合法的答案分布？（牛客题号 848875）

思路

直接枚举 12 道题的答案，但当选项次数约束 + "必须相同"约束同时出现时，要甩两把剪枝刀：

• 次数剪枝：cnt[i] == 0 就说明选项 i 的次数已经用完，这一位不能填 i；
• 相同约束剪枝：填第 pos 题时，扫一遍所有"与 pos 必须相同"的前面的题，如果某个必须相同的题已经被填了不同的选项，当前这个 cur 就不合法，跳过。

用 isSame(pos, cur) 实现第二把剪枝。DFS 从第 1 题填到第 12 题，全部填满（pos > 12）就 ret++。注意每层都要回溯恢复 cnt 和 path。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
int cnt[5];                  // 每个选项还能用几次
int m;
bool same[13][13];           // same[i][j]：题 i 与题 j 答案必须相同
int ret;
vector<int> path;            // path[pos]：第 pos 题填的选项
 
// 检查：与第 pos 题"必须相同"的题是否都已经填了 cur
bool isSame(int pos, int cur)
{
    for(int i = 1; i < pos; i++)
    {
        if(same[pos][i] && path[i] != cur) return false;
    }
    return true;
}
void dfs(int pos)
{
    if(pos > 12) { ret++; return; }        // 12 题填完，一种合法分布
    for(int i = 1; i <= 4; i++)
    {
        if(cnt[i] == 0) continue;          // 该选项次数用光
        if(!isSame(pos, i)) continue;      // 与前面必须相同的题冲突
        cnt[i]--; path.push_back(i);
        dfs(pos + 1);
        path.pop_back(); cnt[i]++;         // 回溯，恢复现场
    }
}
int main()
{
    for(int i = 1; i <= 4; i++) cin >> cnt[i];
    cin >> m;
    while(m--) { int x, y; cin >> x >> y; same[x][y] = same[y][x] = true; }
    path.push_back(0);                     // 占位符，让 path 下标从 1 开始
    dfs(1);
    cout << ret << endl;
    return 0;
}

运行结果

输入：
3 3 3 3
1
1 2

输出（真机 g++ 15.2.0）：
67200

输入：
3 3 3 3
0

输出：
369600

第二组无任何"必须相同"约束：12 题每个选项恰好 3 次，方案数 12! / (3!^4) = 479001600 / 1296 = 369600。✓ 第一组加一条"第 1、2 题必须相同"后骤降为 67200。

详解答案与坑点

• 答案：第一组 67200，第二组 369600。
• 复杂度：DFS 全排列 + 双剪枝，实际运行远优于裸 4^12，是 NFA 可接受范围。
• 坑一（两把剪枝缺一不可）。 只做次数剪枝会在约束条件下多算不合法分布；只做"必须相同"剪枝会忽略"某个选项次数超支"。两个都要，才保证不漏不重复。
• 坑二：isSame 里访问的是"此前已填"的 path[i]，所以只用扫 i < pos。 填当前位只看"locked 关系里已经定下来的题"是否冲突；别扫后面的（还没填）。
• 坑三：回溯要完整。 cnt[i]--、path.push_back 在做完 dfs 后都要还原，漏掉一个 cnt[i]++ 就错一片。
• 一句话：全排列枚举 + "选项次数"与"必须相同"两把剪枝 + 忘记回溯就全盘皆输，这是标准 DFS。

3. 接雨水问题（预处理双数组）

题干

给定 n 个非负整数表示 n 根柱子的高度，柱子宽度都为 1。问下大雨后，这两根柱子之间能接到多少单位的雨水。（牛客题号 1002045）

思路

对每一根柱子单独看它头顶能存多少水。一根柱子能存的水，取决于它左边所有柱子中最高的那根和它右边所有柱子中最高的那根中较矮的那一边 —— 水的顶面被短板限制，所以：

每个位置能存的水 = min(左侧最大高度, 右侧最大高度) - 自身高度   （若为正）

做法是预处理两个数组：

• left[i]：[0..i] 里柱子的最大高度（从左往右递推）；
• right[i]：[i..n-1] 里柱子的最大高度（从右往左递推）。

然后跳过首尾两根柱子（存不了水），对 i = 1..n-2 累加 min(left[i], right[i]) - height[i]。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        vector<int> left(n), right(n);
        left[0] = height[0];
        for(int i = 1; i < n; i++) left[i] = max(left[i - 1], height[i]);       // 左侧最大
        right[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], height[i]); // 右侧最大
        int ret = 0;
        for(int i = 1; i < n - 1; i++)
            ret += min(left[i], right[i]) - height[i];   // 每根柱子头顶能存的水
        return ret;
    }
};
 
// ---- 本地测试驱动 ----
int main()
{
    int n; cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];
    Solution so;
    cout << so.trap(h) << endl;
    return 0;
}

运行结果

输入：
12
0 1 0 2 1 0 1 3 2 1 2 1

输出（真机 g++ 15.2.0）：
6

这是接雨水的经典样例，答案是 6。✓

详解答案与坑点

• 答案：6。
• 复杂度：O(n) 三趟，空间 O(n) 两个辅助数组。
• 坑一（本质）：是"短板决定水位"，取的是两边的 max 再 min，不是另一边的某个值。 容易误写成 left[i] - height[i] 或 right[i] - height[i]，那是错的。一定是 min(left, right) - self。
• 坑二：首尾柱子不参与累加（i 从 1 到 n-2）。 最左/最右柱子一侧没有可接水的边界，跳过。
• 坑三：算出的差值可能为负吗？ 由于 left[i]、right[i] 都至少 ≥ height[i]（包含自身），所以 min(left[i], right[i]) ≥ height[i]，差值恒非负，不用特判负值。
• 一题多解（单调栈 / 双指针）：接雨水还有"单调递减栈"和"首尾双指针"的做法（双指针能省掉辅助数组、空间 O(1)）。预处理双数组是最容易理解、最不易写错的一版，笔试作为首选。
• 一句话：对每根柱子，它的积水由"左右各自最高、再取矮边"决定，预处理 left/right 双数组后 O(1) 累加即可。

Day06：平均值贪心、栈排序、中位数窗口

最后一天，一是求均值范围的贪心，二是"字典序最大出栈序列"的经典栈贪心，三是"中位数滑窗"综合题。收尾带一点综合味。

1. 疯狂的自我检索者（贪心）

题干

一本书里收录了 n 个作品，已经知道其中 n - m 个作品的评分（是确定的整数），而剩下 m 个作品的评分未知，据信是 1 到 5 之间的整数。请你分别求出这 n 个作品的平均分的最小可能值和最大可能值，各输出保留 5 位小数。（牛客题号 955142）

思路

贪心核心一句话：未知的 m 个评分，取最小（1）时平均分最小，取最大（5）时平均分最大。 因为其他 n - m 个已定，平均分只由这 m 个扰动：

• 最小平均 = (sum_known + m × 1) / n；
• 最大平均 = (sum_known + m × 5) / n。

读入时只把已知的 n - m 个数累加进 sum，跳过未知的，然后套公式即可。

完整可运行代码

#include <iostream>
using namespace std;
int n, m;
int main()
{
    cin >> n >> m;
    int sum = 0;                            // 已知的 n-m 个评分的和
    for(int i = 0; i < n - m; i++) { int a; cin >> a; sum += a; }
    printf("%.5lf %.5lf\n", (sum + m) * 1.0 / n,   // 未知 m 个全取最小值 1
           (sum + m * 5) * 1.0 / n);              // 未知 m 个全取最大值 5
    return 0;
}

运行结果

输入：
5 2
3 4 5

输出（真机 g++ 15.2.0）：
2.80000 4.40000

已知 3+4+5=12，min 平均 (12+2)/5 = 2.80，max 平均 (12+10)/5 = 4.40。✓

详解答案与坑点

• 答案：2.80000 4.40000。
• 坑一：只加已知的 n-m 个，别把未知的也当成 0/5 提前算进去。 未知的是"待定变量"，用下界 1 / 上界 5 各做一遍即可。
• 坑二：保留 5 位小数，"%.\5 lf"？——正确的是 "%.5lf"。
• 坑三：* 1.0 / n 保证浮点除法，不要 sum/n（整数除法直接截断成 0/1 之类）。
• 一句话：均值范围的端点就是"未知数全取边界"，一道不要有小九九的贪心。

2. 栈和排序（栈 ＋ 贪心）

题干

给定一个 1 ~ n 的排列作为入栈顺序（按顺序依次入栈，入栈过程中可以随时栈顶出栈）。求按字典序最大的出栈序列。（牛客题号 NC115 / 1024794，核心代码模式）

思路

贪心思路：每次尽可能让"当前还没出过、且能出栈的最大元素"先出栈。 维护一个 aim，表示"截至现在为止，还没出过栈的最大元素"（初始 aim = n）。扫描入栈序列，把元素入栈并用哈希 hash[x] 记录"值 x 已进栈"；每进一个元素，就把 aim 往下拉——只要 hash[aim] 为真（说明最大值已经进过栈了），就不断 aim-- 找到"尚未进栈的最大值"；然后把所有栈顶 >= aim 的元素弹出接到答案里（因为它们是当前能弹的最大那批）。

理解要点：aim 始终是"尚未进栈的最大数"。当 aim 已经进栈，说明从 aim 到 n 的所有更大数字都已经进过栈了——那么此刻一口气把它们从栈里倒出来，就是字典序最大的选择。处理完全部入栈元素，栈里剩下的按 LIFO 全部弹出。

完整可运行代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
class Solution
{
public:
    vector<int> solve(vector<int>& a)
    {
        int n = a.size();
        stack<int> st;
        bool hash[50010] = { 0 };      // hash[x]：元素 x 是否已经入栈
        int aim = n;                   // 当前还没进栈的最大值
        vector<int> ret;
        for(auto x : a)
        {
            st.push(x);
            hash[x] = true;
            while(hash[aim]) aim--;                           // 更新 aim：aim 已进栈就往下走
            while(st.size() && st.top() >= aim)               // 顶部能弹就弹（都是大数）
            {
                ret.push_back(st.top());
                st.pop();
            }
        }
        return ret;
    }
};
 
// ---- 本地测试驱动 ----
int main()
{
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    Solution so;
    auto r = so.solve(a);
    for(size_t i = 0; i < r.size(); i++) cout << (i ? " " : "") << r[i];
    cout << endl;
    return 0;
}

运行结果

输入：
5
2 1 5 3 4

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

走一遍：入 2（aim=5，top2<5 不弹）→ 入 1（不弹）→ 入 5（hash5→aim 降到 4；top5≥4 弹 5）→ 入 3（aim=4，top3<4 不弹）→ 入 4（hash4→aim 降到 0；把所有 top≥0 的 4,3,1,2 全部弹出）。结果 5 4 3 1 2。✓

详解答案与坑点

• 答案：5 4 3 1 2。
• 复杂度：O(n)，每个元素入栈一次、出栈一次。
• 坑一（核心机制）：aim 是"还没进栈的最大值"，不是"还没出栈的最大值"。 while(hash[aim]) aim-- 找的是"从未入过栈"的最大值。如果 aim 已经进过栈（或被弹掉），它之后就不能再"期待它出现"了，所以要往下找。把意思理解成"还没进栈的最大"才是对的。
• 坑二：两个 while 的顺序不能反。 先更新 aim（决定"这一批能弹的上限"），再执行 while(st.top() >= aim) 弹出。顺序反过来会导致该弹的没弹、误弹小的。
• 坑三：最后栈里余下的元素在 for 结束后自然留在答案末尾（因为 aim 已到 0，st.top() >= 0 恒成立，会在某个时刻被倒光——本例在倒数第二步就弹完了）。若真想明确，可在循环外再补一个 while(st.size()) 弹出，更稳。
• 一句话：用 aim 记录"还没进栈的最大值"，每入栈一个就更新，再"尽量弹栈顶的大数"，就是字典序最大。

3. 加减（枚举 ＋ 前缀和 ＋ 滑动窗口）

题干

给定一个长度为 n 的整数数组，每次操作你可以把数组中任意一个数 +1 或 -1。求经过不超过 k 次操作后，数组中最长的"所有元素都相等"的连续子段最长可以有多长。（牛客题号 1946143）

思路

这是"把一段元素通过 ±1 变成同一个值，花费尽量小"的经典优化题。思路是：

1. 排序。要把一段数字变成相等，一个核心的好处是"凑中位数最省"。对连续区间 [l, r]，把它们全部变成中位数 arr[mid]（mid=(l+r)/2）所需的操作次数最少。
2. 用前缀和快速算把一个区间 [l,r] 全部变成 arr[mid] 的代价 cal(l,r)：

cost = (mid - l) * arr[mid] - (sum[mid-1] - sum[l-1])   // 左半部分补到中位
     + (sum[r] - sum[mid]) - (r - mid) * arr[mid]       // 右半部分降到中位

（即左半少了就补、右半多了就砍，都朝中位数聚拢。）

3. 滑动窗口：right 逐位右扩，若 cost > k 就 left++ 收缩窗口，直到窗口内代价 ≤ k；用窗口长度更新答案 ret = max(ret, right-left+1)。

完整可运行代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, k;
LL arr[N], sum[N];              // sum: 前缀和数组
 
// 把区间 [l, r] 全部变成中位数 arr[mid] 需要多少次操作
LL cal(int l, int r)
{
    int mid = (l + r) / 2;
    return (mid - l - r + mid) * arr[mid] - (sum[mid - 1] - sum[l - 1])
           + (sum[r] - sum[mid]);
}
 
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr + 1, arr + 1 + n);                 // 排序后中位数即"最优共同值"
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i];   // 前缀和
 
    int left = 1, right = 1, ret = 1;
    while(right <= n)
    {
        LL cost = cal(left, right);
        while(cost > k)                         // 代价超支就收缩左端
        {
            left++;
            cost = cal(left, right);
        }
        ret = max(ret, right - left + 1);       // 窗口合法，更新答案
        right++;
    }
    cout << ret << endl;
    return 0;
}

运行结果

输入：
5 4
1 5 5 5 5

输出（真机 g++ 15.2.0）：
5

输入：
5 1
1 5 5 5 5

输出：
4

第一组：把 1 变成 5 需要 4 次操作，k=4 够，整段 [1..5] 都能变成 5，答案 5。第二组 k=1：把 1 变 5 要 4 次不够，只能保住后面四个 5，答案 4。✓

详解答案与坑点

• 答案：第一组 5，第二组 4。
• 复杂度：O(n log n)（排序）+ O(n)（滑窗），cal 是 O(1)。
• 坑一（最优共同值是中位数，不是均值）。 把一段数都变成同一个值使总操作最小，最优是中位数而不是平均值（均值会在有异常值时不最省）。这是本体的关键洞察，很多人在均值/中位数间翻车。
• 坑二：cal 的公式别漏项。 左半补差 (mid-l)*arr[mid] - (sum[mid-1]-sum[l-1])，右半砍差 (sum[r]-sum[mid]) - (r-mid)*arr[mid]，写成 (mid - l - r + mid)*arr[mid] 是把两项合并。下标 mid-1、l-1 都要配对好，边界（l=1 时 sum[0]=0）天然成立。
• 坑三：需要排序，窗口内才保证"下标靠中间的元素是全局较小/较大的那批"。 不排序，"中位数"就没意义。所以排序 + 前缀和 + 滑窗三者缺一不可。
• 一句话：排序 → 前缀和快速算"变中位数的代价" → 滑动窗口在代价 ≤ k 内尽量拉长，三步拿下。

本周考点一图流

十八题敲完，把"题型 → 核心套路 → 复杂度 → 必背易错"压成一张表，考前 30 秒扫一眼：

把这张表钉进脑子里，这周再遇到"看起来很像"的题，你就能一键匹配到对的模板。

这一周十八道题刷完，主线其实非常清楚：概率题在教你"翻译成数学公式再编码"；双指针/滑动窗口在教你"一趟扫描、只进不退地省掉内层循环"；BFS 在教你"层序遍历里附加维持额外信息（距离、条数）"；贪心在教你"先想清楚谁是决定胜负的变量，再决定取哪些"；DFS 在教你"全排列枚举 + 剪枝 + 回溯恢复现场"；DP 的三道（LNDS、股票、取金币）则分别对应"贪心优化 DP""状态机 DP""区间 DP"三棵不同的模板树。

老规矩，还是那句掏心窝的话：你看懂了 ≠ 你会 AC。 上面每一份代码都是一行不落地能编译的完整程序，运行结果也是我本机 g++ 15.2.0 一笔一笔测出来的。请你务必本地 Build & Run 一遍，把我贴的输入原样敲进去，检查输出是不是和我贴的一模一样；对得上，再把每个易错点抄进你的错题本。尤其是这几类反复出现的坑——"下标越界"（高音、转置）、"类型溢出"（抽卡、差值、AOE）、"滚动/期望值必须用旧值"（汉诺塔）、"负无穷别用 INT_MIN"（股票）、"容斥求区间个数"（薯条、接雨水）、"排序后才是中位数/相邻差"（加减、差值）——它们几乎是笔试厂商的心头好。

如果能坚持到这里，你这一周的板斧就又硬了一截。下一周我们会继续往更综合、更考察"多算法叠加"的专题上冲。先把这一周练扎实，路还长，咱们一步一步来。