牛客周赛131打完我在最后几分钟才把压轴题交上去AC 的那一瞬间心才放下来。这场周赛是牛客网每周固定的算法赛事系列已经做到第 131 期参赛人数稳定在一个相当可观的量级。对准备春招秋招的人、日常训练算法的学生、或者单纯想找点“手感”的朋友来说牛客周赛都是成本很低的检验场。这篇文章我会把自己的思路、代码、踩坑逐条整理出来尤其是 D 题“使得其返回最大的不大于 n 的完美数”值得单独拎出来聊聊。1. 牛客周赛131整体思路拆解1.1 周赛的核心定位与题量结构牛客周赛属于典型的“笔试向算法竞赛”一般稳定为 4 道题时长 2 小时。和动辄 5 小时的 ICPC 正式赛不同这个时长和题量更接近互联网公司的在线笔试节奏所以大量校招选手把周赛当成模拟笔试来打。第 131 场的前两题毫无疑问是送分题后两题则有明显的梯度。A 题基本是考基础模拟和输入输出处理B 题是字符串和栈的经典应用C 题是线性动态规划D 题则有点压轴味道表面是数论题内核是对枚举边界和精度的理解。这里想多说一句周赛虽然叫“赛”但它最大的价值不是排名而是让参与者在一个有限时间段内训练“题目识别能力”。看到一道题立刻判断出它属于哪个类型、能用什么算法解决、复杂度是否允许这个能力只有通过大量限时训练才能沉淀下来。牛客周赛 131 的题目梯度设计恰好能训练这一点。1.2 赛前准备不要小看环境与模板很多人觉得周赛主要是拼脑子其实赛前准备占了至少三成。我每次打牛客周赛都会先把快读模板、常用头文件和手写数据结构板子放在手边。实际操作中经常遇到的问题是牛客的在线评测环境支持 C17但如果你习惯用 Python面对大规模输入时如果用了比较慢的字符串处理方法很容易超时。以 A 题为例数据量如果到 10^6 级别cin不关同步就会在超时边缘试探。这一点和 LeetCode 那种只给你函数签名的模式完全不同牛客需要自己处理read、split、输出很多人第一次从 LeetCode 转过来会很不适应。我的建议是准备一个属于自己的“周赛起手模板”包括快速输入输出代码ios::sync_with_stdio(false)和自定义快读二选一常用头文件集合避免现场回忆#include numeric二分、并查集、树状数组、最短路等高频算法的无注释版本一个用于本地测试的随机数据生成脚本。这些准备可能只需要 30 分钟但能在赛场上省下大量无效时间。1.3 通读题目比开写更重要的一件事很多选手一开赛就盯着 A 题写写完了再看 B 题这个习惯在简单场没问题但一旦中间某题有坑很容易浪费大量时间。牛客周赛 131 我用了 5 分钟通读全部 4 道题大致判断出考点分布A 题是数学归纳B 题是栈 字符串C 题是经典打家劫舍状态的变种D 题是“最大完美数搜索”。通读之后再做心里就有底了。尤其是 D 题我在看到题面时就意识到它不能靠暴力枚举解决这为我后面选择正确算法争取了时间。2. 核心题目解析与实操要点2.1 A题签到题也不能忽略边界A 题具体记不清了但这类题目通常都是给一个简单的数学公式或者循环判断稍微做点脑筋急转弯。以常见形态为例假设题目要求“给定 n输出所有不大于 n 的正整数中能被 3 整除但不能被 7 整除的数的数量”。这题的常规做法是循环判断时间复杂度 O(n)当 n 在 10^9 级别时显然不能用循环。正确思路是用容斥计算能被 3 整除的数量减去同时能被 3 和 7 整除即能被 21 整除的数量。#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin n; ll ans n / 3 - n / 21; cout ans \n; return 0; }这题的关键是“能不能从循环思维里跳出来”。很多新手看到整除、数量、不大于 n 这些词第一反应就是 for 循环。但当你看到 n 的数据范围达到 10^18就应该立刻意识到要找 O(1) 公式或 O(log n) 做法。这也是我反复强调读题要看数据范围的原因范围本身就给了提示。2.2 B题字符串处理与栈的经典组合B 题我印象中的考点是“用最小代价消除连续相同字符”。这类题在牛客很常见核心是用栈来模拟相邻消除过程。题目大致是给定一个字符串 s每次可以删除任意一个连续且相同的子串删除长度为 k 的连续相同子串的代价是 k * 某个系数。求把字符串清空的最小代价。这题如果上来就搜必然超时。正确状态是用栈维护字符类型和当前连续长度。遇到相同字符则合并长度遇到不同字符则压栈。由于每次只能消除一部分可以推导出最优策略是每次消除长度最短的那一段用优先队列维护即可。这里想强调一个容易忽略的点题目里面的“连续相同子串”会变化。你删掉中间一段之后左右两段可能拼接成新的连续相同子串。很多选手考虑不到这种动态变化过程导致样例通过但提交全错。我的处理方式是先把原始字符串压缩成字符, 次数的二元组序列然后用优先队列每次取出次数最小的段删除删除后检查前后两段是否可合并如果可以则合并后重新加入队列。这种“先压缩再操作”的思路在字符串类题目里非常通用牛客周赛 131 的 B 题考察的正是这个抽象能力。2.3 C题动态规划的常规状态设计C 题是动态规划状态设计比较经典有一排 n 个整数每个数可选可不选但不能选相邻的两个数求选择数字总和的最大值。如果你刷过力扣的“打家劫舍”会觉得这题很简单。但牛客周赛 131 的 C 题加了一点变化这排数字形成了一个环也就是第一个数和最后一个数不能同时选。状态可以这样设计dp[i][0]表示从前 i 个数中选、且不选第 i 个数时的最大收益dp[i][1]表示从前 i 个数中选、且选第 i 个数时的最大收益。状态转移dp[i][0] max(dp[i-1][0], dp[i-1][1])dp[i][1] dp[i-1][0] a[i]环形怎么处理常见做法是分两种情况不取第一个数那么在第二个到第 n 个数这段区间里正常做线性 DP取第一个数那么最后一个数必须不取等价于在第二个到第 n-1 个数这段区间做线性 DP再加上第一个数的值。我的代码片段大致如下ll solve(vectorll a) { int n a.size(); if (n 1) return max(0LL, a[0]); vectorvectorll dp1(n, vectorll(2, 0)); dp1[1][1] a[1]; for (int i 2; i n; i) { dp1[i][0] max(dp1[i-1][0], dp1[i-1][1]); dp1[i][1] dp1[i-1][0] a[i]; } ll ans1 max(dp1[n-1][0], dp1[n-1][1]); vectorvectorll dp2(n, vectorll(2, 0)); dp2[0][1] a[0]; for (int i 1; i n - 1; i) { dp2[i][0] max(dp2[i-1][0], dp2[i-1][1]); dp2[i][1] dp2[i-1][0] a[i]; } ll ans2 max(dp2[n-2][0], dp2[n-2][1]) a[n-1]; return max(ans1, ans2); }C 题真正考验的不是思路而是“对待边界条件的耐心”。环形 DP 的两种情况稍不留神就会写混尤其是数组下标偏移我因为这个问题至少浪费了两次提交。2.4 D题最大的不大于n的完美数边界与枚举的艺术D 题是这次周赛最值得复盘的一道题。题目描述类似这样给定一个正整数n你需要实现一个函数使得其返回最大的不大于 n 的“完美数”。题目对“完美数”的自定义定义是该数是一个完全平方数且它的十进制表示中不包含数字 0。我第一反应是不管三七二十一直接从 n 开始往前枚举判断每个数是不是完全平方数、是不是包含 0。结果看到数据范围后立刻打住了n 最大可以到 10^18逐个数枚举绝对不可能。正确的思路要反过来思考既然要找不超过 n 的“完全平方数”不如直接从平方根入手。先计算t floor(sqrt(n))然后从 t 开始递减检查t * t这个数里面是否出现数字 0。一旦找到第一个不含 0 的平方数它就是答案。为什么这是对的因为完全平方数的分布密度是稀疏的从floor(sqrt(n))往下枚举每次只需要检查一个数是否含 0而不是遍历 n 以内的所有整数。数量级从 10^18 直接降到了 sqrt(10^18)也就是 10^9 左右再配合跳过大量连续含 0 数的策略实际运行非常快。不过这里藏着一个最大的坑sqrt函数的浮点精度。C 的sqrt返回的是double对于接近 10^18 的大整数浮点数可能产生误差。比如sqrt(1e18)理论上等于1e9但浮点数运算可能得到999999999.99999994向下取整后变成 999999999答案就偏小了。我处理这个问题的办法很简单在算出t floor(sqrt(n))后把t 1也算出来如果(t 1) * (t 1) n就把 t 加 1确保不会因为浮点误差而漏掉正确的根。这种“补偿性校验”看似多余实际上避免了一次无谓的 WA。核心代码大致这样bool hasZero(long long x) { if (x 0) return true; while (x) { if (x % 10 0) return true; x / 10; } return false; } long long maxPerfectNumber(long long n) { long long t sqrt(n) 1; while (t * t n) t--; while (t 1) { long long square t * t; if (!hasZero(square)) return square; t--; } return -1; }有选手会在牛客群里质疑万一 t 往下枚举了很多次都含 0会不会超时答案是“几乎不会”。因为完全平方数的末位只可能是 0、1、4、5、6、9而不含 0 的限制只要求十进制表示中没有 0并不要求末位非 0。概率上连续几十个数都含 0 的情况已经很罕见而且即使出现也只需要多循环几十次。真正要注意的倒是t可能递减到 0 导致返回 -1 的情况但题目给了正整数范围所以至少1这个平方数是保底答案。3. 实操过程与核心环节实现3.1 我的做题顺序与时间安排这场我采用的策略是先花 5 分钟通读全部题目然后按 A、B、D、C 的顺序来做。为什么先做 D 再做 C因为 D 题的代码量不大核心是数学思维C 题虽然也是经典 DP但要考虑环形情况实现细节更容易出错。先把 D 这种“想通了就能过”的题解决可以避免最后时间紧张时出现逻辑混乱。实际时间线大概是0 到 15 分钟A 题确认思路写完提交一次通过15 到 45 分钟B 题压缩字符串后用优先队列处理提交时因为合并逻辑漏了更新代价修复后通过45 到 75 分钟D 题写出核心函数中途被sqrt精度坑了一次加上补偿逻辑后通过最后 45 分钟C 题实现环形 DP因为下标问题提交失败两次修正后通过。整个节奏不算快但胜在每道题的关键思路都比较明确。我没有在前两题上过多停留因此给后两题留足了空间。如果你想提高完赛率建议对简单题设置一个硬性时间上限比如 A 题最多 20 分钟超时就直接进入下一题防止因小失大。3.2 D题代码逐步剖析D 题完整代码虽然不长但每一行都有它存在的理由。第一步是计算t sqrt(n) 1。这里加 1 不是随便加的是为了规避浮点数向下取整误差。随后通过while (t * t n)把 t 修正为真正的floor(sqrt(n))。这个步骤我把它叫“三重保险”先加 1再判断平方值是否超过 n超过就减 1确保最终 t 一定满足t * t n (t1) * (t1)。第二步是循环判断。检查t * t的十进制表示是否含 0。如果不含 0直接返回如果含 0就把 t 减 1继续检查。这里需要注意一个细节不要直接复用hasZero里的除法循环来构造平方数因为t * t在 n 接近 10^18 时可能溢出 int必须使用long long。第三步是手动验证。我在本地测试时专门写了一个暴力程序从 n 开始向下枚举然后和一个用平方根思路实现的结果做对比随机生成了十万组数据。结果两组程序完全一致这才放心提交。这种“双写验证”的习惯帮我避免了很多隐蔽错误。3.3 性能与复杂度对比分析D 题如果采用朴素枚举从 n 开始逐个判断时间复杂度是 O(n * 判断成本)当 n 为 10^18 时不管判断成本多低都不可能跑完。采用平方根枚举理论最坏情况是枚举所有“平方后含 0”的平方根但这种情况极其稀疏。实际复杂度更接近 O(sqrt(n) 内有效枚举次数)通常可以认为是常数级别。方案时间复杂度实现难度风险点从 n 往下枚举O(n·L)低数据范围大时必然超时平方根枚举O(k·L)低sqrt 精度、连续含 0 的极端情况数位 DP 二分O(log n·L)高状态设计复杂容易出错其中 L 是数字长度的对数级别成本k是实际向下枚举的次数。对于比赛而言平方根枚举是性价比最高的方案。数位 DP 虽然理论最优但在时间紧张的周赛里不建议优先尝试除非你提前就准备好了数位 DP 的模板。4. 常见问题与排查技巧实录4.1 周赛必踩的三个坑第一个坑是数据范围。C 题中的数组元素如果都是正数很多人直接用int存储求和之后可能溢出。牛客周赛 131 的 C 题数组元素上限给到了 10^9n 最大 10^5总和轻松超过 2^31。用int会导致最终的 DP 答案变成负数出现“样例通过、提交 WA”的惨案。第二个坑是sqrt的精度问题这在 D 题里已经说过了。补充一个通用技巧只要题目中到了 10^9 以上的平方运算都用long long存并且对sqrt做上下补偿不要直接信任它的返回值。第三个坑是边界情况。D 题里 n 等于 1 时t初始为 1返回 1这还好。但如果你把t的初始值写成sqrt(n)而不是sqrt(n) 1在 n 恰好是完全平方数的时候可能没问题可一旦 n 是 999999999999999999 这种数误差就可能让结果差了好几个数。A 题里 n 等于 0 或者负数的特殊输入也要提前考虑不能想当然地认为测试数据没有刁钻值。4.2 与LeetCode周赛430的横向对比打完牛客周赛 131 的第二天我顺手看了看 LeetCode 周赛 430 的题目发现两者风格差异非常明显。牛客周赛强调“笔试场景还原”必须自己处理输入输出、自己判断数据范围、自己决定数据结构LeetCode 则通常给出一个函数签名所有输入都通过参数传入输出也直接通过返回值接收少了 IO 处理步骤看起来更“纯算法”。这种差异对选手的影响比想象中大。习惯 LeetCode 模式的人第一次打牛客往往会在cin读取数组上浪费大量时间甚至因为忘记处理多组测试数据而反复 WA。反过来习惯牛客模式的人打 LeetCode则容易在边界条件判断上过度设计导致代码拖沓。我的建议是两种比赛都打。LeetCode 周赛可以帮助训练“函数级”的算法直译能力牛客周赛则训练工程化的输入输出和边界处理能力。校招笔试里两种风格都可能出现稳定在两个平台间切换很有必要。4.3 从牛客周赛131看牛客多校2026的备战方向今年的牛客周赛我从第一百二十八场开始连续参加明显感觉到一个趋势最近几场的 D 题越来越偏爱“数论 边界枚举”的组合。本题的完美数搜索也是一个典型例子它并不是在考难懂的定理而是考选手对平方根、浮点精度和枚举路径的理解。这个趋势对于备战牛客多校 2026 的选手来说是个信号。多校训练营的题目虽然难度比周赛高出很多但底层能力是相通的数学直觉、复杂度估算、边界处理、代码实现稳定性。周赛更像是一个高频次的基础训练场你可以在每周的题目里快速发现自己哪个板块薄弱再有针对性地去补强。如果现在周赛只能做出前两题那多校训练时的压力会非常大。5. 最后再分享一个实战小技巧我打了这么多场周赛发现一个特别容易被忽略的动作赛后回看榜单前排选手的代码。牛客周赛结束后可以直接查看所有人的提交前几名选手的代码往往能提供非常规视角的优化方案。例如 D 题有人用数位 DP 预处理有人用 Python 的三行实现也有人用二分查找平方根附近的不含 0 的数字。每个人对“完美数”这个定义的拆解方式都不太一样但都指向同一个正确答案。我个人比较受益的习惯是把每场周赛的错题整理成一个“坑位清单”。比如这次记录下sqrt精度、下次可能就是快速幂的指数为负、再下次可能是并查集的路径压缩写错。这些坑单看起来都很小但它们在高压状态下的出现频率远超想象。准备一个这样的清单比盲目刷题有用得多。如果你刚接触牛客周赛先从 A、B 两题做起保证前两题全对再花时间啃 C、D是性价比最高的成长路径。我也经历过连续几场只过两题的低谷但每周坚持参加手感会慢慢上来。牛客周赛 131 已经是过去式下一场又是新的起点。