牛客周赛131复盘：完美数搜索与边界枚举的算法实战

牛客周赛131打完，我在最后几分钟才把压轴题交上去，AC 的那一瞬间心才放下来。这场周赛是牛客网每周固定的算法赛事系列，已经做到第 131 期，参赛人数稳定在一个相当可观的量级。对准备春招秋招的人、日常训练算法的学生、或者单纯想找点“手感”的朋友来说，牛客周赛都是成本很低的检验场。这篇文章我会把自己的思路、代码、踩坑逐条整理出来，尤其是 D 题“使得其返回最大的不大于 n 的完美数”，值得单独拎出来聊聊。

1. 牛客周赛131整体思路拆解

1.1 周赛的核心定位与题量结构

牛客周赛属于典型的“笔试向算法竞赛”，一般稳定为 4 道题，时长 2 小时。和动辄 5 小时的 ICPC 正式赛不同，这个时长和题量更接近互联网公司的在线笔试节奏，所以大量校招选手把周赛当成模拟笔试来打。

第 131 场的前两题毫无疑问是送分题，后两题则有明显的梯度。A 题基本是考基础模拟和输入输出处理，B 题是字符串和栈的经典应用，C 题是线性动态规划，D 题则有点压轴味道，表面是数论题，内核是对枚举边界和精度的理解。

这里想多说一句：周赛虽然叫“赛”，但它最大的价值不是排名，而是让参与者在一个有限时间段内训练“题目识别能力”。看到一道题，立刻判断出它属于哪个类型、能用什么算法解决、复杂度是否允许，这个能力只有通过大量限时训练才能沉淀下来。牛客周赛 131 的题目梯度设计恰好能训练这一点。

1.2 赛前准备：不要小看环境与模板

很多人觉得周赛主要是拼脑子，其实赛前准备占了至少三成。我每次打牛客周赛，都会先把快读模板、常用头文件和手写数据结构板子放在手边。

实际操作中经常遇到的问题是：牛客的在线评测环境支持 C++17，但如果你习惯用 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(vector<ll>& a) { int n = a.size(); if (n == 1) return max(0LL, a[0]); vector<vector<ll>> dp1(n, vector<ll>(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]); vector<vector<ll>> dp2(n, vector<ll>(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 < (t+1) * (t+1)。

第二步是循环判断。检查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) 内有效枚举次数)，通常可以认为是常数级别。

其中 L 是数字长度的对数级别成本，k是实际向下枚举的次数。对于比赛而言，平方根枚举是性价比最高的方案。数位 DP 虽然理论最优，但在时间紧张的周赛里不建议优先尝试，除非你提前就准备好了数位 DP 的模板。

4. 常见问题与排查技巧实录

4.1 周赛必踩的三个坑

第一个坑是数据范围。C 题中的数组元素如果都是正数，很多人直接用int存储，求和之后可能溢出。牛客周赛 131 的 C 题数组元素上限给到了 10^9，n 最大 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 已经是过去式，下一场又是新的起点。