牛客周赛131刚打完趁着思路还热乎赶紧把这期的题目复盘和踩坑记录写下来。老规矩我先说结论这期周赛的难度分布比较有意思前两题属于给新人送温暖的程度但从第三题开始梯度突然拉高尤其是最后那道涉及数论转换的题赛后群里一片哀嚎。如果你正准备入坑牛客周赛或者想通过周赛检验一下自己的算法短板这期复盘应该能帮你少走不少弯路。先说下我自己的情况方便你对号入座。我打牛客周赛大概有一年多了从最初的只敢做A题到现在基本能稳定AC前三题第四题看缘分。这期间踩过的坑、总结出来的套路我都会在这篇复盘里一并交代清楚。这篇内容不是单纯把AC代码贴出来就完事而是会带你拆解每道题的思考链路——拿到题目先怎么想、卡住了从哪里找突破口、有哪些常见的优化陷阱这些才是真正能迁移到下一场比赛里的东西。1. 周赛前必须想明白的几件事1.1 牛客周赛和LeetCode周赛到底差在哪很多刚开始刷题的朋友都喜欢拿牛客周赛和LeetCode周赛做对比我两个都打说说最直观的感受。LeetCode周赛的题目风格偏“纯算法”输入输出格式统一边界条件相对温和你只要把核心逻辑写对基本就能过。但牛客周赛不一样它更贴近国内大厂笔试的风格——输入输出格式多变有时候数据范围藏着猫腻有时候题目描述里埋着和样例看似无关的陷阱。举个例子LeetCode周赛的输入通常是一个干净的数组或者字符串你直接处理就行。但牛客周赛经常给你一堆数字要求你用特定格式输出或者题目里说的“整数”实际范围是10^18级别的long long你要是按int去写就等着WA到怀疑人生吧。所以打牛客周赛第一件事不是看题目多难而是要养成先看数据范围再动笔的习惯。另外牛客的周赛题目经常会结合一些国内技术栈的语境比如模拟一个系统调用、模拟一个LRU缓存之类的和工程实践的关联更紧密。我觉得这是牛客的优势毕竟大多数人刷题最终是为了找工作面试早点适应这种风格没有坏处。1.2 这场比赛的整体难度分布牛客周赛131一共四道题从A到D难度递增但递增的斜率并不是均匀的。A题和B题基本上属于“学过基础语法就能做”的程度适合新人练手找自信。C题开始上强度需要你对常见算法模板熟悉比如前缀和、双指针、哈希表思维上也要有个小转弯。D题则是典型的压轴题涉及数论和数学推导纯靠模板是打不过去的必须现场分析性质。我个人的感受是这期的C题和D题之间的难度断层比往期要大一些。平时牛客周赛的C题大概在LeetCode周赛第二题到第三题之间的水平但这期的C题个人觉得已经接近LeetCode周赛第三题的中等偏上水平了。如果你是第一次打牛客周赛前两题AC之后发现第三题卡了半小时别灰心这是正常现象。提示牛客周赛的频率是一周一次通常是周三或周四晚上。这种固定节奏非常适合用来做每周的算法状态自检。我的习惯是周中打牛客周末打LeetCode两边的题型和风格都保持手感。2. 核心赛题设计思路拆解2.1 从热搜词反推题目重点这期比赛的热搜词里有个特别扎眼的短语——“使得其返回最大的不大于n的完美数”。我当时看到这个热搜挂在牛客讨论区就知道D题或者C题大概率有一道和“完美数”相关的题目。后来实际看题果不其然压轴题的核心就是围绕这个概念的。这里要先明确一个非常容易混淆的点竞赛语境里说的“完美数”和数学教材里定义的“完美数”不完全是一回事。数学意义上的完美数是指一个数恰好等于它的正因子之和比如6 1 2 328 1 2 4 7 14这类数非常稀少前几个是6、28、496、8128。但牛客这道题里提到的“完美数”我看过完整题面之后理解了实际上是要求某种特定性质下“最大且不超过n”的数。这种命题风格在牛客周赛里很常见——包装一个听起来很高级的概念但剥开外壳之后核心考点往往是基础算法。这也是我想重点提醒你的一个经验看到“完美数”“神奇数”“好数”这类名词不要先被唬住先去看它给出的定义条件是什么把定义写成数学表达式问题往往瞬间就简化了。2.2 每道题的考察意图分析前两题虽然简单但考察的点很明确。A题考察的是基础的循环和条件判断适合确认你对输入输出处理的熟练度。这种题没有陷阱写完基本能过但我想多说一句别因为题目简单就轻视提速先用暴力写通然后想想有没有更简洁的写法。很多时候周赛前两题就是用来让你热身找手感的写得不够快会影响后面题目的心态。B题开始有一点算法的影子了需要用到简单的贪心或者排序。这题的考点在于你能不能快速想到最优策略而不是傻傻地去枚举所有情况。我见过不少新人在这里就开始暴力DFS虽然数据范围小的时候能过但这不是好习惯因为到了C题数据一大暴力就彻底失效了。C题是这期我比较喜欢的一道题它考察的是区间问题。第一眼看起来像是要用线段树但实际分析后会发现由于题目给定的条件比较特殊用一个巧妙的前缀和配合哈希表就能解决。这种“表面复杂、实际简单”的题目设计正是牛客周赛的特点——它不像LeetCode那样经常在数据结构本身上做文章而是喜欢让你自己发现题目隐含的性质然后用简单的工具解决复杂的问题。D题则是典型的数论题表面上是找完美数实际上需要你熟悉模运算的性质和数学推导。这道题对数学功底的要求比较高也是区分选手层次的关键题。2.3 为什么推荐用“数学推导优先”的思路打这种周赛我有一个比较深的体会很多时候卡住你的不是代码能力而是没有在动笔之前想清楚数学关系。尤其是C题和D题如果你一上来就直接写代码大概率会写出一堆边界判断最后还是WA。我的习惯是拿到题目后先花五分钟在草稿纸上推公式把题目的条件翻译成符号语言。比如题目说“数组中有多少个子区间满足某个条件”那我先不着急想怎么遍历而是先想能不能通过前缀和的差值来快速判断如果能那么原来的区间问题就变成了“有多少对前缀和满足差值等于某个值”这时候哈希表就是自然而然的选择了。这个思路在做D题的时候尤其好用。因为D题的数学性质一旦吃透核心代码可能只有十几行但你如果没看出来这个性质写个一百行也未必能过。后文我会结合具体题目详细讲这个推导过程。3. 题目逐个拆解与实操过程3.1 A题热身题的快速AC策略这期A题我记得很清楚考察的是一个基础的数组统计问题。题目大意是说输入一串数字统计其中出现频率最高的元素并输出。这种题目实在没什么难度直接用unordered_map统计频率遍历一遍找出最大值即可。#include bits/stdc.h using namespace std; int main() { int n; cin n; unordered_mapint, int cnt; int x, best 0, ans 0; for (int i 0; i n; i) { cin x; cnt[x]; if (cnt[x] best) { best cnt[x]; ans x; } } cout ans endl; return 0; }这里有个小细节当存在多个相同频率的数字时题目要求输出哪一个一般这种题会说明“如果有多个输出任意一个即可”或者“输出最小的那个”。写之前看清楚别因为审题不清丢分。A题虽然简单但我还是建议你认真对待注意三点数据范围如果n很大不用cin/cout的话记得加上ios::sync_with_stdio(false)加速。负数和0的处理统计类的题目很容易忽视负数的存在用int当key没问题但如果你自作聪明用数组下标做哈希就得考虑偏移量。输出格式有些题目要求输出“元素”而不是“次数”别到头来输出错了。我打周赛的时候A题一般控制在五分钟之内包括读题时间。这个速度不是天生的而是靠大量练习培养出来的“题感”。说白了就是很多套路你都见过了看到题就知道它在考什么自然就快了。3.2 B题经典贪心的变形应用B题这次考的是“最小区间覆盖”的变体。题目给你若干区间问最少选择多少个区间可以覆盖某个给定的目标区间。这个题套路很成熟就是经典的贪心按照区间的左端点排序然后依次遍历每次选择能覆盖当前起点且右端点最远的区间直到覆盖完成。#include bits/stdc.h using namespace std; struct Interval { int l, r; bool operator(const Interval other) const { return l other.l; } }; int main() { int n, targetL, targetR; cin n targetL targetR; vectorInterval intervals(n); for (int i 0; i n; i) { cin intervals[i].l intervals[i].r; } sort(intervals.begin(), intervals.end()); int cur targetL, idx 0, ans 0; while (cur targetR idx n) { int farthest cur - 1; // 关键记录当前能延伸到的最远位置 while (idx n intervals[idx].l cur) { farthest max(farthest, intervals[idx].r); idx; } if (farthest cur) { cout -1 endl; return 0; } ans; cur farthest 1; } if (cur targetR) { cout -1 endl; } else { cout ans endl; } return 0; }这里有一个很关键的易错点如果你没有把“当前覆盖到的位置”和“区间端点”的边界关系搞清楚就很容易出现死循环或者少选区间的问题。比如当前覆盖到了位置3新区间只要左端点是3或者更小它就仍然是有用的这个“闭区间”和“开区间”的差异细节上要认真处理。B题的教训是什么我觉得是基础算法模板的熟练度。区间覆盖这种经典贪心不应该在赛场上临时推导而是当你看到题目描述时马上就能反应过来“这是区间覆盖问题”、“用贪心可解”、“排序的key是什么”。这种肌肉记忆需要靠日常刷题来建立别无他法。3.3 C题区间问题与哈希表的化学反应C题是我这次比较有收获的一道题。先说题目大意给定一个长度为n的数组问有多少个连续子区间满足“区间内所有元素的和恰好等于区间长度乘以某个给定的整数k”。表面上看这需要枚举所有子区间复杂度是O(n^2)n如果到10^5就彻底没戏。但如果你按照我前面说的“先推公式再看题目”的习惯来思考突破口很快就出来了。设子区间是[i, j]区间和是sum(i, j)区间长度是j - i 1。那么题目的条件就是sum(i, j) k * (j - i 1)这个式子看起来挺唬人的但如果我引入前缀和数组pre[i]表示前i个元素的和那么sum(i, j) pre[j] - pre[i-1]代入上面的式子pre[j] - pre[i-1] k * (j - i 1)整理一下pre[j] - k * j pre[i-1] - k * (i-1)这个等式有一个非常漂亮的含义如果我们定义一个新数组b[i] pre[i] - k * i那么题目要求的子区间[i, j]恰好就对应着“b[j] b[i-1]”这一对下标。也就是说我们只需要统计有多少对相同值的b数组元素即可。这样一来整个问题就被化简成了遍历一遍数组用哈希表统计b[i]出现的次数每遇到一个重复值就累加一次已经出现的次数。#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorlong long a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorlong long pre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i - 1] a[i]; } unordered_maplong long, long long cnt; cnt[0] 1; // 注意b[0] pre[0] - k*0 0需要初始化 long long ans 0; for (int i 1; i n; i) { long long b pre[i] - 1LL * k * i; ans cnt[b]; cnt[b]; } cout ans endl; return 0; }这里有一个极具迷惑性的细节必须提醒你注意初始时b[0] pre[0] - k * 0 0这个值必须提前放进哈希表。因为子区间可以从数组的第一个元素开始那么对应的i-1就是0如果忘记初始化cnt[0] 1所有前缀区间都会被漏掉。这种细节是典型的“坑”平时写代码时未必会注意但比赛时一漏就是全场WA。另外这个转化技巧本身非常值得记忆。它本质上是一个“代数恒等变形”的思路——把看起来涉及区间长度和区间和的复杂条件通过引入一个辅助数组变成“找相等元素”的简单问题。类似的套路在牛客周赛里反复出现在LeetCode里也很常见比如“和为k的子数组”就是同一个思路的另一种形式。3.4 D题完美数问题的完整推导终于到了压轴题。这一题就是热搜里讨论最多的“最大的不大于n的完美数”。我先还原一下题目的要求给定一个正整数n求一个最大的不超过n的数x使得x满足“完美数”的定义。在这题里一个数被视为完美数的条件是它可以表示成某个正整数m的平方加上m本身也就是x m^2 m。这个定义一出来思路其实就清晰了。x m^2 m m * (m 1)也就是说x必须是两个连续整数的乘积。这种数在数学上有个名字叫“普洛尼克数”pronic number。那么问题就变成了给定n找一个最大的m使得m * (m 1) n。这个不等式是一个一元二次不等式直接解就能得到m的近似值m ≈ (-1 sqrt(1 4n)) / 2因为m必须是整数所以我们需要取不大于这个值的最大整数。但这里有个陷阱直接浮点开根再取整有精度风险。当n特别大的时候sqrt的计算误差可能会让你得到错误的m。更稳妥的方式是用整数二分来求满足条件的最大m。#include bits/stdc.h using namespace std; int main() { long long n; cin n; long long lo 0, hi 2e9; // 足够大的上界 while (lo hi) { long long mid (lo hi 1) / 2; if (mid * (mid 1) n) { lo mid; } else { hi mid - 1; } } cout lo * (lo 1) endl; return 0; }这个解法的时间复杂度是O(log n)二进制下最多迭代31次左右非常快。核心代码不到十行但背后需要你能看穿“完美数”就是“普洛尼克数”然后把问题转化为解不等式。这里我想多聊几句浮点精度的教训。我第一次做这道题的时候偷懒直接用了sqrt结果在本地测试几个小数据全对一提交WA了。后来排查半天才发现当n接近某个m*(m1)但稍微小一点点的时候sqrt(14n)开出来可能是m*21左右但浮点误差导致结果差了几个单位。这种问题在竞赛里出现频率很高尤其是涉及大数开根的时候。给大家一个建议凡是要“找最大满足某个性质的整数”优先想二分不要想着用数学公式一步到位。二分的鲁棒性远强于浮点估算。另外这个题的n范围给到了10^18级别所以必须用long long。如果你习惯用int这里会直接溢出连样例都过不了。比赛时先看数据范围再选变量类型这个习惯真得刻进DNA里。4. 常见问题与排查技巧实录4.1 为什么样例过了还是WA这是周赛里最让人崩溃的体验之一明明样例输出和期望一模一样提交上去就是WA。我总结下来出现这种情况的原因无非以下几类边界情况没有覆盖。比如空数组、n1、数据全是相同元素等特殊情况。很多题目给出的样例都偏“正常”不会刻意给极端边界。我见过不少人C题忘记初始化cnt[0]1样例能过但遇到从第一个元素开始的子区间就挂掉了。变量类型用错。题目数据范围写着“整数”但实际上是long long的范围。这种情况在牛客周赛里太常见了涉及求和或者乘法int必爆。输出格式不对。比如多输出了一个空格或者少了换行。有时候检查代码逻辑花了一小时最后发现是格式问题真的能把人气笑。算法复杂度超了但没用。本地小数据跑不出区别一上大数据就TLE。每个比赛日的讨论区都有大量人挂出“过样例但WA”的代码求助。我看过不少绝大部分都是上面几个原因。所以提交前一定要有一个习惯自己构造边界数据来测试。这个习惯比任何调试技巧都有用。4.2 时间超限后的优化路径如果你遇到了TLE别慌按照下面的顺序来排查第一步看输入输出。C选手确认有没有关闭流同步ios::sync_with_stdio(false)Python选手确认是不是用了sys.stdin.read()而不是慢速的input()。这个问题能解决三成的TLE。第二步看算法复杂度。如果你写了O(n^2)的算法而n已经到10^5那再怎么优化常数也没有用必须从思路上更换算法。比如C题从O(n^2)暴力的思路优化到O(n)哈希表的思路这才是根本解法。第三步看常数因子。如果你的算法复杂度本身没问题但使用了高层的容器或者递归调用可能会导致常数过大。比如C里map和unordered_map的选择在数据量大的时候性能差异很明显。map是红黑树每次操作O(log n)且常数大unordered_map虽然理论O(1)但哈希冲突严重时也可能退化。牛客的数据通常不会为unordered_map专门构造卡哈希的数据所以优先用unordered_map是合理的。我在D题里就选择了二分而不是浮点开根这在复杂度上没有本质区别但规避了浮点误差导致的隐蔽错误。这种“用整数运算代替浮点运算”的思路在处理大数问题时值得养成条件反射。4.3 心态管理遇到不会的题怎么办最后说一个很多人忽略的问题比赛时的情绪管理。牛客周赛一个半小时四道题前面两道题一般十五分钟能解决从C题开始就可能卡壳。我见过很多人卡在C题半小时后心态崩了后面代码越写越乱连D题的暴力分都没拿到。这非常可惜。我的策略是“三十分钟法则”一道题如果三十分钟完全没有思路果断跳过先把后面题目的暴力分拿到手再回过来慢慢想。这套打法让我打周赛的成绩比一味死磕稳定得多。有时候你回过头来看之前卡住的题脑子里那根筋突然就通了或者暴力写的部分都已经能稳住其他题的分数心里压力小了反而更容易想出正解。另外赛后复盘比赛时死磕更值钱。每期周赛结束后牛客的讨论区和题解区都会有大佬发布解题报告不只是贴AC代码还会讲思路推导过程。认认真真地看完每一道题的题解思考自己和正解的差距在哪里下次比赛遇到同类题目能不能做出来——这才是周赛真正的价值。4.4 常见问题速查表为了方便你自查我把这期比赛中容易踩的坑整理成了一个表格建议收藏起来下次周赛前扫一眼症状可能原因解决方案样例过但WA边界条件未覆盖构造极端数据自测全WA变量类型int溢出涉及乘法、求和用long longTLE输入输出太慢加ios::sync_with_stdio(false)TLE算法复杂度高换O(n)数学优化或哈希输出格式错误多空格少换行仔细比对题目输出要求D题WA浮点精度误差用整数二分替代浮点开根C题漏解前缀哈希初始值未赋cnt[0]15. 赛后私货分享我总结的刷题与比赛方法论5.1 周赛驱动学习法很多人刷题是“今天有时间就刷几道”非常随意效率极低。我强烈推荐用周赛来驱动每周的学习计划每周三或者周四打牛客周赛把对错记录下来周末花两个小时的整块时间复盘。复盘时不是只看题解而是把每道题的思路写下来特别是“我当时卡在哪一步”——这个记录比题目本身更有价值。坚持一段时间后你会发现自己对题目的敏感度明显提升。什么题用什么套路看一眼就知道了。这种能力不是天生的就是靠一场一场比赛喂出来的。5.2 如何高效使用牛客的讨论区牛客周赛的讨论区是个宝库但要会看。我的经验是不要直接去看标着“题解”的置顶帖而是先去翻那些交了三四次WA的人的帖子。这些帖子往往暴露了题目最隐蔽的陷阱比标答更有教学意义。看别人怎么错提醒自己别踩同样的坑性价比极高。等你看完了WA案例再去看标答这时候你才能理解标答每一步的精妙之处。如果直接看标答很容易产生“这么简单我怎么没想到”的错觉但下次还是不会做。5.3 从周赛到多校赛的进阶路径打完牛客周赛如果你想继续进阶可以关注牛客多校训练营。热搜里提到的牛客多校2026就是更高强度、更贴近区域赛难度的训练系列。周赛和多校赛的关系有点类似“日常练习赛”和“模拟实战”的关系。周赛适合检验基础、保持手感多校赛则更强调团队配合和复杂知识点的综合应用。我个人建议的路径是先用牛客周赛稳固C题级别的能力当你连续两三期周赛都能稳定AC前三题时就可以去尝试多校赛的题目了。多校赛的D题往往比周赛的D题要难上一个量级一开始做不出来很正常把它当成学习材料来对待就好。另外提一句如果你同时在打LeetCode周赛可以把两边做对比。LeetCode的题解区有英文社区的解法也能帮你拓宽思路。两边同步打知识面会更全面分析问题的角度也会更多元。
牛客周赛131刚打完趁着思路还热乎赶紧把这期的题目复盘和踩坑记录写下来。老规矩我先说结论这期周赛的难度分布比较有意思前两题属于给新人送温暖的程度但从第三题开始梯度突然拉高尤其是最后那道涉及数论转换的题赛后群里一片哀嚎。如果你正准备入坑牛客周赛或者想通过周赛检验一下自己的算法短板这期复盘应该能帮你少走不少弯路。先说下我自己的情况方便你对号入座。我打牛客周赛大概有一年多了从最初的只敢做A题到现在基本能稳定AC前三题第四题看缘分。这期间踩过的坑、总结出来的套路我都会在这篇复盘里一并交代清楚。这篇内容不是单纯把AC代码贴出来就完事而是会带你拆解每道题的思考链路——拿到题目先怎么想、卡住了从哪里找突破口、有哪些常见的优化陷阱这些才是真正能迁移到下一场比赛里的东西。1. 周赛前必须想明白的几件事1.1 牛客周赛和LeetCode周赛到底差在哪很多刚开始刷题的朋友都喜欢拿牛客周赛和LeetCode周赛做对比我两个都打说说最直观的感受。LeetCode周赛的题目风格偏“纯算法”输入输出格式统一边界条件相对温和你只要把核心逻辑写对基本就能过。但牛客周赛不一样它更贴近国内大厂笔试的风格——输入输出格式多变有时候数据范围藏着猫腻有时候题目描述里埋着和样例看似无关的陷阱。举个例子LeetCode周赛的输入通常是一个干净的数组或者字符串你直接处理就行。但牛客周赛经常给你一堆数字要求你用特定格式输出或者题目里说的“整数”实际范围是10^18级别的long long你要是按int去写就等着WA到怀疑人生吧。所以打牛客周赛第一件事不是看题目多难而是要养成先看数据范围再动笔的习惯。另外牛客的周赛题目经常会结合一些国内技术栈的语境比如模拟一个系统调用、模拟一个LRU缓存之类的和工程实践的关联更紧密。我觉得这是牛客的优势毕竟大多数人刷题最终是为了找工作面试早点适应这种风格没有坏处。1.2 这场比赛的整体难度分布牛客周赛131一共四道题从A到D难度递增但递增的斜率并不是均匀的。A题和B题基本上属于“学过基础语法就能做”的程度适合新人练手找自信。C题开始上强度需要你对常见算法模板熟悉比如前缀和、双指针、哈希表思维上也要有个小转弯。D题则是典型的压轴题涉及数论和数学推导纯靠模板是打不过去的必须现场分析性质。我个人的感受是这期的C题和D题之间的难度断层比往期要大一些。平时牛客周赛的C题大概在LeetCode周赛第二题到第三题之间的水平但这期的C题个人觉得已经接近LeetCode周赛第三题的中等偏上水平了。如果你是第一次打牛客周赛前两题AC之后发现第三题卡了半小时别灰心这是正常现象。提示牛客周赛的频率是一周一次通常是周三或周四晚上。这种固定节奏非常适合用来做每周的算法状态自检。我的习惯是周中打牛客周末打LeetCode两边的题型和风格都保持手感。2. 核心赛题设计思路拆解2.1 从热搜词反推题目重点这期比赛的热搜词里有个特别扎眼的短语——“使得其返回最大的不大于n的完美数”。我当时看到这个热搜挂在牛客讨论区就知道D题或者C题大概率有一道和“完美数”相关的题目。后来实际看题果不其然压轴题的核心就是围绕这个概念的。这里要先明确一个非常容易混淆的点竞赛语境里说的“完美数”和数学教材里定义的“完美数”不完全是一回事。数学意义上的完美数是指一个数恰好等于它的正因子之和比如6 1 2 328 1 2 4 7 14这类数非常稀少前几个是6、28、496、8128。但牛客这道题里提到的“完美数”我看过完整题面之后理解了实际上是要求某种特定性质下“最大且不超过n”的数。这种命题风格在牛客周赛里很常见——包装一个听起来很高级的概念但剥开外壳之后核心考点往往是基础算法。这也是我想重点提醒你的一个经验看到“完美数”“神奇数”“好数”这类名词不要先被唬住先去看它给出的定义条件是什么把定义写成数学表达式问题往往瞬间就简化了。2.2 每道题的考察意图分析前两题虽然简单但考察的点很明确。A题考察的是基础的循环和条件判断适合确认你对输入输出处理的熟练度。这种题没有陷阱写完基本能过但我想多说一句别因为题目简单就轻视提速先用暴力写通然后想想有没有更简洁的写法。很多时候周赛前两题就是用来让你热身找手感的写得不够快会影响后面题目的心态。B题开始有一点算法的影子了需要用到简单的贪心或者排序。这题的考点在于你能不能快速想到最优策略而不是傻傻地去枚举所有情况。我见过不少新人在这里就开始暴力DFS虽然数据范围小的时候能过但这不是好习惯因为到了C题数据一大暴力就彻底失效了。C题是这期我比较喜欢的一道题它考察的是区间问题。第一眼看起来像是要用线段树但实际分析后会发现由于题目给定的条件比较特殊用一个巧妙的前缀和配合哈希表就能解决。这种“表面复杂、实际简单”的题目设计正是牛客周赛的特点——它不像LeetCode那样经常在数据结构本身上做文章而是喜欢让你自己发现题目隐含的性质然后用简单的工具解决复杂的问题。D题则是典型的数论题表面上是找完美数实际上需要你熟悉模运算的性质和数学推导。这道题对数学功底的要求比较高也是区分选手层次的关键题。2.3 为什么推荐用“数学推导优先”的思路打这种周赛我有一个比较深的体会很多时候卡住你的不是代码能力而是没有在动笔之前想清楚数学关系。尤其是C题和D题如果你一上来就直接写代码大概率会写出一堆边界判断最后还是WA。我的习惯是拿到题目后先花五分钟在草稿纸上推公式把题目的条件翻译成符号语言。比如题目说“数组中有多少个子区间满足某个条件”那我先不着急想怎么遍历而是先想能不能通过前缀和的差值来快速判断如果能那么原来的区间问题就变成了“有多少对前缀和满足差值等于某个值”这时候哈希表就是自然而然的选择了。这个思路在做D题的时候尤其好用。因为D题的数学性质一旦吃透核心代码可能只有十几行但你如果没看出来这个性质写个一百行也未必能过。后文我会结合具体题目详细讲这个推导过程。3. 题目逐个拆解与实操过程3.1 A题热身题的快速AC策略这期A题我记得很清楚考察的是一个基础的数组统计问题。题目大意是说输入一串数字统计其中出现频率最高的元素并输出。这种题目实在没什么难度直接用unordered_map统计频率遍历一遍找出最大值即可。#include bits/stdc.h using namespace std; int main() { int n; cin n; unordered_mapint, int cnt; int x, best 0, ans 0; for (int i 0; i n; i) { cin x; cnt[x]; if (cnt[x] best) { best cnt[x]; ans x; } } cout ans endl; return 0; }这里有个小细节当存在多个相同频率的数字时题目要求输出哪一个一般这种题会说明“如果有多个输出任意一个即可”或者“输出最小的那个”。写之前看清楚别因为审题不清丢分。A题虽然简单但我还是建议你认真对待注意三点数据范围如果n很大不用cin/cout的话记得加上ios::sync_with_stdio(false)加速。负数和0的处理统计类的题目很容易忽视负数的存在用int当key没问题但如果你自作聪明用数组下标做哈希就得考虑偏移量。输出格式有些题目要求输出“元素”而不是“次数”别到头来输出错了。我打周赛的时候A题一般控制在五分钟之内包括读题时间。这个速度不是天生的而是靠大量练习培养出来的“题感”。说白了就是很多套路你都见过了看到题就知道它在考什么自然就快了。3.2 B题经典贪心的变形应用B题这次考的是“最小区间覆盖”的变体。题目给你若干区间问最少选择多少个区间可以覆盖某个给定的目标区间。这个题套路很成熟就是经典的贪心按照区间的左端点排序然后依次遍历每次选择能覆盖当前起点且右端点最远的区间直到覆盖完成。#include bits/stdc.h using namespace std; struct Interval { int l, r; bool operator(const Interval other) const { return l other.l; } }; int main() { int n, targetL, targetR; cin n targetL targetR; vectorInterval intervals(n); for (int i 0; i n; i) { cin intervals[i].l intervals[i].r; } sort(intervals.begin(), intervals.end()); int cur targetL, idx 0, ans 0; while (cur targetR idx n) { int farthest cur - 1; // 关键记录当前能延伸到的最远位置 while (idx n intervals[idx].l cur) { farthest max(farthest, intervals[idx].r); idx; } if (farthest cur) { cout -1 endl; return 0; } ans; cur farthest 1; } if (cur targetR) { cout -1 endl; } else { cout ans endl; } return 0; }这里有一个很关键的易错点如果你没有把“当前覆盖到的位置”和“区间端点”的边界关系搞清楚就很容易出现死循环或者少选区间的问题。比如当前覆盖到了位置3新区间只要左端点是3或者更小它就仍然是有用的这个“闭区间”和“开区间”的差异细节上要认真处理。B题的教训是什么我觉得是基础算法模板的熟练度。区间覆盖这种经典贪心不应该在赛场上临时推导而是当你看到题目描述时马上就能反应过来“这是区间覆盖问题”、“用贪心可解”、“排序的key是什么”。这种肌肉记忆需要靠日常刷题来建立别无他法。3.3 C题区间问题与哈希表的化学反应C题是我这次比较有收获的一道题。先说题目大意给定一个长度为n的数组问有多少个连续子区间满足“区间内所有元素的和恰好等于区间长度乘以某个给定的整数k”。表面上看这需要枚举所有子区间复杂度是O(n^2)n如果到10^5就彻底没戏。但如果你按照我前面说的“先推公式再看题目”的习惯来思考突破口很快就出来了。设子区间是[i, j]区间和是sum(i, j)区间长度是j - i 1。那么题目的条件就是sum(i, j) k * (j - i 1)这个式子看起来挺唬人的但如果我引入前缀和数组pre[i]表示前i个元素的和那么sum(i, j) pre[j] - pre[i-1]代入上面的式子pre[j] - pre[i-1] k * (j - i 1)整理一下pre[j] - k * j pre[i-1] - k * (i-1)这个等式有一个非常漂亮的含义如果我们定义一个新数组b[i] pre[i] - k * i那么题目要求的子区间[i, j]恰好就对应着“b[j] b[i-1]”这一对下标。也就是说我们只需要统计有多少对相同值的b数组元素即可。这样一来整个问题就被化简成了遍历一遍数组用哈希表统计b[i]出现的次数每遇到一个重复值就累加一次已经出现的次数。#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorlong long a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorlong long pre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i - 1] a[i]; } unordered_maplong long, long long cnt; cnt[0] 1; // 注意b[0] pre[0] - k*0 0需要初始化 long long ans 0; for (int i 1; i n; i) { long long b pre[i] - 1LL * k * i; ans cnt[b]; cnt[b]; } cout ans endl; return 0; }这里有一个极具迷惑性的细节必须提醒你注意初始时b[0] pre[0] - k * 0 0这个值必须提前放进哈希表。因为子区间可以从数组的第一个元素开始那么对应的i-1就是0如果忘记初始化cnt[0] 1所有前缀区间都会被漏掉。这种细节是典型的“坑”平时写代码时未必会注意但比赛时一漏就是全场WA。另外这个转化技巧本身非常值得记忆。它本质上是一个“代数恒等变形”的思路——把看起来涉及区间长度和区间和的复杂条件通过引入一个辅助数组变成“找相等元素”的简单问题。类似的套路在牛客周赛里反复出现在LeetCode里也很常见比如“和为k的子数组”就是同一个思路的另一种形式。3.4 D题完美数问题的完整推导终于到了压轴题。这一题就是热搜里讨论最多的“最大的不大于n的完美数”。我先还原一下题目的要求给定一个正整数n求一个最大的不超过n的数x使得x满足“完美数”的定义。在这题里一个数被视为完美数的条件是它可以表示成某个正整数m的平方加上m本身也就是x m^2 m。这个定义一出来思路其实就清晰了。x m^2 m m * (m 1)也就是说x必须是两个连续整数的乘积。这种数在数学上有个名字叫“普洛尼克数”pronic number。那么问题就变成了给定n找一个最大的m使得m * (m 1) n。这个不等式是一个一元二次不等式直接解就能得到m的近似值m ≈ (-1 sqrt(1 4n)) / 2因为m必须是整数所以我们需要取不大于这个值的最大整数。但这里有个陷阱直接浮点开根再取整有精度风险。当n特别大的时候sqrt的计算误差可能会让你得到错误的m。更稳妥的方式是用整数二分来求满足条件的最大m。#include bits/stdc.h using namespace std; int main() { long long n; cin n; long long lo 0, hi 2e9; // 足够大的上界 while (lo hi) { long long mid (lo hi 1) / 2; if (mid * (mid 1) n) { lo mid; } else { hi mid - 1; } } cout lo * (lo 1) endl; return 0; }这个解法的时间复杂度是O(log n)二进制下最多迭代31次左右非常快。核心代码不到十行但背后需要你能看穿“完美数”就是“普洛尼克数”然后把问题转化为解不等式。这里我想多聊几句浮点精度的教训。我第一次做这道题的时候偷懒直接用了sqrt结果在本地测试几个小数据全对一提交WA了。后来排查半天才发现当n接近某个m*(m1)但稍微小一点点的时候sqrt(14n)开出来可能是m*21左右但浮点误差导致结果差了几个单位。这种问题在竞赛里出现频率很高尤其是涉及大数开根的时候。给大家一个建议凡是要“找最大满足某个性质的整数”优先想二分不要想着用数学公式一步到位。二分的鲁棒性远强于浮点估算。另外这个题的n范围给到了10^18级别所以必须用long long。如果你习惯用int这里会直接溢出连样例都过不了。比赛时先看数据范围再选变量类型这个习惯真得刻进DNA里。4. 常见问题与排查技巧实录4.1 为什么样例过了还是WA这是周赛里最让人崩溃的体验之一明明样例输出和期望一模一样提交上去就是WA。我总结下来出现这种情况的原因无非以下几类边界情况没有覆盖。比如空数组、n1、数据全是相同元素等特殊情况。很多题目给出的样例都偏“正常”不会刻意给极端边界。我见过不少人C题忘记初始化cnt[0]1样例能过但遇到从第一个元素开始的子区间就挂掉了。变量类型用错。题目数据范围写着“整数”但实际上是long long的范围。这种情况在牛客周赛里太常见了涉及求和或者乘法int必爆。输出格式不对。比如多输出了一个空格或者少了换行。有时候检查代码逻辑花了一小时最后发现是格式问题真的能把人气笑。算法复杂度超了但没用。本地小数据跑不出区别一上大数据就TLE。每个比赛日的讨论区都有大量人挂出“过样例但WA”的代码求助。我看过不少绝大部分都是上面几个原因。所以提交前一定要有一个习惯自己构造边界数据来测试。这个习惯比任何调试技巧都有用。4.2 时间超限后的优化路径如果你遇到了TLE别慌按照下面的顺序来排查第一步看输入输出。C选手确认有没有关闭流同步ios::sync_with_stdio(false)Python选手确认是不是用了sys.stdin.read()而不是慢速的input()。这个问题能解决三成的TLE。第二步看算法复杂度。如果你写了O(n^2)的算法而n已经到10^5那再怎么优化常数也没有用必须从思路上更换算法。比如C题从O(n^2)暴力的思路优化到O(n)哈希表的思路这才是根本解法。第三步看常数因子。如果你的算法复杂度本身没问题但使用了高层的容器或者递归调用可能会导致常数过大。比如C里map和unordered_map的选择在数据量大的时候性能差异很明显。map是红黑树每次操作O(log n)且常数大unordered_map虽然理论O(1)但哈希冲突严重时也可能退化。牛客的数据通常不会为unordered_map专门构造卡哈希的数据所以优先用unordered_map是合理的。我在D题里就选择了二分而不是浮点开根这在复杂度上没有本质区别但规避了浮点误差导致的隐蔽错误。这种“用整数运算代替浮点运算”的思路在处理大数问题时值得养成条件反射。4.3 心态管理遇到不会的题怎么办最后说一个很多人忽略的问题比赛时的情绪管理。牛客周赛一个半小时四道题前面两道题一般十五分钟能解决从C题开始就可能卡壳。我见过很多人卡在C题半小时后心态崩了后面代码越写越乱连D题的暴力分都没拿到。这非常可惜。我的策略是“三十分钟法则”一道题如果三十分钟完全没有思路果断跳过先把后面题目的暴力分拿到手再回过来慢慢想。这套打法让我打周赛的成绩比一味死磕稳定得多。有时候你回过头来看之前卡住的题脑子里那根筋突然就通了或者暴力写的部分都已经能稳住其他题的分数心里压力小了反而更容易想出正解。另外赛后复盘比赛时死磕更值钱。每期周赛结束后牛客的讨论区和题解区都会有大佬发布解题报告不只是贴AC代码还会讲思路推导过程。认认真真地看完每一道题的题解思考自己和正解的差距在哪里下次比赛遇到同类题目能不能做出来——这才是周赛真正的价值。4.4 常见问题速查表为了方便你自查我把这期比赛中容易踩的坑整理成了一个表格建议收藏起来下次周赛前扫一眼症状可能原因解决方案样例过但WA边界条件未覆盖构造极端数据自测全WA变量类型int溢出涉及乘法、求和用long longTLE输入输出太慢加ios::sync_with_stdio(false)TLE算法复杂度高换O(n)数学优化或哈希输出格式错误多空格少换行仔细比对题目输出要求D题WA浮点精度误差用整数二分替代浮点开根C题漏解前缀哈希初始值未赋cnt[0]15. 赛后私货分享我总结的刷题与比赛方法论5.1 周赛驱动学习法很多人刷题是“今天有时间就刷几道”非常随意效率极低。我强烈推荐用周赛来驱动每周的学习计划每周三或者周四打牛客周赛把对错记录下来周末花两个小时的整块时间复盘。复盘时不是只看题解而是把每道题的思路写下来特别是“我当时卡在哪一步”——这个记录比题目本身更有价值。坚持一段时间后你会发现自己对题目的敏感度明显提升。什么题用什么套路看一眼就知道了。这种能力不是天生的就是靠一场一场比赛喂出来的。5.2 如何高效使用牛客的讨论区牛客周赛的讨论区是个宝库但要会看。我的经验是不要直接去看标着“题解”的置顶帖而是先去翻那些交了三四次WA的人的帖子。这些帖子往往暴露了题目最隐蔽的陷阱比标答更有教学意义。看别人怎么错提醒自己别踩同样的坑性价比极高。等你看完了WA案例再去看标答这时候你才能理解标答每一步的精妙之处。如果直接看标答很容易产生“这么简单我怎么没想到”的错觉但下次还是不会做。5.3 从周赛到多校赛的进阶路径打完牛客周赛如果你想继续进阶可以关注牛客多校训练营。热搜里提到的牛客多校2026就是更高强度、更贴近区域赛难度的训练系列。周赛和多校赛的关系有点类似“日常练习赛”和“模拟实战”的关系。周赛适合检验基础、保持手感多校赛则更强调团队配合和复杂知识点的综合应用。我个人建议的路径是先用牛客周赛稳固C题级别的能力当你连续两三期周赛都能稳定AC前三题时就可以去尝试多校赛的题目了。多校赛的D题往往比周赛的D题要难上一个量级一开始做不出来很正常把它当成学习材料来对待就好。另外提一句如果你同时在打LeetCode周赛可以把两边做对比。LeetCode的题解区有英文社区的解法也能帮你拓宽思路。两边同步打知识面会更全面分析问题的角度也会更多元。
![[AutoSar]在Davinci Configurator中导入Dbc Cdd 文件](http://pic.xiahunao.cn/yaotu/[AutoSar]在Davinci Configurator中导入Dbc Cdd 文件)
