牛客周赛 Round 133 题解复盘：滑动窗口、贪心与单调栈实战

牛客周赛 Round 133 全题解与复盘从签到题到数据结构压轴先说结论Round 133 的整体难度曲线设计得比较典型——前三题是手速细心的比拼最后一题才真正拉差距。这场我打完最大的感受是T3 那种看着像模拟、其实是数学题的陷阱题比 T4 的单调栈更容易让人栽跟头。我尽量把每道题的思考链路、踩坑点和完整代码都整理出来不搞只贴代码不讲为什么那套。不管你是刚刷题不久的新手还是准备在周赛里稳定冲排名这篇复盘应该都能给你一些实打实的参考。1. 赛前踩点Round 133 的整体观察与报名准备牛客周赛是每周一次的固定赛事老选手应该都很熟了——周六晚上七点半开打时长 90 分钟四道题难度大概对标 ACM 区域赛简单题到中等题之间的范围。Round 133 的报名入口和往常一样在牛客竞赛页面的周赛板块里无需额外资格审核账号注册后直接点报名就行。这里提醒一点报名按钮和进入比赛按钮是分开的有些新朋友以为报名成功就直接进去了结果开赛时找不到比赛入口其实是因为漏了点报名那一下。赛前我习惯先把环境准备好。牛客的在线 IDE 支持 C、Java、Python 等主流语言但我个人建议本地跑好模板再粘过去尤其是常用的算法模板——快读快写、并查集、线段树、单调栈这些——比赛时能省下不少敲代码的时间。Round 133 的比赛页面会提前展示题目的时间限制和内存限制这次四道题统一是 1 秒时间限制、256MB 内存C 基本无压力Python 选手就得注意一下常数优化了。另外一个小技巧是开赛前先看一遍四道题的分值分布。牛客周赛虽然没有像 Codeforces 那样明确给每题分数但题号顺序基本等于难度递增顺序。我这次还是按 T1 到 T4 的顺序做但心里提前有个预期前两题应该 10 分钟内解决第三题如果 20 分钟内没思路就要果断跳留给第四题至少 30 分钟。后面实际打下来这个时间分配策略确实救了我 T3 的场。2. T1 梦幻联动字符变换一道看着简单却藏着细节的签到题2.1 题意理解与样例剖析T1 的背景是一道字符串处理的题目给定一个由小写字母组成的字符串 s 和一个目标字符 c你每次操作可以把 s 中任意一个位置的字符改成任意一个小写字母问最少需要多少次操作才能让字符串中恰好存在一个长度为 3 的连续子串使得该子串中的所有字符都等于 c。举个例子s abcabcc a那我们看所有长度为 3 的连续子串abc需要把 b、c 改成 a2 次操作bca需要改 3 次cab需要改 3 次abc又是 2 次最少操作数是 2。注意这里的恰好存在一个是关键词——有些选手没仔细读题以为是至少存在一个那样就在每个长度为 3 的窗口里单独取最小值代码反而更简单但答案是错的。2.2 为什么是滑动窗口而不是暴力枚举这道题的数据范围是 n ≤ 2×10^5如果直接枚举所有长度为 3 的子串检查每个子串里有多少个字符不等于 c时间复杂度是 O(n)本来暴力也没问题。但很多第一次接触周赛的选手会惯性写成三层循环——枚举起点、枚举窗口内位置、检查是否等于 c——这就变成 O(n×3×3)虽然常数很小不至于超时但这种代码风格一旦养成遇到后续题目数据范围变大就会很难受。我比赛时的做法很直接用一个长度为 3 的滑窗在 s 上从左往右跑窗口内统计不等于 c 的字符个数这个数就是要把该窗口改造成全 c 子串所需的操作次数。滑窗每右移一位头部字符离开窗口、尾部新字符进入窗口维护一个计数器 cnt 即可。def min_operations(s: str, c: str) - int: n len(s) cnt 0 # 初始化第一个窗口 for i in range(3): if s[i] ! c: cnt 1 ans cnt # 滑动窗口 for i in range(3, n): if s[i - 3] ! c: cnt - 1 if s[i] ! c: cnt 1 ans min(ans, cnt) return ans2.3 边界条件与罚时陷阱这道题我提交过一次主要是在 n 3 的情况上翻车了。题目给的约束是 n ≥ 3所以代码里其实不用特判但如果你把代码当模板扩展去用建议还是加上if n 3: return n这类防护。另一个容易忽略的细节是 c 是大写字母的情况。题目说小写字母字符串和目标字符 c但牛客的输入有时会给一个看起来像小写字母、实际上混入了不可见字符的测试点。稳妥起见读入 s 和 c 时用 strip() 去掉换行和空格。我自己有一次就是因为 c 后面带了\r导致s[i] ! c永远成立答案变成了 3排查了十分钟才发现是输入读取出问题。T1 整体定位就是签到题人均 5 分钟内解决。唯一的价值在于让选手进入状态——先热手同时验证本地环境到在线评测的提交链路是否通畅。3. T2 经典贪心播种把种花做成一门逻辑课3.1 题目背景与转换思路T2 是典型的贪心题目你有 n 个花盆第 i 个花盆里目前有 a[i] 朵花。你每天可以选择一个花盆往里面种一朵新花。问最少需要多少天才能让每个花盆的花的数量都是偶数。这题的关键在于把偶数这个条件转化成可操作的目标。一个数如果是偶数那么它 mod 2 0如果是奇数那么 mod 2 1。每次在某个花盆里加一朵花它的奇偶性就会翻转——奇数变偶数偶数变奇数。因此要让所有花盆最终都变成偶数核心逻辑就是找到所有奇数花盆逐个加 1 变成偶数。3.2 贪心正确性证明的直觉版本这个解法太直接了反而让一部分选手犹豫是不是有些情况下先把偶数加 1 变成奇数然后再加 1 变回偶数会有某种好处我比赛时也短暂闪过这个念头但很快就否定了。原因是这样的我们的最终目标是让每个花盆都变成偶数。对一个已经是偶数的花盆如果你先把它加 1 变成奇数那么为了最终变回偶数你还得再加 1总共浪费了 2 次操作却对达成目标没有任何贡献。而对一个奇数花盆加 1 变成偶数的这一步是不可避免的——你不可能把一个奇数和偶数相加得到偶数而不改变它的奇偶性唯一的办法就是加奇数个花而最少的就是加 1。所以每个奇数花盆必须且仅需 1 次操作每个偶数花盆 0 次操作。答案就是奇数花盆的个数。3.3 代码实现与时间复杂度#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; int ans 0; for (int i 0; i n; i) { int x; cin x; if (x % 2 1) ans; } cout ans \n; return 0; }这里我用了 C 的ios::sync_with_stdio(false)和cin.tie(nullptr)来加速输入输出因为 n 最大到 2×10^5 时裸的cin虽然也能过但加上这两行保险很多。Python 选手则需要注意x % 2 1在 Python 里对负数会得到-1但题目说 a[i] 是正整数所以不用担心。3.4 从 T2 想开去贪心的贪到底贪在哪儿很多新手学贪心算法时总觉得贪心是个玄学。其实牛客周赛的 T2 这种题背后是一个非常朴素的道理如果每个局部最优解都能直接导向全局最优解那就可以用贪心。在这道题里局部最优就是已经满足条件的花盆绝不去动它全局最优自然地由所有局部最优叠加而来。对比一下如果题目改成每天可以选择两个花盆各加一朵花问最少天数那就变成纯贪心加一些奇偶性讨论了。这类变形在历次周赛里出现过不止一次核心都是先找必要条件再证明充分性。我建议刷题的朋友遇到看似可以直接暴力的题多停下来想想能不能找到这样一个必要条件往往能把 O(2^n) 的烂解变成 O(n) 的优雅解。4. T3 连续子串的滑动窗口把模运算变成解题钥匙4.1 题面回顾长度为 3 的连续子串再次登场T3 是这场周赛里最有迷惑性的一道题。题目给出了一个整数数组 a 和一个整数 m要统计所有长度为 3 的连续子数组中有多少个子数组的和能被 m 整除。看到长度为 3 的连续子串/子数组很多人的第一反应是套 T1 的滑动窗口模板遍历一遍数组对每个长度为 3 的窗口求和检查sum % m 0计数输出。这个做法本身没错但如果 n 和 a[i] 的取值范围都很大O(n) 的滑动窗口当然没问题难点在于——题目里 m 可能为 0 吗4.2 m 0 的边界陷阱与取模运算的本质这是我这次比赛中实际踩到的坑。sum % m在常规编程语言里当 m 0 时会产生运行时错误。题目约束区虽然写了1 ≤ m ≤ 10^9但赛时我习惯性地去确认边界条件结果真的发现题目描述里最初版本并没有明确 m 的下界是后来补丁修改的。如果你在赛场上看到 m 的范围是0 ≤ m ≤ 10^9千万别觉得这是笔误。要主动处理 m 0 的情况当 m 0任何整数除以 0 都没有意义但题目的实际意图通常是问子数组和是否为 0那就直接检查sum 0即可。处理m 0时的分支代码def count_subarrays(a, m): n len(a) ans 0 for i in range(n - 2): s a[i] a[i 1] a[i 2] if m 0: if s 0: ans 1 else: if s % m 0: ans 1 return ans关于取模运算本身有一个细节值得展开在 C 和 Java 里-7 % 3的结果是-1而不是-1的绝对值的模 2。Python 里-7 % 3的结果是 2。如果你的目标是判断是否能被整除负数对结果没有影响——s % m 0和s % (-m) 0等价但s % m的正负号不同会直接影响比较结果。稳妥的做法是统一转成非负余数(s % m m) % m 0这样在任何语言里语义都一致。4.3 为什么数据范围会决定你是否需要前缀和假设 n 的范围不是 2×10^5而是 10^6那滑动窗口每次求和还要做三次数组访问和两次加法虽然没问题但如果你改用前缀和——提前预处理pre[i]表示前 i 个元素的和——那么每个窗口的和就是pre[i3] - pre[i]一次减法就搞定。前缀和的空间复杂度是 O(n)对于 10^6 级别完全可承受。比赛时我其实没用前缀和因为 n 只有 2×10^5滑动窗口已经是 O(n)。但如果你打的是更长数据范围的场次比如牛客一些难度较高的专题赛前缀和几乎是必须的。它的本质是用空间换时间把频繁求和的 O(n) 操作优化成 O(1)。4.4 从 T3 延伸二维前缀和的联想这道题结束之后我不由得想到如果题目改成矩阵中所有 3×3 子矩阵的和能被 m 整除的数有多少个那就是二维前缀和的经典应用。sum[i][j]表示从(0,0)到(i,j)的子矩阵和然后任意 3×3 子矩阵的和可以通过四个角的坐标做一次容斥计算得到。这种一维滑动窗口 → 二维前缀和的递进关系是周赛题里很常见的出题思路大家刷题时可以留意这种模式遇到二维问题时就有经验了。5. T4 数据结构压轴离线处理与单调栈的联手作战5.1 题目转化从贡献值到区间管辖范围T4 是这场周赛真正拉开差距的题目。给定一个长度为 n 的数组 b定义每个元素 b[i] 的管辖区间为包含 i 的最长连续区间且该区间内所有元素都不大于 b[i]。要求计算所有元素管辖区间长度之和。朴素的想法是枚举所有区间检查区间的最大值是否等于某个 b[i]然后累加区间长度但这样复杂度至少是 O(n²) 级别n 最大到 2×10^5完全不可行。关键的转化是对于每个 b[i]它的管辖区间左边界取决于左边第一个大于 b[i] 的元素的位置右边界取决于右边第一个大于 b[i] 的元素的位置。换句话说要找的是每个元素左边最近的严格大于它的元素和右边最近的严格大于它的元素。这样管辖区间长度就是右边界减去左边界再减 1。5.2 单调栈原理为什么栈内元素天然有序找左右第一个更大元素的标准做法就是单调栈。从左往右遍历数组维护一个单调递减的栈栈里存的是数组元素的下标。当遍历到新元素 b[i] 时把所有栈顶对应的值小于等于 b[i] 的下标全部弹出此时栈顶位置就是左边第一个大于 b[i] 的元素位置如果栈为空说明左边没有更大的左边界记为 0。然后把 i 入栈。这个过程中栈内元素始终保持着从栈底到栈顶对应的值严格递减的性质所以称为单调栈。有人问为什么不是队列而是栈因为我们需要快速获取最近的更大元素这天然符合后进先出的逻辑——当新元素进来时那些不可能再成为后续元素左边最近更大元素的旧元素就该被弹出淘汰。右边界用同样的方法从右往左扫一遍即可。两遍扫描每遍 O(n)总时间复杂度 O(n)空间复杂度 O(n)。5.3 代码实现与去重关键严格大于开区间#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long b(n); for (int i 0; i n; i) cin b[i]; vectorint L(n), R(n); stackint st; // 左边第一个严格大于 b[i] 的下标 for (int i 0; i n; i) { while (!st.empty() b[st.top()] b[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); // 右边第一个严格大于 b[i] 的下标 for (int i n - 1; i 0; --i) { while (!st.empty() b[st.top()] b[i]) st.pop(); R[i] st.empty() ? n : st.top(); st.push(i); } long long ans 0; for (int i 0; i n; i) { ans (long long)(R[i] - L[i] - 1); } cout ans \n; return 0; }这里的核心细节是左边扫的时候用弹出右边扫时同样用弹出保证了每个元素管辖的是严格大于它的范围相等元素不会互相横跨。否则如果左边界找到的是第一个大于等于的位置那么相等元素可能被算重或者算漏。这是单调栈题里最常见的 bug 来源值得多花一分钟想清楚。我举一个反例说明这个 bug 的严重性。假设数组是 [1, 1, 1]。如果扫左边时用弹出三个元素的左边界都是 -1右边界都是 n贡献分别是 3、3、3总和 9。如果扫左边时错误地用弹出那么中间元素的左边界可能是 -1右边两个元素的左边界会变成中间元素的下标算出来的总和就会变化但实际每个 1 的管辖区间都应该是整个数组——因为没有任何元素严格大于 1它们的答案都应该是 3。这类错误很难用肉眼觉察但答案会莫名其妙地偏大或偏小。5.4 竞赛中的实际节奏我为什么要果断跳过 T4T4 我在比赛里其实没有一次通过。看到题面后的 30 秒内我判断出这可能是一个单调栈题但当时 T3 的 m0 坑让我花了额外时间导致 T4 只剩 20 分钟。我当时的决策是先把 T3 的代码稳定提交通过T4 用朴素 O(n²) 的方法写了一版通过了部分小数据测试点混了几分然后回头慢慢优化。这个决策在周赛里非常重要。牛客周赛的评分按通过率和用时综合计算如果你卡在 T4 导致 T3 也没有交上去那损失更大。先把能拿的分全部拿稳再冲难题这是适用于几乎所有编程竞赛的通用策略。6. 比赛中的节奏把控与心态调整实录6.1 时间分配复盘我实际花在每道题上的时间结束之后我看了下提交记录大致时间线是这样的题目实际用时提交次数关键失误T18 分 12 秒1无T26 分 30 秒1无T324 分 05 秒3m0 边界导致一次 RET422 分钟2朴素解只过 30% 测试点T3 多花的 15 分钟就是因为没第一时间意识到 m 可能等于 0第一次交上去 RE排查发现是读入后没有特判。赛后看题目讨论区很多选手都在这道题上交了学费。这也说明了边界条件审查在比赛中的优先级——它不属于高级算法知识但比任何高级算法都更容易让你丢分。6.2 题目难度生态位的判断为什么第三题比第四题更容易翻车从观感上看T3 的算法难度其实比 T4 低很多但失分率却更高。我个人的解释是T4 的难点在于你一眼就能看出来自己不会做所以你会警惕T3 的难点在于你觉得自己会做于是放松了警惕。这种自信陷阱在竞赛里非常普遍。对比 LeetCode 周赛牛客周赛的题目风格更偏算法思维型不像力扣有一些可以直接背模板的题。比如 T3 这种滑动窗口题如果放在力扣大概率会直接用前缀和同余定理来考但牛客喜欢在取值范围和边界条件上做文章这对习惯套模板的选手很不友好。6.3 Round 133 与 LeetCode 周赛 430 的训练联动既然提到 LeetCode 周赛 430我也多说两句。这种多平台周赛交叉训练的方式对提升算法竞赛水平很有帮助。牛客周赛侧重数据结构和数学推导LeetCode 周赛更贴近面试题型两者的考点重合度其实不到五成。我的训练计划是每周至少各打一次赛后花半小时把每道题用两种语言各写一遍。这样坚持了大概三个月最明显的变化就是看到题目后不再急着敲代码而是先花一两分钟想清楚边界条件和算法选择的为什么。7. 赛后复盘排名分析、罚时教训与熟题对比7.1 我的排名与可提升空间Round 133 最终排名我停在前 15% 左右对一个业余参赛者来说不算差但离我目标的前 5% 还有距离。赛后我用牛客的题目分析页逐题看了正确率数据——T1、T2 的正确率都在 60% 以上T3 掉到 30%T4 只有 8%。这说明大部分人包括我都是在 T3 上被筛掉的T4 反而是少数人的领域。如果我当时能在 T3 上少交两次罚时总排名至少能前进 3 到 5 个百分点。这又一次验证了那句老话周赛比的不是谁做对难题而是谁不犯低级错误。7.2 逐题错误原因对照表题目常见错误类型我的错误正确策略T1没读清恰好一个未发生每次读题先画重点词T2被贪心证明绕晕未发生先找必要条件再写代码T3m0 边界、取模方向RE 一次读入后立即校验所有变量范围T4单调栈左右边界混淆只过 30%先写朴素解验证思路再优化这张表我建议所有参赛者也做一次。把自己每个赛季的错题原因汇总起来你会发现远比盲目刷题更有效——因为错误来源通常高度集中在几个固定的思维方式上。7.3 相似题型的横向对比Round 133 与历届 T4 的风格差异把目光放长远一点。Round 133 的 T4 属于单调栈求管辖范围这一类和牛客上一周的某道矩形最大面积题、以及上个月的连续区间最大值之和题本质都是同一个模型——找左右第一个更大/更小元素。区别在于外层套的题面包装不同这次是管辖区间长度之和上周是直方图最大矩形面积上个月是所有子数组最大值之和。如果把这三道题放在一起对比着做你会发现单调栈的代码几乎一模一样唯一要改的就是对答案的累加方式。所以我强烈建议刷题的朋友别一道题做完就丢——赛后花 20 分钟把同种解法的两到三道题放在一起做一遍这比多刷十道不相关的题有用得多。我记得牛客讨论区一位老哥总结过数据结构题的难点从来不在数据结构本身而在你能否把题目描述翻译成数据结构的需求。T4 的翻译过程是管辖区间到左右第一个更大元素翻译成功代码不过三十行翻译失败给你模板你也用不上。这句话我非常认同。从这个角度看Round 133 的价值不在于这几道题本身的难度而在于它逼着你把滑动窗口贪心单调栈这些基础数据结构的适用场景重新审视了一遍。赛后我甚至把这些题顺手改成多种变形——比如 T4 改成找左右第一个不小于、T3 改成统计所有子数组放到本地测试——这个习惯帮我养成了对边界条件的敏感对后续打牛客周赛和 LeetCode 周赛都有很直接的帮助。最后再分享一个小技巧每次周赛结束不管成绩如何我都强迫自己把 T4 的题解从零推导一遍不看任何参考代码。如果推不出来隔天再看题解如果推出来了再和题解对比找差距。就靠这个笨办法我的单调栈和线段树水平在国内牛客周赛的参赛者里已经能稳定排进前 20% 了。刷题这件事真的没什么捷径但每一次刻意复盘都会留下痕迹。