1. 读懂题目数位平方和的“拆分陷阱”1.1 题目到底在问什么第168场双周赛的Q2题号3723核心就五个字“数位平方和”。初看这个词很容易往数位DP方向想毕竟“数位”两个字在竞赛里几乎就是按位动态规划的代名词。实际上这道题考的根本不是DP而是拆数直觉。题目模型可以这样理解给你一个正整数n你可以把它拆成若干个正整数之和对于拆出来的每一个数计算它十进制表示下每位数字的平方和最后把所有拆出数的平方和累加问这个总和最大能到多少。举个例子n10时如果不拆10的数位平方和是1^20^21。如果拆成9和1那么9的贡献是9^2811的贡献是1总贡献变成82。同样一个10不拆和拆开差别是81倍。也就是说这道题所有的难度都藏在“拆”这个动作里。读题的时候很多人会本能地觉得“拆得越细越赚”但后面你会发现82的组合只有64468远不如91的82所以拆法是有讲究的。1.2 先写一个暴力版本动态规划兜底在没有确定数学结论之前最稳的做法是先把暴力跑通。设dp[i]表示数字i被拆成若干正整数之和时能得到的最大数位平方和初始状态是dp[i]digitSquareSum(i)表示不拆。转移方程很直观dp[i] max(dp[i], dp[i-j] digitSquareSum(j))其中1 ≤ j i。这个方程的意思是先拆出一个j剩下的i-j继续按照最优方式拆。写成代码也很快双重循环就能搞定。如果n的范围很小比如n≤5000这个DP完全够用。它的时间复杂度是O(n^2)空间复杂度O(n)在实际比赛中可以作为验证工具而不是最终解法。不过一旦n到10^9甚至10^18量级DP就没戏了。所以必须找一个数学规律把问题压缩成O(1)或O(log n)的解法。这也是这类“看似数位DP、实则是贪心找规律”题目的通用解法路径先暴力验证直觉再提炼规律。1.3 核心直觉为什么拆开往往比整体更大要理解这道题先要理解一个现象一个数的数位平方和和它本身的大小并不是线性关系。9的平方和是81而10的平方和只有1。也就是说数字每进一位高位数字的“权重”反而被十进制结构稀释了。举个更明显的例子99的数位平方和是9^29^2162但99本身接近100。如果直接把99拆成9999999999911个9总和不变还是99但贡献变成11×81891。差距接近5.5倍。把这个问题类比成发奖金就好理解了数字9就像一个“满额奖金池”每次出现都固定给81分而一个数一旦带上十位、百位高位信息被压缩成一次计数效率就大幅下降。所以最优策略一定是尽可能多地制造“独立的9”让每个9单独领一份81分的满额奖励。这就是全题的题眼。2. 最优策略为什么答案是“一堆9加一个余数”2.1 个位数字的“单位收益”对比在0到9这十个数字里每个数字单独作为拆出项时贡献等于它本身的平方。列个表就更直观数字数位平方和每单位数值的收益111242393416452556366749786489819从表里能看到数字9的“单位收益”是9是所有个位数里最高的。这意味着如果总和中有一块数值必须作为一个整体存在把它做成9是最不亏的。反过来数字1的单位收益只有1所以“全拆成1”这种方案一定是最差的。但这里有个前提9这个数字自己是不能再拆的。如果硬把9拆成45贡献从81变成162541直接腰斩拆成111111111贡献更是只有9。所以一旦决定拆出9就原样保留它。2.2 余数不要合并也不要继续拆现在问题就变得非常具体了n除以9商是q余数是r那么方案就是q个9外加一个余数r。最终答案是q×81r^2。这句话写出来简单但现场容易掉进两个坑。第一个坑是“余数要不要合并到某个9上”。比如n17q1r8。按公式是98贡献8164145。如果贪心地把8并到9上变成17贡献是1^27^250直接少了95。所以余数必须单独保留。第二个坑是“余数要不要继续拆”。比如r8有人觉得8可以拆成17贡献14950但8单独保留是64拆了反而更低。其实这个规律在1到9所有数字上都成立一个数字a如果保留贡献是a^2如果拆成两个正整数uva最大贡献也不会超过u^2v^2而u^2v^2在uv固定时只有把数值集中到一端才最大。当a1时拆与不拆都是1当a2时拆成11贡献2小于4而当a8时拆成17贡献50小于64。所以任何余数都不要继续拆。2.3 小范围对拍验证公式与DP完全一致数学上想得再漂亮代码写错也是白搭。我在比赛里习惯的做法是先用第1节里的DP作为暴力对拍器再用公式直接算两边跑相同输入逐项对比。这里列出一小段n从1到30的对比结果n最优拆法示例DP结果公式结果11115525259981811091828217981451451899162162199911631632099216616627999243243289991244244从表格能看到公式结果和DP结果完全一致。这基本可以确定当n是正整数且允许拆分为正整数之和时“q个9加一个余数r”就是最优结构。现场如果还有疑虑可以再随机生成几万个n用assert确认两个结果相等这一步比任何理论证明都让人安心。3. 代码实现一行公式与完整兜底方案3.1 数学公式版Python一行流一旦规律确定了代码就变得极其简单。Python版本几乎可以写成一行def maxDigitSquareSum(n: int) - int: return (n // 9) * 81 (n % 9) ** 2这里n//9是9的个数n%9是余数。如果n能被9整除余数是0那么公式自动退化为(n//9)×81没有任何特殊处理。这也是这个公式比if-else分支更优雅的地方。如果你担心“余数是0”的时候多写了一个0^2完全没必要式子本身就处理了这个情况。提交前可以跑几个用例n1返回1n9返回81n10返回82n17返回145n18返回162n19返回163。这几个用例覆盖了整除、不整除、小数、整十整百等情况。3.2 C实现与溢出处理C版本需要多留一个心眼乘法溢出。虽然n的范围题目没有给死但双周赛里Q2的数据范围经常到10^9甚至10^18。n为10^18时n//9大约是1.11×10^17再乘81结果是9×10^17左右。这个值还没超过long long的上限9.22×10^18但如果不小心写成int直接爆掉。using int64 long long; long long maxDigitSquareSum(long long n) { long long q n / 9; long long r n % 9; return q * 81 r * r; }如果题目给出的n更大比如达到10^18量级而且要输出一个可能接近9×10^18的答案建议用__int128做中间运算避免q×81这一步在边界处溢出__int128 ans (__int128)q * 81 r * r; // 最后再转成字符串输出我的实际经验是竞赛环境里只要n≥10^16就直接把中间类型提到64位以上不要拘泥于“题目说答案在long long范围内”。很多WA错误答案不是思路问题而是溢出问题尤其是这种“乘法平移”结构。3.3 大数场景下的处理还有一类变体题输入是一个很长的十进制字符串而不是整数。比如n有1000位这种情况下连long long都装不下输入值更别提直接做除法。遇到这种输入只需要模拟竖式除法求n//9和n%9即可不需要把整个字符串转成整数。模拟方法很简单维护一个余数rem从字符串最高位开始逐位处理rem (rem * 10 (s[i] - 0)) % 9走完后rem就是n%9。商是几位数可以先不管因为最终答案 81×(n//9) r^2而n//9就是(n - r)/9可以直接用大数减法实现或者用模拟除法把商的每一位算出来。如果只是输出结果可以这样算n减去余数r得到一个末位为9整除关系的数然后除以9整体乘81最后再加上r^2。在纯字符串实现里这些都变成了大数乘除但代码量也不会很长。核心思路仍然是“9的个数×81 加 余数平方”只是底层计算从整数运算变成了大数运算。Python自带大整数完全不用操心这类问题Java可以用BigIntegerC则需要手写或依赖大数板子。对于一场40分钟的模拟赛我建议优先用Python提交这种题省去大量大数实现时间。3.4 复杂度分析整个公式解法的时间复杂度是O(1)输入如果是普通整数读入和计算都是常数级。空间复杂度O(1)。如果用DP暴力做时间复杂度是O(n^2)空间复杂度O(n)。两者差距在n10^9这种量级是天文数字这也是为什么必须找出数学规律。对拍脚本的复杂度不需要太优化n比较小时跑DP完全够用。我习惯把对拍范围设在1到5000这样既保证了样本量又不会因为O(n^2)的DP卡太久。实际跑下来也就是一瞬间的事。4. 现场排坑实战中容易出问题的几个点4.1 边界条件N1、N9、r0边界是最容易翻车的地方。n1时公式结果是1正确n9时公式结果是81正确n18时结果是162正确。这些用例提交之前一定要手动过一遍尤其是n18这个整除用例它能验证你没有把“余数为0”错误地当成“不用拆”。我见过不少人在推导时忘了r0的情况写成if (r 0) return q * 81else return q * 81 r * r。这样写本身没有错但多一个分支就多一个出错点。直接用公式q81rr逻辑更统一也不容易漏掉分支。4.2 拆分的“允许范围”别搞错很多WA不是算法错而是把拆分规则理解错了。这题要求拆成若干正整数意味着每个加数都至少是1不能出现0更不能出现负数。所以像“17拆成18-1”这种操作在数学上不合法虽然在数值上等于17但“-1”不是一个正整数。还有一点拆分顺序不重要。98和89被视为同一种方案但因为我们在计算总和顺序并不会影响答案。这也是能把问题直接归纳到“有多少个9”的原因之一。如果题目要求输出具体方案那还要多做一步构造但Q2通常只问最大值。4.3 对拍脚本不放心贪心时的自检方式如果你在赛场上推导了半天还是不太确定“全是9加一个余数”是否正确我强烈建议写一个对拍脚本。不用很复杂核心就三部分def digit_square_sum(x: int) - int: return sum(int(c) ** 2 for c in str(x)) def brute(n: int) - int: dp [digit_square_sum(i) for i in range(n 1)] for i in range(1, n 1): for j in range(1, i): dp[i] max(dp[i], dp[i - j] digit_square_sum(j)) return dp[n] def formula(n: int) - int: return (n // 9) * 81 (n % 9) ** 2 for n in range(1, 2000): assert brute(n) formula(n), fmismatch at {n} print(all ok)这段脚本能在几秒内告诉你公式是否正确。我在双周赛里遇到类似“看起来是贪心”的题都会先用小规模暴力校验再提交主解法。这个习惯帮我避免了很多次“直觉错误”导致的返工。4.4 双周赛Q2的实战节奏双周赛的Q2通常定位是“中等偏简单”但它的区分度在于你能不能快速识别本质。看到“数位平方和”这类词第一反应可能是数位DP但不要急着套模板。先花30秒做个最简单的样例分析比如n10、n19去感受拆分的收益规律。通常两个样例就能看出端倪。我个人的实战流程是这样的先读题确认n的数据范围和输出类型然后手算几个特殊值建立直观感受再暴力或DP写一个不超时的验证版最后提炼公式提交公式版。整个过程控制在10到15分钟比较合理剩余时间留给Q3和Q4。另外如果这场双周赛是模拟赛或练习赛赛后一定要用对拍脚本把整场测试点跑一遍。很多选手比赛时过了样例就提交结果在隐藏边界上翻车。养成对拍习惯之后这类低级失误会大幅减少。