春节假期刚过，我在2月13日晚上准时打开了牛客的2026寒假训练营页面。原以为假期结束大家手都生了，签到题会写得比较轻松，结果第一道题就让我意识到自己还是太天真。整场下来最值得写的是那道“使得其返回最大的不大于n的完美数”的题——题目描述只有一句话，却把数学、预处理、二分和溢出边界全部串在一起。这篇博文不打算歌功颂德，就把我这场从开题到复盘的全过程、踩过的坑、最后清理干净的代码，一次说清楚。
1. 2月13日这一场牛客寒假训练营的整体画像
1.1 赛制、题量和时间分配
牛客寒假训练营和暑假的多校联赛定位不太一样。多校更偏向组队、拼手速和配合，寒假营更像个人向的算法基础集训，每场大概5到7道题，难度从签到到防AK呈阶梯状分布。2月13日这场我印象很清楚，晚上7点开始，时长3小时，题目总量是6道，前两道基本是给新手热身的，中间两道需要一点经典算法功底，最后一道则是需要沉下心推结论的压轴题。
我那天的时间分配大致是这样的：前20分钟写掉签到题，中间40分钟卡在第二道题上，之后用一个半小时处理“完美数”这道核心题，最后留了时间做压轴题的部分分数。这里想提醒第一次参加寒假营的朋友，训练营不是正式比赛，允许你反复提交、看错误样例，所以“先拿稳能拿的分，再啃硬骨头”是更划算的策略。很多选手喜欢从最后一题开写，结果签到题没时间做，最后排名很难看。
1.2 题目难度分布和我的开题顺序
我个人的习惯是先把6道题全部读一遍，花3分钟建立一个初步印象，再按通过人数倒序开题。那种通过人数特别多的题，往往就是签到题，先拿下来能稳定心态；通过人数很少的题，如果不是一眼有思路，我会先放着，等前面分数拿够了再回头想。
这场6道题的粗略分布大概是：字符串签到、差分数组/区间覆盖、树上子树统计、数学推导题（就是那道完美数）、一道思维构造题。难度上，第一题几乎没有门槛，第二题开始需要知道前缀和或者差分的用法，第三题和第四题属于中间分水岭，能把这两道做出来的基本都能拿到中上排名，最后一道思维题则是对临场推理能力的考验。我在比赛里实际开题顺序是：签到题、树上子树统计、完美数、差分题，最后返回去啃思维题。这个顺序不一定是标准答案，但至少保证我每拿一道分，排名都在往前动。
2. 复盘那天我实际写掉的几道题
2.1 签到题：字符串包含判断
签到题的具体描述很直白：给一个字符串，判断它是否包含连续子串“2026”。字符串长度上限不大，直接调用find函数或者手写一个KMP都可以。我选择的是直接if (s.find("2026") != string::npos)，一行搞定。
这种题看起来没什么营养，但有个细节值得说：很多人写字符串包含判断时，会下意识枚举起点然后循环比对，这是没问题的，但要注意字符串长度可能到10万，此时substr截取子串再判等会造成额外内存拷贝，容易把签到题写成超时题。正确做法是只比较字符，不要真的截出一个新串。赛事社区里经常看到新人在这种简单题上TLE，基本都是这个原因。
2.2 树上子树统计：DFS一次搞定
有一道题是给一棵n个节点的树，每个节点有权值，要求统计每棵子树中某种属性的节点个数。这类题的标准解法是DFS后序遍历：从根开始递归，先处理所有子节点，再把子节点的信息累加到当前节点，复杂度O(n)。
我第一次提交用了递归DFS，结果在一条链的数据上爆了栈。这里要提醒一句：如果题目没保证树深，递归深度可能达到n，默认栈会溢出。牛客的评测机通常不会给你无限栈空间，所以遇到树形结构先想一下会不会是链。我后来改成显式栈迭代或者直接开一个数组模拟，问题就消失了。这种“递归爆栈”问题几乎每场都会有人踩，处理方式是：能迭代就迭代，不能迭代就加上稳健的递归边界判断。
2.3 差分/区间覆盖题：不要一上来就写线段树
还有一道是区间覆盖问题：给定m个区间，每个区间给一段位置加上一个值，最后查询某个位置的值。看到“区间加”三个字，很多人的第一反应是线段树，但是数据范围如果只有1e5级别，差分数组就够了，代码量少很多，也没有线段树那种调试成本。
差分数组的思路是维护一个数组diff，区间[l, r]加v时，让diff[l] += v、diff[r+1] -= v，最后对整个数组做一遍前缀和，就能还原出每个位置的实际值。这个技巧我强调过很多次，算法竞赛里“会很多高级数据结构”和“能在10分钟内写出最合适的解法”是两码事。那场我最初也想直接上懒标记线段树，后来看了一眼数据范围果断用差分，前后不到5分钟就过了。
3. “最大的不大于n的完美数”：从暴力到数学定理的完整推导
3.1 先澄清概念：这里的完美数到底是什么
题目要求“返回最大的不大于n的完美数”，如果不先澄清定义，很容易跑偏。在中文算法讨论里，“完美数”这个词有歧义：一部分人说的是完全平方数，另一部分人说的是数论里的“完全数”（Perfect Number），也就是等于它真因子之和的正整数。
从题目的英文表述和牛客近年的命题风格来看，这道题指的一定是“完全数”。例如6的真因子是1、2、3，加起来等于6，所以6是完美数；28的真因子是1、2、4、7、14，加起来也是28。前几个完美数是6、28、496、8128、33550336。如果理解成完全平方数，答案就完全不一样了。所以第一步一定是根据题目给出的样例或者英文关键词确认定义，在数学题里定义错了，后面所有推导都白费。
3.2 暴力验证为什么连样例都撑不住
拿到题我当然先想暴力：从n往前枚举每一个数，判断它是不是完美数。判断一个数m是不是完美数，需要枚举它的所有真因子，复杂度是O(sqrt m)。如果n最大只有1e4，这个做法完全可行，但赛题通常会把n给到1e18，这时从n往前枚举第一个数就可能要执行1e9次开方级别的因子遍历，妥妥的超时。
于是有人会想：那我从1到n枚举，把完美数存起来，最后输出不大于n的最大值。这个思路方向是对的，但复杂度依旧是O(n sqrt n)，是一种自欺欺人的“预处理”。真正的问题在于：完美数是极度稀疏的，目前已知的完美数在一亿亿级别以下只有寥寥几个，我们要做的不是把所有数字都筛一遍，而是直接生成可能的完美数候选。
3.3 欧几里得-欧拉定理与梅森素数
这里需要请出一个数论定理：偶完全数的充分必要条件是它可以写成2^(p-1) * (2^p - 1)，其中2^p - 1必须是一个素数。这个形式的素数又叫梅森素数。
注意一下，这个定理说的是偶完全数，而奇完全数是否存在至今还是数学界的未解问题。不过在算法竞赛里，题目给出的n范围通常到1e18，在这个范围内目前已知的所有完美数都是偶数，所以直接使用这个公式是完全安全的。考试不是写论文，不需要纠结奇完全数，只需要知道：生成完美数，本质上是找到合适的p，使得2^p - 1是素数。
那p的范围怎么定？当p=31时，2^31 - 1 = 2147483647，对应的完美数是2^30 * 2147483647，约等于2.3058e18，这个数已经超过了题目常见的1e18上限。所以如果n上限是1e18，我们只需要考虑p不超过31的情况；如果n上限放大到9e18，p=31对应的那个数也可以放进答案集合。我习惯直接枚举p从2到31，再用一个素数判断函数过滤一遍，既不需要记住梅森素数表，也能保证答案正确。
3.4 预处理 + 二分查找的最终代码
我最后提交的版本长这样，用的是C++：
#include <bits/stdc++.h> using namespace std; using int64 = long long; bool isPrime(int64 x) { if (x < 2) return false; for (int64 i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; } void generatePerfectNumbers(vector<int64>& v, int64 limit) { v.clear(); // 偶完全数公式：2^(p-1) * (2^p - 1)，其中 2^p - 1 为梅森素数 for (int p = 2; p <= 31; p++) { int64 mersenne = (1LL << p) - 1; if (!isPrime(mersenne)) continue; int64 val = (1LL << (p - 1)) * mersenne; if (val <= limit) v.push_back(val); } } int main() { vector<int64> perfect; generatePerfectNumbers(perfect, 1000000000000000000LL); int T; cin >> T; while (T--) { int64 n; cin >> n; auto it = upper_bound(perfect.begin(), perfect.end(), n); if (it == perfect.begin()) { cout << -1 << '\n'; // 不存在不大于n的完美数 } else { --it; cout << *it << '\n'; } } return 0; }几个细节我展开说一下。
第一，isPrime里面用i * i <= x，x最大约2^31 - 1 = 2147483647，i最多枚举到46340，这个量级在预处理阶段完全可接受。所以“不背梅森素数表”是完全可行的。
第二，乘法之前先判断val <= limit，避免把超出范围的大数塞进结果集合。limit这里设1e18，而p=31生成的数约2.3058e18，会被过滤掉，所以最终的集合里实际只有6、28、496、8128、33550336、8589869056、137438691328这7个数。如果某些测试点给了更大的n，也可以把limit调成LLONG_MAX，但要注意乘法是否溢出。
第三，查找阶段用upper_bound再往前移一格，而不是lower_bound。如果n刚好等于某个完美数，lower_bound会直接返回指向这个数的迭代器，再做--it反而拿到前一个更小的数。upper_bound返回第一个大于n的位置，减一得到的是“最后一个不大于n的位置”，正好是我们要的答案。这个边界问题非常隐蔽，我见过很多人在这个地方WA。
4. 现场WA了两次：溢出与边界条件的排查全记录
4.1 第一次WA：位运算优先级搞出来的数字错误
我第一次提交测样例，小数据全对，但一旦n比较大，输出就变成一堆莫名其妙的巨大整数。我第一反应是答案集合生成错了，于是把预处理后的vector打印出来，发现里面混进了几个特别离谱的数。
排查到最后，问题出在移位运算的优先级上。我最初写的代码是：
int64 val = 1LL << (p - 1) * mersenne;这里*的优先级比<<高，所以实际计算的是1LL << ((p - 1) * mersenne)，直接把一个接近1e9的数当成了移动位数，结果自然爆炸。正确的写法是：
int64 val = (1LL << (p - 1)) * mersenne;这种错误本质上不是算法问题，而是语言细节问题。C++的运算符优先级表里，移位运算符的优先级低于加减乘除，这是很多人写位运算时最容易踩的坑。建议在有歧义的地方一律加括号，不要赌编译器会按你的直觉理解。
4.2 第二次WA：long long乘法溢出
把位运算修好之后，我又遇到一次WA，这次是本地生成答案列表时，p=31之前的值全部正常，但我一开始很贪心，想把p一直枚举到63，想看看能不能覆盖更大的n。结果发现p=61的时候，(1LL << 61)本身还能装进long long，但再乘以(1LL << 60)之后数字直接溢出成了负数。
这就是一个典型的乘法溢出问题。long long能表示的最大值约9.22e18，而2^60 * (2^61 - 1)远大于这个范围。竞赛标准做法是：先算出梅森素数2^p - 1，再算完整数值之前先判断它是否超过limit，如果超过就直接跳过。我在最终代码里用limit做了这道保险，p最多枚举到31，完全不越界。
如果题目确实需要处理更大的n，可以使用__int128来临时存放乘法结果，最后再判断能不能安全转成long long。我在本地测试时试过用__int128，确实能避免溢出，但日常题面很少给出超过1e18的n，所以这里不把它作为主方案。
4.3 边界条件：n小于6和n恰好等于某个完美数
WA问题清完之后，还有两个边界情况让我不敢直接交。
第一个是n小于6的情况。6是最小的完美数，如果n=1，答案应该是不存在。我在代码里用it == perfect.begin()判断这种情况，输出-1。这个判断必须放在--it之前，否则就对空区间执行了减一操作，属于未定义行为。
第二个是n恰好等于中间某个完美数，比如n=28。如果使用lower_bound，会定位到28本身，再执行--it就得到6，答案是错的。我在现场第一次用lower_bound提交，就是在这个样例上挂掉，改成upper_bound之后就通过了。经验就是：涉及“不大于n的最大值”时，优先考虑upper_bound再回退。
我还顺手测了n=1e18、n=8128、n=8129、n=0这几个典型边界，确认输出分别是137438691328、8128、8128和-1，这才放心交了代码。做数学类题目，样例通过不等于全对，边界值测试一定要自己补全。
5. 这套题做完之后，我沉淀下来的几条经验
5.1 动手写代码前，先看一眼数据范围
这句话说起来像废话，但每次比赛都有很多人栽在“没看数据范围”上。完美数这道题最核心的决策点其实是：n最大是多少？如果n最大是1e4，暴力完全够用；如果n最大是1e9，你需要一个更聪明的枚举；如果n最大是1e18，你必须用数论公式生成候选。同样的题目，数据范围不同，选用的算法天差地别。
我现在的习惯是：读题之后先在草稿纸上写下数据范围里出现的最大数，然后估算暴力的时间复杂度。如果时间复杂度超过1e8量级，基本就要换思路。这个习惯帮我避免了很多无意义的代码。
5.2 数论题的小知识库值得整理
“完美数”不是第一次出现在牛客的题目里，过去几场类似的“回文数”“自幂数”“素数对”其实都沿用了同一类套路：用数学性质缩小候选集合，而不是逐个枚举。比如：
- 判断素数：试除到sqrt即可，但多次判断时可以预筛质数表。
- 完全数：用偶完全数公式，本质是找梅森素数。
- 回文数：枚举一半的数字再镜像生成另一半。
- 快乐数：用set检测循环。
把这些常见数学对象的生成方式整理成小抄，比赛时能省很多推导时间。我建议每个算法选手都维护一个自己的“数论小工具库”，平时遇到了就写进去，上场直接调用。
5.3 打表不是歪门邪道，但要打得聪明
完美数这种题还有一个经典解法：直接把已知的完美数硬编码进代码。因为不大于1e18的完美数就7个，写死进数组，查询时二分即可。很多人觉得打表丢人，我反倒觉得，在参赛场景下，只要不违反赛制，能用最少的代码拿到分就是好策略。
不过我建议平时练习还是把数学推导过程走一遍。打表能让你AC，但不会让你理解为什么答案是这些数。等到题目变成“求第k个完美数”，或者“判断一个数是不是完美数”，只靠打表就会露馅。真正的提升来自理解公式、理解边界、理解二分的细节。
5.4 复盘比刷题重要，赛后一定要重新写一遍
这场比赛结束之后，我没有急着去看别人的代码，而是先把完美数这题按“无注释版、注释版、边界测试版”写了三遍。第一遍默写完整流程，第二遍在关键位置加上注释和推导，第三遍把所有边界测试封装成一个函数，确保以后遇到类似题可以直接复用。
这个习惯是从上一个赛季开始养成的，效果很明显。很多题目当时AC了，过两周再看就像新题；但如果赛后重新推导一遍，并且沉淀出一段可复用的代码，下次遇到同类题就是送分题。2月13日这场训练营给我最大的收获不是排名，而是让我把“完美数”这个认知从名字升级成了定理、公式、代码三位一体的东西。
最后再分享一个小技巧：牛客的寒假训练营通常可以回看别人的提交记录，里面有很多高手的代码风格非常值得学习。我每次复盘时都会挑一个排名靠前、代码简洁的选手，把他的解法重新理解一遍，对比自己的代码寻找差异。这种“带着问题读别人代码”的效率，比单纯刷题高很多。希望这篇复盘对准备2026后续赛程的你有帮助，我们牛客多校赛场上见。
