企业官网建设流程全解析

牛客周赛 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 = "abcabc"，c = 'a'，那我们看所有长度为 3 的连续子串：

• "abc"：需要把 b、c 改成 a，2 次操作
• "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 ans

2.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[i+3] - 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; vector<long long> b(n); for (int i = 0; i < n; ++i) cin >> b[i]; vector<int> L(n), R(n); stack<int> 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 竞赛中的实际节奏：我为什么要果断跳过 T4

T4 我在比赛里其实没有一次通过。看到题面后的 30 秒内，我判断出这可能是一个单调栈题，但当时 T3 的 m=0 坑让我花了额外时间，导致 T4 只剩 20 分钟。我当时的决策是：先把 T3 的代码稳定提交通过，T4 用朴素 O(n²) 的方法写了一版，通过了部分小数据测试点，混了几分，然后回头慢慢优化。

这个决策在周赛里非常重要。牛客周赛的评分按"通过率和用时"综合计算，如果你卡在 T4 导致 T3 也没有交上去，那损失更大。先把能拿的分全部拿稳，再冲难题，这是适用于几乎所有编程竞赛的通用策略。

6. 比赛中的节奏把控与心态调整实录

6.1 时间分配复盘：我实际花在每道题上的时间

结束之后我看了下提交记录，大致时间线是这样的：

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 逐题错误原因对照表

这张表我建议所有参赛者也做一次。把自己每个赛季的错题原因汇总起来，你会发现远比盲目刷题更有效——因为错误来源通常高度集中在几个固定的思维方式上。

7.3 相似题型的横向对比：Round 133 与历届 T4 的风格差异

把目光放长远一点。Round 133 的 T4 属于"单调栈求管辖范围"这一类，和牛客上一周的某道"矩形最大面积"题、以及上个月的"连续区间最大值之和"题，本质都是同一个模型——找左右第一个更大/更小元素。区别在于外层套的题面包装不同：这次是"管辖区间长度之和"，上周是"直方图最大矩形面积"，上个月是"所有子数组最大值之和"。

如果把这三道题放在一起对比着做，你会发现单调栈的代码几乎一模一样，唯一要改的就是对答案的累加方式。所以我强烈建议刷题的朋友别一道题做完就丢——赛后花 20 分钟把同种解法的两到三道题放在一起做一遍，这比多刷十道不相关的题有用得多。

我记得牛客讨论区一位老哥总结过：数据结构题的难点从来不在数据结构本身，而在你能否把题目描述"翻译"成数据结构的需求。T4 的翻译过程是"管辖区间"到"左右第一个更大元素"，翻译成功，代码不过三十行；翻译失败，给你模板你也用不上。这句话我非常认同。

从这个角度看，Round 133 的价值不在于这几道题本身的难度，而在于它逼着你把"滑动窗口""贪心""单调栈"这些基础数据结构的适用场景重新审视了一遍。赛后我甚至把这些题顺手改成多种变形——比如 T4 改成"找左右第一个不小于"、T3 改成"统计所有子数组"，放到本地测试——这个习惯帮我养成了对边界条件的敏感，对后续打牛客周赛和 LeetCode 周赛都有很直接的帮助。

最后再分享一个小技巧：每次周赛结束，不管成绩如何，我都强迫自己把 T4 的题解从零推导一遍，不看任何参考代码。如果推不出来，隔天再看题解；如果推出来了，再和题解对比找差距。就靠这个笨办法，我的单调栈和线段树水平在国内牛客周赛的参赛者里已经能稳定排进前 20% 了。刷题这件事，真的没什么捷径，但每一次刻意复盘都会留下痕迹。