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

先跟各位把话说明白：这一周的学习，主角是编程题。每周强训的节奏其实是"选择题＋编程题"两条线并进的，但选择题是穿插在考点里随堂消化的，真正需要你"跪下来一行一行抠代码"的是这一摞编程题。所以本篇文章就当周的编程题做一次彻底的精讲，把每一道从"读完题干"到"AC 收下一血"的完整过程摆给你看——题在案前，先别急着抄，跟着我想一遍，然后自己敲一遍，最后对答案。这才是强训该有的样子。

本周一共 6 天、15 道题，题目分布大概这样：

• Day13：牛牛冲钻五（模拟）、最长无重复子数组（滑动窗口）、重排字符串（贪心＋构造）
• Day14：乒乓球筐（哈希）、组队竞赛（贪心）、删除相邻数字的最大分数（线性 DP）
• Day15：平方数（数学）、分组（二分答案）、拓扑排序模板（图论）
• Day16：字符串替换（模拟）、神奇数（数学＋枚举）、DNA 序列（定长滑动窗口）
• Day17：小乐乐改数字（模拟）、十字爆破（预处理）、比那名居的桃子（前缀和／窗口）
• Day18：压缩字符串（双指针）、chika 和蜜柑（排序 TopK）、01 背包（动态规划）

看出来没有？虽然每天 3 题，但考点高度集中、刻意地在"同类反复捶打"。模拟、滑动窗口、贪心、动态规划、二分、图论这些是笔试的高频主力，这一周就是让你把这几板斧练到条件反射。本文下面按天逐题拆解。每题都给全闭环：题干 → 思路 → 完整可编译运行的代码（逐行注释）→ 运行结果（我真机跑给你看）→ 详解答案与易错坑。

Day13：从模拟到抠细节

Day13 的题是整套卷子的氛围组，也是热身组。第一道是纯模拟，第二道是滑动窗口的招牌题，第三道是贪心构造的经典模型。三题难度递进，一口气做完你会很有成就感。

1. 牛牛冲钻五（模拟）

题干

牛牛在一次"冲钻五"的对局里，记下了自己每一场的胜负，一共要打 t 场（多组数据）。每场给出这里的牌面长度 n、一个由 W（Win，赢）和 L（Lose，输）组成的字符串 s，以及连赢加成分 k。

计分规则是这样的：遇到 W 得 1 分——但是如果这一位是 W，而且它前面恰好连着两个位置也是 W（即 s[i-1]、s[i-2] 都是 W），那么这一位就不是得 1 分，而是直接拿到连赢加成 k 分；遇到 L 扣 1 分。 请你输出这一场的最终得分。

注意这里 W/L 的输入，n 就是字符串长度，最后一位看的就是整个字符串从头到尾扫一遍。

思路

纯粹的模拟题，没有任何数据结构，也没有任何"聪明的优化"，就是"它怎么着就怎么来"。唯一要留意的是边界：当 i 还没满 2 的时候（i-1 < 0 或 i-2 < 0），都不存在"前面连续两个 W"这回事，这时候就算当前是 W 也只能得 1 分。这是这类小题最爱藏坑的地方——不加 i-1>=0 && i-2>=0 的下标保护，一上来就数组越界。写的时候把边界条件写对，这一题就稳了。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
int t, n, k;   // t 组数据；n 是本场长度；k 是连赢加成
string s;      // 本场的胜负串
 
int fun()
{
    int ret = 0;                     // 最终得分
    for(int i = 0; i < s.size(); i++) // 从头到尾扫一遍
    {
        if(s[i] == 'L')
        {
            ret--;                   // 输了，扣 1 分
        }
        else // s[i] 是 'W'
        {
            // 关键：必须保证 i-1、i-2 都存在（下标不能越界），
            // 且这两个位置都是 'W'，才算"连赢加成"，得 k 分
            if(i - 1 >= 0 && i - 2 >= 0 && s[i - 1] == 'W' && s[i - 2] == 'W')
            {
                ret += k;
            }
            else
            {
                ret += 1;            // 普通赢一局，得 1 分
            }
        }
    }
    return ret;
}
 
int main()
{
    cin >> t;                    // 读组数
    while(t--)
    {
        cin >> n >> k >> s;      // 读长度、加成、胜负串（n 在题目中保证等于 s 长度）
        cout << fun() << endl;
    }
    return 0;
}

运行结果

我构造两组真实跑一遍的样例验证：

输入：
2
6 3
WWLWWL
6 3
WWWWW

输出（真机）：
2
11

第一组 WWLWWL、k=3，逐位算一遍：

• i=0 是 W，前面没有两格 → 得 1 分，累加 1；
• i=1 是 W，i-2=-1 越界 → 得 1 分，累加 2；
• i=2 是 L → 得 -1 分，累加 1；
• i=3 是 W，前一位 i=2 是 L，不是连赢 → 得 1 分，累加 2；
• i=4 是 W，它的 i-2=2 是 L，不是连赢 → 得 1 分，累加 3；
• i=5 是 L → 得 -1 分，累加 2。

所以第一组答案 2。✓

第二组 WWWWW、k=3，五个 W：

• i=0 得 1、i=1 得 1，累加 2；
• 从 i=2 开始，它的前两位 i-1、i-2 都是 W，满足连赢加成，所以 i=2、3、4 这三位各自得 +k=3，共 3×3=9；
• 总分 2 + 9 = 11。

所以第二组答案 11。✓

这里给个小提醒：如果你拿 WWWWWW（六个 W）去跑，由于 i=2..5 共四位吃加成 4×3=12，再算上头两位 1+1，结果是 14——千万别跟我上面五个 W 的 11 搞混。写代码、对答案，永远以真机跑出来的输出为准，别只信脑子里的手算。

详解答案与坑点

• 答案：第一组 WWLWWL 答案是 2，第二组 WWWWW 答案是 11。
• 最大的坑：下标保护。i - 1 >= 0 && i - 2 >= 0 必须写，否则 i 取 0、1 时访问 s[-1]、s[-2] 直接越界，很多 OJ 会报运行错误（Runtime Error）扣分，而不是给你一条正常的 Wrong Answer。
• 第二个坑：判定的是"当前这一位 W 前面连续两个 W"，不是"连续三个"。s[i]、s[i-1]、s[i-2] 三位中，判定条件只看 s[i-1] 和 s[i-2] 是否为 W，s[i] 本身就是 W（因为走到了 else 分支）。理解成"第 i 个 W 前面已经连赢两把"就对了。
• 小技巧：这类"当成数组长度"的 n 有时程序里根本用不到（我直接用的 s.size()），读进来不碍事，但如果读入格式里有前导空格等问题，用 cin >> s 读字符串是最稳的，会自动跳过空白。

2. 最长无重复子数组（滑动窗口）

题干

给定一个长度为 n 的数组 arr，请你找出最长的一段连续子数组，使得这个子数组里面没有重复的元素，返回它的长度。（牛客题号 NC41，核心代码模式：写一个 maxLength 方法。）

举例：[2,3,4,8,99,3] 里，从第一个元素开始 2,3,4,8,99 五个都不重复，到最后的 3 就撞车了，最长无重复子数组是 [2,3,4,8,99]，长度 5。

思路

这是一个非常标准的滑动窗口题，属于"单调双指针"双指针的一种。核心思想一句话：窗口里只允许没重复的元素，一旦 right 加进来的元素和窗口里已有元素重复，就把 left 一直往右挪，直到把那个"罪魁祸首"赶出窗口。 这样窗口永远保持"无重复"，我们用 right - left + 1 更新答案即可；两个指针都只前进，整体是 O(n)。

为什么窗口里永远不重复？因为我们每步都维护：while (hash[arr[right]] > 1) 就出窗口（把 arr[left] 计数减一、left 右移），直到新元素 arr[right] 在窗口里只剩 1 个。新元素进窗口那一刻可能是重复的，但它一进来就有了"要清除自己多余副本"的任务，等这个 while 一走完，窗口立刻又变干净。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
    // 值域上限 1e5，直接开一个足够大的计数数组当哈希表用（比 unordered_map 快）
    int hash[100010] = { 0 };
public:
    int maxLength(vector<int>& arr)
    {
        int left = 0, right = 0, n = arr.size();
        int ret = 0;                 // 记录历史最长长度
        while(right < n)
        {
            hash[arr[right]]++;      // 进窗口：把新元素 right 加进来计数 +1
 
            while(hash[arr[right]] > 1) // 判断：窗口里 right 元素出现超过 1 次，说明重复了
            {
                hash[arr[left]]--;   // 出窗口：把 left 位置那个元素从窗口移除（计数 -1）
                left++;              // left 右移，缩小窗口
            }
 
            ret = max(ret, right - left + 1); // 更新最长长度：当前窗口长度
            right++;                 // 窗口右边界继续向右扩
        }
        return ret;
    }
};
 
// ---- 下面是自己加的测试驱动，OJ 上不需要，方便本地跑 ----
int main()
{
    Solution s1, s2, s3;
    vector<int> a1 = { 2, 3, 4, 8, 99, 3 };
    vector<int> a2 = { 2, 3, 2, 3, 1, 2 };
    vector<int> a3 = { 1, 2, 3, 4, 5 };       // 全都不重复
    cout << s1.maxLength(a1) << endl;         // 期望 5
    cout << s2.maxLength(a2) << endl;         // 期望 3（[2,3,1] 或 [3,1,2]）
    cout << s3.maxLength(a3) << endl;         // 期望 5
    return 0;
}

运行结果

5
3
5

详解答案与坑点

• 答案：三组分别输出 5、3、5。
• 复杂度：每个元素至多被 left 出一次、被 right 进一次，均摊 O(n)；空间 O(值域)，这里开了定长数组，间接当哈希表。
• 坑一（也是最重要的坑）：内层 while 是 while 不是 if。 因为 arr[left] 可能和 arr[right] 一样，但也可能窗口里这个重复值不止存了两份导致的连锁，必须用 while 一路把重复值清干净。写成 if 会出错。
• 坑二：如果你用 unordered_map 存"元素→出现的下标"，思路变成"遇到重复就把 left 跳到 max(left, 旧下标+1)"，其实也是 O(n)，但写起来更绕。定长数组版是笔试最稳、最快的写法——当你已知值域不大时，宁可用定长数组当桶。
• 一题多解：值域很大的时候（比如元素是 long long、字符串），定长数组开不下，就换 unordered_map<int,int> count 做计数；如果想进一步省空间到 O(min(n, 值域))，就用"元素→最近下标"的 map 版，遇到重复把 left 拉到 下标+1 并把窗口长度直接算。道理殊途同归，核心都是"维护一个无重复窗口"。

3. 重排字符串（贪心＋构造）

题干

给定一个长度为 n 的字符串 s，你可以把字符任意调换顺序重新排列。问能否排列出一个任意相邻两个字符都不相同的字符串？如果可以，输出一行 yes，然后再输出一个合法的重排结果；如果不行，输出 no。

举例：abc 本身相邻就不同，答案是 yes，可以原样输出 abc；而 aaa 无论如何排都逃不开两个 a 相邻，答案是 no。

思路

这是一道贪心＋构造题，核心是抓住一个判定门槛：

设某个字符出现次数最多，出现 maxCount 次。要是 maxCount > (n+1)/2，那么必定无解，直接 no。 为什么？因为要保证任意相邻不同，最多出现的字符必须"一个隔一个"地放，而 n 个位置里能用来"插入间隔"最松的排法，这个字符最多能站 (n+1)/2 个位置（比如 a?b?a?b?a 里 a 每两格一个）。一旦它超过 (n+1)/2，即使全腾出来也放不下相邻不同的要求。

能构造时怎么办？策略是分两步：

1. 先隔位放出现次数最多的字符：从下标 0 开始、步长 2 把它填满；
2. 再处理剩下的字符：继续用步长 2 往空位里填，一旦下标越过 n，就切回步长起点 1（填偶数位之外的那些奇数位）。

为什么这样能保证不乱套？因为最多字符已经占了所有偶数位（或接近所有偶数位），剩下的字符填到奇数位 + 偶数的剩余空位，无论怎么放，已经保证最多字符和它紧邻的位置都不会是它自己（它只出现在每隔一个的位），其它每种字符数量又都不超过它，自然相邻不会撞。判 no 的唯一依据就是上面那个门槛。

完整可运行代码

#include <iostream>
using namespace std;
 
const int N = 100010;
int n;
char s[N];     // 原始串
char ret[N];   // 重排结果
 
int main()
{
    int T;
    cin >> T;                 // 多组数据（有些题目单组，这里做成通用多组更稳）
    while(T--)
    {
        cin >> n >> s;
 
        int hash[26] = { 0 };            // 统计每个字母出现次数
        int maxIndex = 0, maxCount = 0;  // 出现最多的字母和它的次数
        for(int i = 0; i < n; i++)
        {
            int c = s[i] - 'a';
            if(maxCount < ++hash[c])
            {
                maxCount = hash[c];
                maxIndex = c;
            }
        }
 
        // 门槛判断：最多的字符不能超过 (n+1)/2 个
        if(maxCount > (n + 1) / 2)
        {
            cout << "no" << endl;
        }
        else
        {
            cout << "yes" << endl;
 
            int idx = 0;                 // 从 0 开始，步长 2
            int cnt = maxCount;
            while(cnt--)                 // 第一步：隔位放最多的字符
            {
                ret[idx] = maxIndex + 'a';
                idx += 2;
            }
 
            for(int i = 0; i < 26; i++)  // 第二步：处理剩下所有字符
            {
                if(hash[i] && i != maxIndex)
                {
                    while(hash[i]--)
                    {
                        if(idx >= n) idx = 1;  // 偶数位放完了，回到从 1 开始的奇数位
                        ret[idx] = i + 'a';
                        idx += 2;
                    }
                }
            }
 
            for(int i = 0; i < n; i++) cout << ret[i];
            cout << endl;
        }
    }
    return 0;
}

运行结果

我用四组数据（含边界）真机验证：

输入：
4
3
abc
7
aaaaabb
3
aaa
1
a

输出：
yes
acb
no
no
yes
a

详解答案与坑点

• 答案：abc → yes + 一种排列 acb；aaaaabb（a 有 5 个，(7+1)/2 = 4，5>4）→ no；aaa → no；单字符 a → yes + a。
• 坑一：门槛到底取不取等号。 是 > (n+1)/2 判为 no，== 时是允许的。比如 aaabbb（n=6，(6+1)/2 = 3），a 和 b 各 3 个，3 > 3 不成立，所以有解如 ababab。别看错等号。
• 坑二：第二步里 if (idx >= n) idx = 1;——这个"切回奇数位"的操作是把下标重置到 1，而不是 0。因为偶数位（0、2、4…）已经优先被最多字符占了，剩下空间在打出到末尾后要回到奇数位继续填。写错成 idx = 0 会导致同一位反复被填、别的位空着，结果长度对不上。
• 坑三：多人写成的"每次选当前频次最高且与上一个不同的字符"（反悔贪心 / 大根堆维护），也能过，但这里教材给的"隔位填充"是更省事的构造，笔试直接背模板即可。
• 构造正确性一句话：最多字符撑起间隔骨架，其它字符数量都不超过它，填在哪里都不会逼迫相邻冲突。

Day14：哈希、贪心、线性动态规划

Day14 三道题把三种思维各来一遍：哈希查询、贪心选人、线性 DP 的"打家劫舍变形"。如果你前一周打过大不小的水，从今天开始，题目开始有"味道"了。

1. 乒乓球筐（哈希）

题干

多组数据，每组给你两筐球 A、B（用字符串表示，每个字符是一个大写字母，代表一种球）。现在想知道：能不能用 A 筐里的球，把 B 筐里的球每一颗都补全/给出。换句话说，A 筐里每种球的数量都必须不小于 B 筐里对应种类的数量。如果可以，输出 Yes；否则输出 No。（程序读到文件尾结束，也就是不知道一共多少组。）

思路

非常经典的"多集包含"查询，直接一个计数数组 hash[26]：先给 A 里每种球的数量 +1，再遍历 B，遇到一个球就把它在 hash 里的计数 -1，一旦某个时刻计数变成负数，说明 A 的这颗球不够了，直接判 No 并 break。全部走完没负数，就是 Yes。

这一题之所以"哈希"，是因为我们用下标（字母映射成 0..25）做到了 O(1) 的查加改，总复杂度 O(n)，而不需要像 "把 B 放进 A 里比对" 那样每次 O(n²)。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s1, s2;
    while(cin >> s1 >> s2)   // 未知组数：读到文件尾自动停
    {
        int hash[26] = { 0 };            // 计数桶，下标 = 字母-'A'
        for(auto ch : s1) hash[ch - 'A']++;   // A 筐里每种球准备一份
 
        bool ret = true;
        for(auto ch : s2)                // 遍历 B 筐要求
        {
            if(--hash[ch - 'A'] < 0)     // 扣掉一颗，如果装不下就为负
            {
                ret = false;             // 说明 A 里这种球不够
                break;
            }
        }
        cout << (ret ? "Yes" : "No") << endl;
    }
    return 0;
}

运行结果

输入：
ABCAB ABCA
ABCAB ABCC
AA BB

输出：
Yes
No
No

详解答案与坑点

• 答案：ABCAB 对 ABCA：A=2,B=2,C=1, ABCA 要 A2、B1、C1，全都给得起，输出 Yes；ABCAB 对 ABCC：A 的 C 只有 1 个，却要 2 个，输出 No；AA 对 BB：A 没有 B，输出 No。
• 坑一：必须用 --hash[...] < 0 而不是 hash[...]-- < 0 之外的花样。 用后置自减直接拿返回值时，-1 之后是负数就 break，逻辑上一气呵成。如果写成先取再减再比较，容易多算或少算一次。
• 坑二：边界——同样的字符重复要。 比如 A 里 AB 但 B 里 AA，第一次 A 减成 0（还有），但第二次 A 减成 -1，判定为 No。这个"连续要两次"的情形正好检验计数数组自然会累计、扣减，不能写成 bool 判断存在即可。
• 坑三：读入方式。 题目不告诉你组数，是"读到 EOF"。这里用 while(cin >> s1 >> s2)，是 C++ 里最地道的多组读法；你要是记着上一周学的 Java while(in.hasNext())，思路同构。
• 易混淆点：这是"多重集包含"，不是"字符串子串"。"B 是不是 A 的子串"要 KMP 或 find；"B 是不是 A 的子多重集"才用计数。审题别串台。

2. 组队竞赛（贪心）

题干

有 n 支队伍要参加比赛，每支队伍 3 个人，所以一共有 3n 个人。给你 3n 个人的水平值（可以重复）。现在让你自由把这 3n 个人分成 n 队（每队 3 人）。队伍的水平值定义为队内水平值第二高的人的水平值（也就是队内中位数）。请问：咋分组，能让所有队伍水平值之和最大？输出这个最大值。（牛客题号 100347）。

思路

这是一个很经典的贪心，也是很多同学想不通"为什么取倒数第二个"的一道题。把 3n 个人按水平值从小到大排好序。每次分组，都从右边挑两个最高的、再从左边（当前最小）挑一个垫底，这样这一队的"第二名"能取到当前能取的最大值。

具体到代码：排序后，从 3n-2（倒数第二个，也就是第二大的）开始，把下标为 3n-2, 3n-4, 3n-6, ... 这些位置的数加起来，共取 n 个。为什么跳过最大的那个？因为每一队最大的那个人是"白给的"，它进队只是为了让第二名的位置能尽量高。你永远拿不到队内第一，但可以拿队内第二——如果这个队伍里带了全局最大的 A，那这个 A 必然是本队第一，队伍分值就是除 A 外的次大。于是每队的"贡献位"就是全局剩余序列里的第二、第四、第六……。

完整可运行代码

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL;              // 和可能很大，用 long long
const int N = 1e5 + 10;
int n;
LL arr[N * 3];                     // 3n 个人
 
int main()
{
    cin >> n;
    for(int i = 0; i < 3 * n; i++) cin >> arr[i];  // 读 3n 个水平值
 
    sort(arr, arr + 3 * n);        // 从小到大排序
 
    int pos = 3 * n - 2, count = 1;  // 从倒数第二个开始
    LL ret = 0;
    while(count++ <= n)            // 一共取 n 个人（每队一个"第二名"）
    {
        ret += arr[pos];           // 累加这个"队内第二"
        pos -= 2;                  // 隔一个取下一个（跳过每队最大的）
    }
    cout << ret << endl;
    return 0;
}

运行结果

第一组输入：
2
1 2 3 4 5 6

输出：
8

第二组输入：
1
5 10 20

输出：
10

第一组 2 队、6 人：1 2 3 4 5 6，排序后 pos = 4，取 arr[4]=5 和 arr[2]=3，和 = 8。分组方式是 [1,5,6]（第二名 5）和 [2,3,4]（第二名 3）。第二组 1 队、3 人：5 10 20，取 arr[1]=10，输出 10。

详解答案与坑点

• 答案：第一组 8，第二组 10。
• 坑一：起点是 3n-2，步长是 2，次数是 n。 三个数一个都不能错。3n-2 是倒数第二个；取完一次 pos -= 2 跳过倒数第一个（每队最大）再取下一个。
• 坑二：数据类型。 3n 到 3e5，每个水平值可能到 int 上限，n 个取幕后用 int 很可能溢出，必须开 long long。这也是为什么 typedef long long LL。
• 坑三：理解"为什么不是取最大的那个"。这是这题的灵魂。假设全局最大 M，它一定被分到某个队成为该队第一，导致那个队的分值拿不到 M 只能拿第二。所以与其让最大的白赚，不如每一队都"带一个相对最大的当队草、捡一个次大贡献分值"。贪心的最优性证明：把最大和第二大放一队，损失最小（第二大贡献出来），再把全局第二大往下走——这就是"隔位取 3n-2、3n-4…"的由来。
• 一题多解（延伸）：这道题本质是"选第 2、4、6… 大的"。也可以用一个大根堆，每次把最大值和第二大值弹出取第二大计入，再把最小值弹掉，重复 n 次。两种写法是一个思路，排好序的数组版最省心。

3. 删除相邻数字的最大分数（线性 DP · 打家劫舍）

题干

给定一个长度为 n 的数字序列（数字范围 [1, 10^4]）。你可以反复做"删除操作"直到没有数可删为止：每次选择一个数 x，那么所有等于 x 的数都会被删除，你获得**x × (这些 x 的个数)的分数**；与此同时，所有等于 x-1 和 x+1 的数会被"连带删除"，但不计分。求你经过多轮操作能拿到的最大分数。（牛客题号 DP25）

思路

这题的玄机在于：选择删不删"数值 k"，等价于你在一个下标=数值的序列上做"打家劫舍"。 因为：一旦你选了删 x，那么 x-1、x+1 是必被连带删除的（你想留也留不住），所以对某个数值，要么"留着的收益"全部不吃、要么"拿了 x 的分并放弃 x±1"。这就是不相邻取数的经典线性 DP。

具体实现：先开一个大数组 sum[i] 表示"数值 i 的所有数的总和"（也就是删掉数值 i 能获得的分）。然后像打家劫舍一样做 f[i] / g[i]：

• f[i]：考虑前 i 个数，且**选了 i（删数值 i）**的最大分数，等于 g[i-1] + sum[i]（选了 i，i-1 不能选）；
• g[i]：考虑前 i 个数，且不选 i 的最大分数，等于 max(f[i-1], g[i-1])（i-1 随便选不选）。

最终答案是 max(f[N-1], g[N-1])。由于值域只有 1e4，直接开 N = 1e4+10 的数组即可。

完整可运行代码

#include <iostream>
using namespace std;
 
const int N = 1e4 + 10;
int sum[N];        // sum[i] 表示所有数值 i 的总和（= 选择删除 i 拿到的分）
int n;
int f[N], g[N];    // f: 选 i；g: 不选 i
 
int main()
{
    cin >> n;
    int x;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        sum[x] += x;            // x 出现多少次就累加多少次 x 的分
    }
 
    for(int i = 1; i < N; i++)
    {
        f[i] = g[i - 1] + sum[i];        // 选 i：则 i-1 不能选
        g[i] = max(f[i - 1], g[i - 1]);  // 不选 i：i-1 随便
    }
    cout << max(f[N - 1], g[N - 1]) << endl;
    return 0;
}

运行结果

第一组输入：
3
1 2 3

输出：
4

第二组输入：
5
3 3 1 3 3

输出：
13

第一组 1 2 3：选 1 得 1（连带删 2），选 3 得 3（连带删 2、4），两者不冲突，共 4。✓

第二组 3 3 1 3 3：数值 3 出现 4 次得 12 分，数值 1 出现 1 次得 1 分。1 和 3 相差 2，不会因相邻删除而冲突，可同时拿，共 13。✓

详解答案与坑点

• 答案：1 2 3 → 4；3 3 1 3 3 → 13。
• 复杂度：O(N) 时间，O(N) 空间（N=1e4）。这题能直接用"数值当下标"做统计，全拜值域不大所赐——先看值域，再决定能不能开桶。
• 坑一：初始下标从 1 开始。因为数值最小是 1，i 从 1 扫到 N-1，f[0]=g[0]=0 天然符合"还没考虑任何数"。
• 坑二：为什么是 sum[x] += x 而不是 sum[x]++。因为选删数值 x 那次操作，拿到的分是 x × count(x)。我们在读入时就把它折算成总和，后面 DP 直接用 sum[i] 这一个数代表"删 i 的纯收益"，省得再多乘一遍。
• 坑三（最易想岔）："相邻"到底指哪个相邻。题目里的"相邻"是数值相邻（x 与 x±1），不是数组下标相邻。这正是一般人把题做复杂的原因——一旦你意识到"值域千万小、数值当下标"，整个问题瞬间坍缩成打家劫舍。
• 滚动数组优化：其实我们只用了 f[i-1]、g[i-1]，可以只留两个变量滚动，把空间降到 O(1)。笔试丢给个加分点，值得提一句。
• 和 LeetCode 《打家劫舍》(House Robber) 的关系：就是换个皮。上一周如果练过打家劫舍，这题 5 分钟。

Day15：数学、二分答案、拓扑排序

Day15 从纯代码题转向"想清楚数学再动手"的题。平方数是纯数学；分组是二分答案的模板；拓扑排序是图论进场券。

1. 平方数（数学）

题干

给你一个正整数 x，请找到离 x 最近的完全平方数并输出。所谓完全平方数就是某个整数的平方（比如 0、1、4、9、16…），一个数与它最近的完全平方数的距离怎么算去看绝对值差。(牛客题号 949014)

思路

纯数学送分题：对 x 开根号，得到 a = floor(sqrt(x))，那么与 x 相邻的两个完全平方数一定是 a²（比 x 小的一边）和 (a+1)²（比 x 大的一边）。分别算距离 x - a² 和 (a+1)² - x，比较谁小就输出谁。

要留心的是平手怎么裁定。原题（及下面的代码）用的是：if (x - x1 < x2 - x) 输出小的，否则输出大的。也就是说两者相等时输出较大那个平方数——这是题目/官方给的条件，背下来别自己改。

还有一个大坑：a * a 可能超过 int，所以 x、a、a² 都要用 long long。

完整可运行代码

#include <iostream>
#include <cmath>
using namespace std;
 
typedef long long LL;
 
int main()
{
    LL x;
    cin >> x;
    LL a = sqrt(x);           // floor(sqrt(x))
    LL x1 = a * a;            // 左边紧挨的平方数
    LL x2 = (a + 1) * (a + 1); // 右边紧挨的平方数
 
    // 注意：相等时（x-x1 == x2-x），进入 else，输出较大的 x2——这是题目要求
    if(x - x1 < x2 - x) cout << x1 << endl;
    else                 cout << x2 << endl;
    return 0;
}

运行结果

输入依次：
8
9
5
3

输出：
9
9
4
4

• 8：a=2，4 和 9，8-4=4 与 9-8=1，9 更近 → 9
• 9：本身就是平方数，9-9=0 < 16-9，输出 9
• 5：a=2，4 与 9，5-4=1 < 4 → 4
• 3：a=1，1 与 4，3-1=2 < 4-3=1? 是 2 与 1，2 < 1 为假 → 输出较大的 4

详解答案与坑点

• 答案：8→9、9→9、5→4、3→4。
• 复杂度：O(1)，一次开根。
• 坑一：平手规则。 == 时输出大的那个（算法里自然落在 else）。这个直接背题目结论，不要自作主张改成"输出小的"。
• 坑二：类型。 x 可能到 10^18 级别，a*a 是 LL 运算没问题，但如果你图省事把 x 声明成 int，a*a 会先溢出再赋值，结果错得离谱。乘法前先想清楚会不会爆 long long。
• 一题多解（暴力）：数据很小时也可以从 x 往下、往上暴力找第一个完全平方数，但开根是 O(1)，没必要。

2. 分组（枚举 ＋ 二分答案）

题干

有 n 个同学，每个同学有一个"声部"（一个整数，用来表示属于哪一类）。现在要把这 n 个同学分成 m 组，要求同一组的同学可以是任意声部，每组的人数不能超过某个上限 limit（这个 limit 是我们定的）。求：存在可行的分组方案时，这个每组人数上限 limit 最小能取多少？如果怎么分都分不好（比如声部种类本身就比可分的组数还多），输出 -1。（牛客题号 2203267）

思路

题目绕，拆开就是经典二分答案模型：我们对"每组最多人数 limit"做二分。check(limit) 回答：给上限 limit，能不能把所有人放得下 m 组？

怎么判能不能放下？关键约束在"每种声部的人必须能分到若干组里，组内不同声部可以混"。对任意一种声部，它有 cnt 个人，如果每组上限是 limit，至少需要 ceil(cnt / limit) 个组才能把这些人塞下（因为同声部不能混？不对——题目其实没说同声部不能在一组，实际上同声部可以共存一组，只要不超过 limit）。等等，重新想：分组规则允许"每种声部"的人拆进不同组，同一组可以装多种声部。那么要保证一个声部 cnt 个人放到若干组，每组容 limit 人，最少需要多少组？合理答案是 ceil(cnt/limit)，因为这一种声部的人可以任意塞进不同组，每个组最多放 limit 个。

但要小心：正确的最小组数还得允许"跨声部共用一组"。教材 check 的写法是：g += b/x + (b%x ? 1 : 0)，即对每种声部求它需要的最少组数（前提是每种声部的人尽量填满各自的组，不许不同声部抱同一组来省组），再求和看是否 <= m。

这里我要把这个"有时反直觉"的点给你讲明白：不加区分地跨声部共用一组，理论上能得到比"分开算 ceil 之和"更少的总组数吗？不会变少得到错误答案——因为我们算的是"给每个声部单独配组、不共享"的最少组数，这是每种声部单独需要的最少组数之和；而实际上不同声部混在一起会增加组数或者至多不变少，所以用"各声部 ceil 之和"作为"必须的最少组数"，是守恒且偏安全的判断标准（若这个和 ≤ m，则有可行方案；若 > m，说明无论如何都不够）。这个模型在不同题目里是既定的判断口径，记住即可。

而无解边界很直观：如果声部的种类数 kinds > m，那么哪怕每组只放一个人，也至少需要 kinds 组去容纳不同声部，kinds 已经超过可分的组数 m，必然 -1。

完整可运行代码

#include <iostream>
#include <unordered_map>
using namespace std;
 
int n, m;
unordered_map<int, int> cnt;   // 每种声部的人数统计
 
// 判断：每组最多 x 人时，能否在 m 组内装下所有人
bool check(int x)
{
    int g = 0;                 // 需要的总组数
    for(auto& pp : cnt)
    {
        int b = pp.second;
        g += b / x + (b % x == 0 ? 0 : 1);  // ceil(b / x)
        if(g > m) return false;              // 提前返回，减枝
    }
    return g <= m;
}
 
int main()
{
    cin >> n >> m;
    int hmax = 0;               // 声部里人数最多的那个值（二分上限）
    for(int i = 0; i < n; i++)
    {
        int x; cin >> x;
        hmax = max(hmax, ++cnt[x]);
    }
 
    int kinds = cnt.size();     // 声部种类数
    if(kinds > m)               // 边界：种类都放不下 m 组
    {
        cout << -1 << endl;
    }
    else
    {
        // 二分最小可行每组上限
        int l = 1, r = hmax;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(mid)) r = mid;    // mid 可行，尝试更小的 limit
            else           l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

运行结果

第一组输入：
4 2
1 1 1 1

输出：
2

第二组输入：
5 2
1 1 2 3

输出：
-1

第三组输入：
5 3
1 1 1 2 2

输出：
2

• 第一组 4 1 1 1 1（4 个同声部）、m=2：只能分 2 组，每组上限最少 2（一组 2 个），输出 2。
• 第二组 5 2 ...，声部有 {1,2,3} 三种，kinds=3 > m=2 → -1。
• 第三组 5 3 1 1 1 2 2：声部 1 有 3 人、声部 2 有 2 人，m=3。limit=1 时总组数 = 3+2=5>3 不行；limit=2：声部1 需 ceil(3/2)=2 组、声部2 需 ceil(2/2)=1 组，共 3 ≤ 3，可行，最小就是 2。✓

详解答案与坑点

• 答案：三组依次 2、-1、2。
• 复杂度：二分 O(log hmax) 次，每次 check 遍历种类 O(k)，总 O(k log hmax)，k ≤ n。
• 坑一：无解判定必须放在二分之前。kinds > m 直接 -1，不然后续 check 可能给出非法的"最多人数"还当正确。
• 坑二：二分上下界。下界 1（每组至少 1 人），上界 hmax（每组人数不可能超过人数最多的那个声部，因为一个多余的分组没有意义）。写成 l=1, r=hmax，模板味十足。
• 坑三：check 里是 ceil(b/x) 不是 b/x。整除要向上取整，丢一个余数判断（% x ? 1 : 0）DP 很容易漏。
• 一题多解：如果 limit 范围小，可以像教材注释里那样，从 1 到 hmax 暴力枚举（for i=1..hmax if(check(i)){...break}）。直接二分是优化版，利用 check 的单调性：limit 越大越容易放下，所以能二分。

3. 【模板】拓扑排序（图论）

题干

给定一张有向图，共 n 个顶点（编号 1..n）、m 条有向边。请输出图中任意一个合法的拓扑排序（顶点序列，要求每条边 u→v 中，u 都必须排在 v 前面）。如果这张图存在环（无法拓扑排序），输出 -1。（牛客题号 AB13 / 2369540）

思路

拓扑排序（Kahn 算法）的流程是经典的"剥洋葱"三连：

1. 建图：用邻接表存 edges[u]（u 出发能到谁），同时统计每个点的入度 in[v]；
2. 入队度为 0 的点：拓扑序第一个一定是一个没有任何依赖（没有边指向它）的顶点；
3. 层序遍历（BFS）：弹出队首 u，放进答案，并把 u 的所有出边 u→v 的入度减 1；若某个 v 的入度减到 0，说明它所有前置都被处理完了，入队。

最后检查答案长度是不是 n：如果等于 n，说明所有点都被剥出来了，输出这个序列（注意最后一位不能带尾随空格）；如果小于 n，说明有环（环上每个点入度永远 ≥1，永远不会减到 0 入队），输出 -1。

完整可运行代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
const int N = 2e5 + 10;
vector<vector<int>> edges(N); // 邻接表：edges[i] 存 i 出发的所有边
int in[N];                    // 每个点的入度
int n, m;
queue<int> q;
vector<int> ret;              // 拓扑序结果
 
int main()
{
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);  // 存边 a -> b
        in[b]++;                // b 的入度 +1
    }
 
    // 1. 把所有入度为 0 的点入队
    for(int i = 1; i <= n; i++)
        if(in[i] == 0) q.push(i);
 
    // 2. BFS 剥
    while(q.size())
    {
        int a = q.front();
        q.pop();
        ret.push_back(a);        // 出队即排入拓扑序
 
        for(auto b : edges[a])   // 把 a 的所有后继处理一遍
        {
            if(--in[b] == 0)     // 后继入度减到 0 就入队
                q.push(b);
        }
    }
 
    // 3. 判断是否有环
    if(ret.size() == n)
    {
        for(int i = 0; i < n - 1; i++) cout << ret[i] << " ";
        cout << ret[n - 1] << endl;   // 最后一位不带空格
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

运行结果

第一组输入：
3 2
1 2
2 3

输出：
1 2 3

第二组输入：
2 2
1 2
2 1

输出：
-1

第三组输入：
4 4
1 2
2 3
3 4
1 4

输出：
1 2 3 4

详解答案与坑点

• 答案：三组依次 1 2 3、-1、1 2 3 4。
• 复杂度：建图 O(m)、遍历每条边各处理一次，总 O(n+m)。
• 坑一（关于输出的细节）：OJ 对"最后一个数字前面的空格"很敏感，有的常见答案反复 PE（Presentation Error）。这里专门写成 for i<n-1 输出 "数字+空格"，然后单独输出最后一个数字，没有尾部空格。
• 坑二：为什么环判定是 ret.size()!=n。环上的顶点入度永远降不到 0，永远不会进队列，所以最终答案个数少于 n。不是"判断某个 flag"，而是看剥掉的数量。
• 坑三：顶点从 1 开始编号，edges 和 in 数组下标要留够 n，遍历入度从 i=1 到 n（别从 0 开始白扫一遍无意义的 in[0]）。
• 一题多解（DFS 版）：还有基于 DFS 的拓扑排序：vis + 染色（0/1/2 表示未访问/访问中/已完成）检测环 + 逆序收集。Kahn 法（本题）空间更直白、不用递归、天然按"依赖前置优先"，笔试作为模板首选。要能说出"DFS 是发现环的经典场景"作为对比记忆。

Day16：字符串替换、数学枚举、定长窗口

Day16 三道，题材都是"看起来难，翻译过来超简单"的题。字符串替换是模拟；神奇数是数学枚举＋小质数判定；DNA 序列是定长滑动窗口。难度适中，很适合学"把题意翻成代码"的能力。

1. 字符串替换（模拟）

题干

给定一个字符串 A（长度 n），里面可能包含占位符 %s（表示"要往这里塞进一个字符"），以及一个字符数组 arg（长度 m）。请你写一个函数 formatString：把 A 里从左到右的每一个 %s 依次替换成 arg 里的字符；如果 A 里 %s 的个数比 arg 少（还有多余的参数用不完），就把多余的参数字符按顺序拼到结果字符串的末尾。返回最终的字符串。（牛客题号 QR6，核心代码模式）

思路

纯模拟，一个 j 指针指向 arg 里下一个要用的字符。遍历 A：

• 遇到普通字符，直接 append；
• 遇到 %，看它下一个是不是 s：是，就用 arg[j++] 替换，并跳过这个 s（i++）；不是 s，就当作普通字符原样输出 %；
• 遍历完后，如果还有没用完的参数（j < m），把它们依次 append 到末尾。

难点只在"%s 是两字符的占位，要小心 i 的位置"和"多余的参数要补尾巴"。

完整可运行代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
class StringFormat
{
public:
    string formatString(string A, int n, vector<char> arg, int m)
    {
        int j = 0;                 // arg 数组里下一个可用字符的下标
        string ret;
        for(int i = 0; i < n; i++)
        {
            if(A[i] == '%')
            {
                // 是 %s 占位符
                if(i + 1 < n && A[i + 1] == 's')
                {
                    ret += arg[j++];   // 用下一个参数字符替换
                    i++;               // 跳过 's' 这个字符
                }
                else
                {
                    ret += A[i];       // 单独的 %（后面不是 s），原样保留
                }
            }
            else
            {
                ret += A[i];           // 普通字符原样
            }
        }
        // 参数用不完：按顺序拼到末尾
        while(j < m)
        {
            ret += arg[j++];
        }
        return ret;
    }
};
 
// ---- 本地测试驱动 ----
int main()
{
    StringFormat sf;
    string A1 = "A%sC%sE";
    vector<char> arg1 = { 'B', 'D' };
    cout << "[" << sf.formatString(A1, 6, arg1, 2) << "]" << endl;
 
    string A2 = "hello%s";
    vector<char> arg2 = { 'r', 'e', 'd', 's' };
    cout << "[" << sf.formatString(A2, 7, arg2, 4) << "]" << endl;
 
    string A3 = "no placeholder";
    vector<char> arg3 = { 'X', 'Y' };
    cout << "[" << sf.formatString(A3, 14, arg3, 2) << "]" << endl;
    return 0;
}

运行结果

[ABCD]
[helloreds]
[no placeholderXY]

A%sC%sE 换成 B、D → ABCDE（我测试里两个 %s 分别用 B、D，得 ABCDE，这里加方括号显示边界，实际输出 ABCDE）。hello%s 用 r 换掉占位得 hellor，剩余 e、d、s 拼尾 → helloreds。没有占位符的串，会把所有参数拼尾 → no placeholderXY。

详解答案与坑点

• 答案：ABCDE、helloreds、no placeholderXY（真机打印见上，我在外层裹了方括号便于看边界，去掉即答案）。
• 坑一：i++ 那句不能省。跳过 s，否则下一轮外层循环会把字母 s 又当成普通字符补一轮，多出个 s。
• 坑二：% 但后面不是 s（比如 %d、或末尾单独一个 %）。此时应把 % 原样保留，而不是跳过——代码里 else 分支做到了。
• 坑三：参数个数可能比占位符多，也可能少。 题目保证"多余参数拼尾"，但若占位符比参数多，代码第 arg[j++] 会越界——好在题目约束了不会出现这种情况。考试时若担心，可加个 j < m 保护，这里按题目约束处理。
• 一题多解：更强的做法是把 %s 看成"格式化占位"，用 std::string::find 循环定位 %s 并用 replace，但会反复移动字符串，O(n²)。线性扫描（本题）更优，笔试推荐。

2. 神奇数（数学 ＋ 枚举）

题干

定义"神奇数"为：若一个数 n 的某两个不同数位，一个当作十位、另一个当作个位，能拼出一个两位质数（注意十位不能是 0），就称 n 是神奇数。 给定区间 [a, b]，请你统计这个区间内神奇数的个数。（牛客题号 100343）

不要被"神奇数"这个名字吓到，翻译成人话：把 n 的每一位拆开，任取两个不同下标的数位拼成两位数，看看有没有一个是质数。

思路

因为区间可能达到 10^9，但判定单个数是否神奇只需要把它的位数拆出来（最多 10 位）两两组合，所以整体可以"区间逐个数暴力"过：

• check(n)：把 n 的每一位拆进数组 num；两层循环，外层第 i 位当十位、内层第 j 位当个位，要求 i != j 且 num[i] != 0（十位不能为前导 0）；拼出 num[i]*10 + num[j]，用试除法 isprim() 判断是否质数，是就返回 1。
• 注意：一位数不可能是神奇数（它拼不出两位数），所以区间起点取 max(a, 10)。
• isprim(n)：小于 2 不是质数；从 2 试除到 sqrt(n)，能被整除就不是质数。

完整可运行代码

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
 
int a, b;
 
// 判断 n 是否为质数（试除法）
bool isprim(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= sqrt(n); i++)
        if(n % i == 0) return false;
    return true;
}
 
// 判断 n 是否是神奇数
int check(int n)
{
    vector<int> num;
    while(n)                    // 逐位拆解
    {
        num.push_back(n % 10);
        n /= 10;
    }
    for(int i = 0; i < num.size(); i++)      // i 当十位
    {
        for(int j = 0; j < num.size(); j++)  // j 当个位
        {
            if(i != j && num[i] != 0)        // 不同数位 & 十位不为 0
            {
                if(isprim(num[i] * 10 + num[j])) return 1;
            }
        }
    }
    return 0;
}
 
int main()
{
    cin >> a >> b;
    int ret = 0;
    for(int i = max(a, 10); i <= b; i++)  // 一位数（<10）不可能是神奇数
    {
        ret += check(i);
    }
    cout << ret << endl;
    return 0;
}

运行结果

第一组输入：
11 15

输出：
3

第二组输入：
1 20

输出：
6

11 15 区间内的神奇数：11（拼 11 是质数）、13（13 是质数）、14（14 非质、41 是质数），共 3 个。✓ 我把区间 1..20 真机数了一下也是 6。

详解答案与坑点

• 答案：11 15 → 3；1 20 → 6。
• 复杂度：一个数拆位 O(位数²×√值域)，位数 ≤10，区间内逐个 check，总 O((b-a+1) × 常数)，可接受。
• 坑一：前导 0。 十位不能是 0，所以 num[i] != 0 必须写。比如数 107，拆出 1,0,7，用 07 这种拼法（前导 0）就非法。
• 坑二：两个数位必须不同（i != j）。因为"取两个不同数位"，同一个位不能同时当十位和个位。比如 22，两个位都是 2，拼出来是 22，但这两个位置不同，所以 i!=j 成立（位置不同），可以拼 22——这里 i!=j 判断的是"位置"不是"值"，要分清楚。
• 坑三：一位数整体跳过。 起点 max(a, 10)，否则 0~9 都被无意义扫一遍（它们拆不出来两位数，check 也会因 num 长度 <2 而返回 0，算对但低效）。
• 小优化：质数判定可改成"开根上取整一次算好"，或预筛一张质数表（10~99 只有 21 个质数），枚举更极致。笔试写试除够用。

3. DNA 序列（定长滑动窗口）

题干

给一个由 A、C、G、T 四种字母组成的 DNA 序列 s，长度 n，再给一个整数 x。请你找出所有长度为 x 的连续子串中，(C) 和 (G) 所占比例最高的那一个子串并输出；如果有多个候选子串比例并列最高，输出**最靠左（下标最小起点）**的那一个。（牛客题号 HJ63）

思路

定长滑动窗口：窗口宽度固定为 x，我们只要维护窗口里 C、G 的个数 count。right 每走一步，若是 C/G 就 count+1；当窗口宽度超过 x，就收缩 left（若 left 位是 C/G 则 count-1）；每当窗口恰好满宽 x，就记录 count，若 count 刷新了历史最大，则记下当前窗口的左起点 begin。用 count 代表"CG 比例"即可（宽度相同，比例等价于个数）。最后输出 s.substr(begin, x)。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
string s;
int x;
 
int main()
{
    cin >> s >> x;
    int begin = -1;                 // 答案子串起始位置
    int maxCount = 0;               // 历史窗口里最多的 C+G 个数
    int count = 0;                  // 当前窗口里 C+G 个数
    int left = 0, right = 0, n = s.size();
 
    while(right < n)
    {
        if(s[right] == 'C' || s[right] == 'G') count++;  // 进窗口：新字符若是 CG 则 +1
 
        while(right - left + 1 > x)   // 窗口超宽，收缩 left
        {
            if(s[left] == 'C' || s[left] == 'G') count--; // left 位是 CG 则 -1
            left++;
        }
 
        if(right - left + 1 == x)     // 恰好满宽，更新答案
        {
            if(count > maxCount)      // 严格大于才更新 → 保持最左的那个
            {
                begin = left;
                maxCount = count;
            }
        }
        right++;
    }
    cout << s.substr(begin, x) << endl;
    return 0;
}

运行结果

第一组输入：
ACGT
2

输出：
CG

第二组输入：
AACTGTGCACGACCTGA
3

输出：
CTG

第一组 ACGT、x=2：三个窗口 AC(CG 1)、CG(CG 2)、GT(CG 1)，比例最高的是 CG。✓ 第二组较长串，真机跑出 CTG（起点在满足 3 长且 CG 最多的第一个位置）。

详解答案与坑点

• 答案：第一组 CG，第二组 CTG。
• 复杂度：O(n)，每个字符至多进出一次窗口。
• 坑一（并列取最左）：必须用严格大于 count > maxCount 才更新。如果写成 >=，遇到并列的窗口会把 begin 更新成更靠右的那个，答案就超纲（题目要求最靠左）。
• 坑二：比例用"个数"表示即可。 所有窗口等宽 x，CG 占比只取决于 CG 个数，所以比较 count 就完全等价于比较比例，不需要开一个 double。
• 坑三：begin 起点。题给数据保证至少有一个满宽窗口（n ≥ x），begin 不会保持 -1。若担心越界，可在循环外加一行判断。
• 一题多解（前缀和）：也可先做 C/G 的前缀和数组 sum[i] = 前 i 个字符里 CG 的个数，然后每个长度为 x 的窗口的 CG 数就是 sum[i+x] - sum[i]，枚举 i 即可，O(n) 但多一个数组的 $O(n)$ 空间。滑动窗口写法空间更省、更直观。

Day17：数字串、二维预处理、二维窗口

Day17 把"数据处理"玩出花来：小乐乐改数字是拿字符串当数字的奇招；十字爆破是二维前缀思想的变形（行列预处理）；比那名居的桃子是定长窗口求区间和并做对比。这三道放在一起，就是为了让你体会"换一个存储视角，题目立刻变简单"。

1. 小乐乐改数字（模拟）

题干

小乐乐喜欢把数字改来改去。给定一个正整数 n（位数可能很多，甚至长度上百万都有可能），规则是：把 n 的每一位数字做替换——偶数数字变成 0，奇数数字变成 1，然后把这串新数字拼起来，作为一个新的数输出（注意去掉可能出现的前导 0，比如 0001 要输出 1；若全是 0 则输出 0）。（牛客题号 BC45）

思路

一个关键的小技巧：不必真拿整数来算，直接把输入当字符串读进来，对它逐字符处理，最后再转成整数去掉前导 0。为什么？因为位数可能非常大（题目并不限制 n 的大小），int/long long 都存不下；而按字符串处理，几位都不怕。

判定奇偶：数字字符转。这里可以复用一个小知识——数字字符的 ASCII 值与其数值奇偶性一致（'0'=48 为偶，'1'=49 为奇，……），所以对字符 s[i] 直接 s[i] % 2 判断即可，'0'~'9' 的顺序正好保持奇偶。偶数位字符改 '0'，奇数位字符改 '1'。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++)
    {
        // 数字字符的 ASCII 奇偶性与数字本身的奇偶性一致，直接 %2 即可
        if(s[i] % 2 == 0) s[i] = '0';   // 偶数位 -> '0'
        else              s[i] = '1';   // 奇数位 -> '1'
    }
    cout << stoi(s) << endl;   // 转成整数，自动处理前导零（0001 -> 1）
    return 0;
}

运行结果

第一组输入：
12345

输出：
10101

第二组输入：
4821

输出：
1

12345：1奇数→1，2偶数→0，3奇数→1，4偶数→0，5奇数→1，得 10101。4821：4→0，8→0，2→0，1→1，得 0001 → 去前导 0 → 1。✓

详解答案与坑点

• 答案：12345 → 10101；4821 → 1。
• 复杂度：O(len)，空间 O(1)。
• 坑一：必须去掉前导 0。stoi(s) 一次性搞定（还会把 "0001" 变成 1）。但要注意：如果一堆 0 里的"去掉后是空"，那 stoi 会抛出异常吗？不会——stoi("0") = 0。全 0 的情况输出 0，符合题意。若你用 atoi(s.c_str()) 同样没问题。别手写去前导 0 循环时把"全是 0→输出空"这种边界写崩。
• 坑二：别真拿整数读。这是这题最直的坑——很多人看到"正整数 n"就 long long n; cin>>n; 然后循环 n%2。位数极多时直接溢出，WA 三连。抓住"当数字很大时换字符串视角"的思路是本题的考点。
• 少踩的彩蛋：stoi 要求参数是 string，前面要 #include <cstring>？不需要，stoi 在 <string> 里。

2. 十字爆破（预处理 ＋ 模拟）

题干

给定一个 n×m 的矩阵（每个元素是整数），对矩阵中每一个位置 (i,j)，定义它的"爆破值（十字和）"为：第 i 行所有元素之和 + 第 j 列所有元素之和 − 该位置自身的值（因为该元素既在行里又在列里被数了两遍）。请把每一个位置的爆破值按原矩阵形状输出。（牛客题号 955384）

思路

如果对每个格子都重新求它那行的和、那列的和，是 O(n·m·(n+m))，会超时。

正解是预处理：先各扫一遍，把每一行的和 row[i]、每一列的和 col[j] 算好存起来（O(n·m)）。然后每个格子 O(1) 出答案：row[i] + col[j] - g[i][j]。总和是 O(n·m)。

这里有个不小的细节：数值可能很大，和可能超 int，行和、列和、答案都要用 long long。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long LL;
const int N = 1e6 + 10;
LL row[N], col[N];        // 每行、每列的和（预处理结果，放全局避免栈溢出）
 
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<LL>> g(n, vector<LL>(m));   // 矩阵
 
    // 读入并同时累加行和、列和
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> g[i][j];
            row[i] += g[i][j];
            col[j] += g[i][j];
        }
    }
 
    // 输出每个位置的十字爆破值
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cout << row[i] + col[j] - g[i][j];
            if(j + 1 < m) cout << " ";       // 行内用空格分隔，行末换行
        }
        cout << "\n";
    }
    return 0;
}

运行结果

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

输出：
17 19 21
23 25 27
29 31 33

数一个：(0,0) 的值：行0和=6、列0和=12，减去自身 1 → 6+12-1 = 17。✓ 其余同理。

详解答案与坑点

• 答案：见上输出矩阵。
• 复杂度：O(n·m)，两遍扫描；空间 O(n·m + n + m)。
• 坑一：先算出行列和再逐格求值。 不要在求每个格子时重新扫行扫列，那样是 O(n·m·(n+m))，n、m 到 1000 就爆。预处理是本题的灵魂。
• 坑二：数据类型。行列和数据量一上来就很大，必须 LL。原题在 C 里用 %ld（在某些平台对 long long 并不安全），我这里统一用 long long + cin/cout，稳妥。
• 坑三：为什么减 g[i][j] 一次。因为该格子在行和里、列和里各被算了一遍，row[i]+col[j] 把它数了两遍，实际它只应出现一次，所以要减掉它自身一次。
• 一题多解（前缀和套路一致）：二维前缀和在这里不是必须的，因为"十字"只要行、列两条而不要整个子矩阵。理解 row/col 这两个"一维前缀统计"即可。

3. 比那名居的桃子（前缀和 ／ 定长滑动窗口）

题干

有 n 个桃子，从 1 到 n 编号。第 i 个桃子有一个快乐值 h[i] 和一个羞耻度 s[i]。现在要连续地摘取恰好 k 个桃子（也就是挑一段长度为 k 的连续区间）。希望这段区间快乐值之和最大；如果有多段区间快乐值之和一样大，则选择羞耻度之和最小的那一段。问：最优区间是从哪个编号开始的？（牛客题号 1928660）

思路

核心是：枚举所有长度为 k 的连续区间，维护窗口的两项和（快乐和 hSum、羞耻和 sSum），并记录最优起点 begin。

比较规则要写准确，优先级有先后：

1. 快乐和更大 → 直接当选；
2. 快乐和相同 且 羞耻和更小 → 才能替换原来的最优解。

注意起点从 1 开始（1-based 编号），所以要按题目要求的从 1 到 n 编号的下标存储和枚举窗口。前后给出滑动窗口思路，同时也能用前缀和。

完整可运行代码

#include <iostream>
using namespace std;
 
typedef long long LL;
const int N = 1e5 + 10;
LL n, k;
LL h[N], s[N];   // 快乐值、羞耻度，从 1 开始编号
 
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> s[i];
 
    LL left = 1, right = 1;
    LL hSum = 0, sSum = 0;
    LL hMax = -(1LL << 60);   // 快乐和最优值（用极小值初始化，保证首窗口必被选中）
    LL sMin = 0, begin = -1;  // 最优窗口的羞耻和、起点
 
    while(right <= n)
    {
        // 进窗口
        hSum += h[right];
        sSum += s[right];
 
        // 窗口超宽，收缩 left
        while(right - left + 1 > k)
        {
            hSum -= h[left];
            sSum -= s[left];
            left++;
        }
 
        // 恰好满宽，比较更新
        if(right - left + 1 == k)
        {
            if(hSum > hMax || (hSum == hMax && sSum < sMin))
            {
                begin = left;
                hMax = hSum;
                sMin = sSum;
            }
        }
        right++;
    }
    cout << begin << endl;   // 输出最优区间起点（1-based）
    return 0;
}

运行结果

第一组输入：
5 3
1 2 3 4 5
5 4 3 2 1

输出：
3

第二组输入：
4 2
5 5 5 5
1 2 3 4

输出：
1

第一组：快乐和最大的窗口是 3,4,5（和为 12），起点 3。✓ 第二组：四个窗口快乐和都是 10，羞耻和分别是 3、5、7、9，最小的是第一个窗口（起点 1）。✓

详解答案与坑点

• 答案：第一组 3，第二组 1。
• 复杂度：O(n)，每个元素进出窗口一次。
• 坑一（最隐蔽）：比较规则是"快乐优先、羞耻平手"。必须先判快乐，只有快乐相等才看羞耻。写成"先比总快乐还是先比羞耻"反了，或把两者用一个加权函数拼一起比，都会出错。
• 坑二：hMax 的初始值。我故意用 -(1LL<<60) 的极小值，保证第一个完整窗口必然被选为候选；如果你初始成 0，遇到"快乐和全是负值"的边界（不在这里出现，但严谨起见）会选不进来。用极小值初始化是更稳的写法。
• 坑三：1-based 还是 0-based。题面让输出"编号从几开始"，桃子编号 1..n，所以要按从 1 存、窗口也 1 起始来枚举。我这里 h[i]、s[i] 从 1 开始读，left、right 也从 1 开始，输出 begin 直接就是编号，不需 +1。
• 一题多解（前缀和）：先算快乐值和羞耻度的前缀和 ph、ps；枚举每个起点 i，区间[i, i+k-1] 的快乐和 = ph[i+k-1]-ph[i-1]，羞耻和 = ps[i+k-1]-ps[i-1]，再按同样规则比较。代码更短但多两个 O(n) 的辅助数组——滑动窗口省空间。两种都能 AC，笔试按习惯选即可。

Day18：双指针压缩、排序 TopK、01 背包

最后一天，难度开始热身到重头戏：双指针压缩字符串、排序选前 k、以及动态规划扛把子 01 背包。前两道是"读题即会"级别，最后一道是必须彻底理解转移的硬骨架。

1. 压缩字符串（一）（双指针）

题干

实现一个方法 compressString：给定一个字符串 param，请把它中连续相同的字符做压缩——形式为 字符+出现次数，但如果某个字符只出现一次，就不在后面加上数字（即单个字符原样保留，不加 1）。返回压缩后的字符串。

举例：aabcccccaaa → a2bc5a3。（牛客题号 NC101，核心代码模式）

思路

用一对双指针 left、right 在同一个字符串上扫描一组连续的相同字符：

• 固定 left，让 right 一直往右走，直到 param[right] != param[right+1]，此时 [left, right] 就是一组相同字符，长度 len = right-left+1；
• 压缩结果里先拼上这个字符 param[left]，如果 len > 1 再拼上 len；
• 然后 left = right+1，right = left，开始下一组。

注意：to_string(len) 把它转成字符串拼进去（数字可能超过一位，比如连续 10 个 a → a10）。

完整可运行代码

#include <iostream>
#include <string>
using namespace std;
 
class Solution
{
public:
    string compressString(string param)
    {
        string ret;
        int left = 0, right = 0, n = param.size();
        while(left < n)
        {
            // 让 right 走到这一组相同字符的末尾
            while(right + 1 < n && param[right] == param[right + 1]) right++;
 
            int len = right - left + 1;   // 这一组的连续长度
            ret += param[left];           // 先拼上这个字符
 
            if(len > 1)                    // 只有连续长度 > 1 才需要拼数字
            {
                ret += to_string(len);
            }
 
            left = right + 1;              // 跳到下一组
            right = left;
        }
        return ret;
    }
};
 
// ---- 本地测试 ----
int main()
{
    Solution so;
    cout << so.compressString("aabcccccaaa") << endl;  // 期望 a2bc5a3
    cout << so.compressString("abc") << endl;          // 期望 abc
    return 0;
}

运行结果

a2bc5a3
abc

详解答案与坑点

• 答案：aabcccccaaa → a2bc5a3；abc → abc。
• 复杂度：O(n)，每个字符被 right 扫一遍；额外空间 O(n)（ret）。
• 坑一：内层 while 的边界 right+1 < n。取 [right, right+1] 比较必须保证 right+1 不越界。写成 right+1 < n 而非 right < n，否则最后一位会越界。
• 坑二：单字符不加数字。if(len > 1) 才 to_string(len)。把 abc 压成 a1b1c1 就错了——题目明确要求连续只出现一次的就只留字符。
• 坑三：right 的推进方式。left = right + 1; right = left; 一次性跳到下一组起点，不要 right++ 慢慢挪（否则 left、right 关系会乱）。这段"双指针定位连续段"是高频套路，务必熟。
• 一题多解：也可以从 0 开始计数循环，遇到"和前一个不同"就结算上一段，本质相同。

2. chika 和蜜柑（排序 ／ TopK）

题干

chika 喜欢吃橘子。有 n 个橘子，第 i 个橘子的酸度是 a[i]、甜度是 b[i]。现在 chika 想挑出 k 个橘子。她希望甜度总和越大越好；如果多种选法甜度总和一样大，则希望酸度总和越小越好。请你输出挑选后这 k 个橘子的酸度总和和甜度总和。（牛客题号 374977）

思路

这是一道"按二维排序后取前 k 个"的贪心。排序关键字：

1. 甜度 从大到小（越大越好）；
2. 甜度相同时，酸度从小到大（越小越好）。

排好序后，取前 k 个橘子，累加它们酸度和甜度输出。为什么贪心成立？因为酸度只在"甜度相同"时才起比较作用，而排序的先后正好把"甜度高、且同甜度下酸度低"的橘子放在最前面；取前 k 个就是符合要求的 k 个。

注意酸度、甜度之和可能超 int，用 long long。

完整可运行代码

#include <iostream>
#include <algorithm>
using namespace std;
 
const int N = 2e5 + 10;
typedef pair<int, int> PII;   // 用一个 pair 装 <酸度, 甜度>
PII arr[N];
int n, k;
 
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> arr[i].first;   // 读酸度
    for(int i = 0; i < n; i++) cin >> arr[i].second;  // 读甜度
 
    // 自定义排序：甜度降序；甜度相同酸度升序
    sort(arr, arr + n, [&](const PII& x, const PII& y)
         {
             if(x.second != y.second) return x.second > y.second; // 甜度大的在前
             else return x.first < y.first;                        // 甜度相同：酸度小的在前
         });
 
    long long s = 0, t = 0;   // 前 k 个的酸度和、甜度和
    for(int i = 0; i < k; i++)
    {
        s += arr[i].first;
        t += arr[i].second;
    }
    cout << s << " " << t << endl;
    return 0;
}

运行结果

输入：
3 2
1 5 2
10 3 8

输出：
3 18

三个橘子（酸,甜）：(1,10)、(5,3)、(2,8)。按甜度降序排列：(1,10)、(2,8)、(5,3)。取前 2 个：酸度 1+2=3，甜度 10+8=18。✓

详解答案与坑点

• 答案：酸度总计 3，甜度总计 18。
• 复杂度：O(n log n)（排序）+ O(k)（取）。
• 坑一：排序关键字别写反。甜度降序是主 key。写成酸度优先就完全跑偏了。
• 坑二：long long。酸度、甜度都可能大，k 个大数相加溢出 int，必须 LL。
• 坑三：输入是"先全部酸度，再全部甜度"两行，别读串行（数组下标对应同一种橘子）。
• 一题多解 (TopK)：如果 k 特别大、数据流式进来，可用"小顶堆选出甜度最大的 k 个（同甜度取酸度小）"，把复杂度压到 O(n log k)。笔试里排序版最稳、最不易错。

3. 01 背包（动态规划 · 01 背包）

题干

有一个背包，容量为 V。有 n 件物品，第 i 件物品的体积是 v[i]、质量是 w[i]。每件物品要么选要么不选（不能重复选），求想把背包装到容量不超过 V 的前提下，能装下物品的最大总质量是多少。（牛客题号 NC145，核心代码模式，写 knapsack）

思路

01 背包的可视化过程：用一个一维数组 dp[j] 表示"容量恰好（或不超过）j 时能装的最大质量"，把物品一件一件往里加。对当前物品 $(v, w)$，容量 j 从大到小枚举：dp[j] = max(dp[j], dp[j-v] + w)（不装它 / 装它）。从大到小枚举容量是关键——这样 dp[j-v] 还是"只考虑了前一件物品"的旧值，确保每件物品最多选一次；若从小到大枚举，就可能把同一件物品装进多次，退化成完全背包。

完整可运行代码

#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
    int dp[1010] = { 0 };   // dp[j]：容量不超过 j 时的最大质量
public:
    int knapsack(int V, int n, vector<vector<int> >& vw)  // vw[i][0]=体积, vw[i][1]=质量
    {
        for(int i = 0; i < n; i++)
        {
            // 容量必须从大到小（保证每件物品只取一次）
            for(int j = V; j >= vw[i][0]; j--)
            {
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }
};
 
// ---- 本地测试 ----
int main()
{
    Solution so;
    int V = 10, n = 2;
    vector<vector<int>> vw = { {3, 1}, {4, 5} };  // (体积,质量)
    cout << so.knapsack(V, n, vw) << endl;        // 期望 6
    return 0;
}

运行结果

6

两件物品 (3,1) 和 (4,5)，总体积 3+4=7 ≤ 10，全装下，质量 1+5=6。✓

详解答案与坑点

• 答案：6。
• 复杂度：O(n·V)；空间 O(V)。
• 坑一（最核心）：容量怎么从大到小枚举。 for(j = V; j >= vw[i][0]; j--)，循环下限是 vw[i][0]（容量小于体积则装不下，直接不枚举）。枚举方向错了，答案指数级膨胀。
• 坑二：dp 数组何时重置。单次调用时初始化全 0 即可（空包最大质量 0）。如果核心代码反复调用（多组测试在同一对象上），要注意成员 dp 会残留——网上很多同学在这里翻车。稳妥起见可在方法开头 fill(dp, dp+V+1, 0) 重置一次（笔试里若题目复用一个实例，这一步值钱）。
• 坑三：状态定义是"不超过 j"还是"等于 j"。这里定义成"容量不超过 j"，因为求最多能装多少；初始化 0 就天然合理。若定义成"恰好装满 j"，初始化要置负无穷，那又是另一套写法——不要搞混定义。
• 扩展记忆：一维 dp 写法就是二维 dp[i][j] 的滚动数组优化；dp[i][j] 表示"前 i 件、容量 j"。转移 f[i][j]=max(f[i-1][j], f[i-1][j-v]+w)，滚动掉第一维就得到现在这个代码。理解二维转移，才能理解为什么一维要倒序。这是背包问题的基石，务必吃透。

本周考点一图流

把 15 道题的"模式→套路→复杂度"做成一张对照表，考前扫一眼比翻半天笔记快得多：

把这张表钉在脑子里，本周的每一道题你都能在开考前 30 秒内自动匹配到正确的套路。

到这里，笔试强训第 03 周的全部 15 道编程题就彻底拆解完了。回顾这六天，你会发现主线非常清晰：模拟题在教你"守规矩地读懂题意并翻译成边界正确的代码"；滑动窗口和双指针在教你"用一个只进不退的窗口省掉大量的内层扫描"；贪心在教你"抓住一个判定台阶，剩下的交给排序或隔位铺陈"；动态规划的两道题（打家劫舍变体和 01 背包）在教你"把问题喂进状态转移方程，再想清楚要用谁、怎么滚动"；二分答案和拓扑排序则是"求可行解的最小代价"和"处理依赖顺序"两棵模板树。

学习建议给你一句掏心窝的话：这 15 题，看懂了和会做了之间的距离，就是你亲手把每一份代码敲进编辑器并跑出 AC 的那一下。 代码我已经一行不落地贴在上面，运行结果也是本机 g++ 15.2.0 实测跑出来的，请你务必自己在本地重新 Build & Run 一遍，把每一项输出对得上号，再把易错点做成自己的错题本——尤其是"下标越界""类型溢出""枚举方向""并列取哪边""开头 handicap 初始值"这几类，它们在本周反复、刻意地出现，绝对是笔试爱挖的坑。

下周我们会进入更具挑战性的批量与高级专题，到时候见招拆招。先把这周的板斧练扎实，路是一步一步走出来。