做 PAT 甲级题最难受的一种体验是样例全对自己觉得思路也没问题交上去却卡在最后一个测试点。1104 这道 Sum of Number Segments 就是这样代码本身不到二十行但测试点 3 硬生生放倒了一大批人。我第一次做的时候也中招了排查了很久最后发现根本不是公式的问题而是 double 的精度在背后捣鬼。先给第一次接触这道题的朋友说一下它到底要干什么给你 N 个排好顺序的正数要你把这个序列所有的连续子段也就是所有连续的子区间分别求和再把所有子段和全部加起来输出总和保留两位小数。听着很简单但 N 最大到 100000如果真按字面意思枚举所有子段子段数量是 N(N1)/2大约是 50 亿个任何一种语言都跑不完。所以它被戏称为“智力题”——真正的考点不是你会不会写循环而是你能不能从另一个角度把这笔账算明白。这篇文章我会先带你用手算把 N4 的情况扒清楚然后推导出 O(N) 的核心公式再重点复盘测试点 3 的 double 精度坑它为什么会出现、错误是怎么累积的、为什么换成 long double 就好使了最后给出一个可以直接交上去的 C 实现以及我踩过坑之后总结出来的通用经验。1. 题目在问什么把每个连续子段的和再全部加起来1.1 输入输出先看清题目输入有两行第一行一个整数 N表示有几个数第二行是 N 个正数。输出是一个保留两位小数的浮点数表示所有连续子段元素之和的总和。这里的“段”必须是连续的比如 [第 2 个元素, 第 3 个元素]不能跳着取。需要注意 N 的量级是 100000而不是 100。很多人第一眼看到“连续子段”四个字脑子里的第一反应就是“枚举所有子段然后求和”。这个反应本身没错但它直接被 N 的量级判了死刑。想 AC 这道题必须换一个完全不枚举子段的方法。1.2 拿 N4 手算一遍找找感觉假设输入是4 0.1 0.2 0.3 0.4把所有连续子段列出来按长度分组长度为 1 的子段[0.1]、[0.2]、[0.3]、[0.4]和分别是 0.1、0.2、0.3、0.4长度为 2 的子段[0.1, 0.2]、[0.2, 0.3]、[0.3, 0.4]和分别是 0.3、0.5、0.7长度为 3 的子段[0.1, 0.2, 0.3]、[0.2, 0.3, 0.4]和分别是 0.6、0.9长度为 4 的子段[0.1, 0.2, 0.3, 0.4]和是 1.0把这些和全部加在一起(0.1 0.2 0.3 0.4) (0.3 0.5 0.7) (0.6 0.9) 1.0 1.0 1.5 1.5 1.0 5.0所以样例输出是 5.00。这一步不难但它给了我们一个重要的观察同样是求总和我完全可以不一个子段一个子段地加而是把每个数字拿出来问一句“你在多少个连续子段里出现过”然后用“数字 × 出现次数”来累加。1.3 数一数每个数字出现了几次继续用上面四个数观察0.1 出现在所有以第 1 个位置开头的子段里一共 4 次0.2 出现在 [0.2]、[0.1,0.2]、[0.2,0.3]、[0.2,0.3,0.4]、[0.1,0.2,0.3]、[0.1,0.2,0.3,0.4] 里一共 6 次0.3 同样出现 6 次0.4 出现 4 次于是总和可以写成0.1 × 4 0.2 × 6 0.3 × 6 0.4 × 4 5.0和前面枚举子段算出来的结果一模一样。现在问题就清晰了只要我能用公式直接算出“第 i 个数字在多少个连续子段中出现”这道题就从枚举所有子段的 O(N²) 变成了对每个数算一次的 O(N)。2. 智力题的核心公式第 i 个数为什么出现 i×(N-i1) 次2.1 推导过程看左端点和右端点能怎么选这里统一用 1 开始的下标也就是说数组是 a[1] 到 a[N]。对于任意一个连续子段它都可以表示为闭区间 [L, R]其中 L 是左端点的位置R 是右端点的位置。现在问a[i] 会被哪些连续子段包含答案是所有满足 L i 且 R i 的 [L, R]。先看左端点 L。L 必须落在第 1 个位置到第 i 个位置之间因为如果 L 比 i 大子段就整个跑到 a[i] 右边去了根本不包含 a[i]。所以 L 一共有 i 种选择。再看右端点 R。R 必须落在第 i 个位置到第 N 个位置之间因为如果 R 比 i 小子段就整个跑到 a[i] 左边去了。所以 R 一共有 N-i1 种选择。L 和 R 的选择是互相独立的所以同时包含 a[i] 的连续子段总数就是i × (N - i 1)用这个式子回到 N4 验证一下i11 × 4 4和手算一致i22 × 3 6和手算一致i33 × 2 6和手算一致i44 × 1 4和手算一致所以最终答案就是sum(a[i] × i × (N - i 1))i 从 1 到 N这是整道题的核心也是“智力题”三个字所在的地方。想通这一层代码怎么写都是对的想不通这一层写多少循环都是超时。2.2 贡献法的思维方式值得多说一句这种思路在算法竞赛里有个专门的说法叫“算贡献”或者“拆贡献”。它的核心思想是不直接枚举所有组合或子段而是反过来问每一个元素对最终答案的贡献是多少。我打个比方。假如班里要统计所有人一个月总共参加了多少天值日你当然可以把每天的名单挨个查一遍然后累加。但更快的做法是问每一个人“你这个月值了多少天”然后把这些值日天数加起来。前者就是枚举子段后者就是算贡献。回到这道题a[i] 的“值日天数”就是 i × (N - i 1)。这个次数完全由位置决定跟数字本身的大小没有任何关系。这也是为什么输入正数是什么、数值多大都不影响公式的结构。2.3 复杂度对比从 50 亿次到 10 万次如果用最朴素的枚举法N100000 时子段总数是N(N1)/2 ≈ 5 × 10^9就算你用前缀和把每个子段求和优化成 O(1)也要做 50 亿次这样的查询和累加。在 PAT 的评测环境下这几乎必然超时。而用贡献法只需要遍历一次数组每次做一次乘法和一次加法总共 10 万次操作时间复杂度 O(N)空间复杂度甚至可以做到 O(1)。这就是“智力题”和“暴力题”的分水岭。3. 测试点 3 到底坑在哪double 精度的极限3.1 现象本地样例全过提交就是 WA很多人的第一版代码长这样#include cstdio int main() { int n; scanf(%d, n); double ans 0.0; for (int i 1; i n; i) { double x; scanf(%lf, x); ans x * i * (n - i 1); } printf(%.2f\n, ans); return 0; }本地拿样例测输入 4、0.1 0.2 0.3 0.4输出 5.00一切正常。提交之后测试点 0、1、2 全过唯独测试点 3 答案错误。这时候最容易陷入的误区是怀疑公式。很多人把 i×(N-i1) 换着花样重写比如改成 (N-i1)×i或者把下标从 0 开始再调一遍结果还是不对。实际上公式没问题问题出在 double 类型根本扛不住这个量级的累加。3.2 答案量级估算double 的精度已经被整数部分吃光了要理解这个精度坑得先算算答案到底能有多大。考虑一个极限情况N100000且每一个数都取题目允许的上限 1.0。此时答案变成Σ i × (N-i1) N(N1)(N2)/6 ≈ 1.67 × 10^14这是一个 15 位的整数。double 的尾数只有 53 位二进制折算成十进制大约是 15 到 16 位有效数字。也就是说当累加结果到达 1.67×10^14 这个量级时double 的精度已经几乎被整数部分占满了小数点后面几乎没有剩余的有效位可用。更要命的是这个结果不是一次性精确算出来的而是 10 万次乘法、加法逐步累加出来的。每一次运算都会有一次舍入0.1、0.2 这些数在二进制里本来就是无限循环小数读入 double 时已经损失了一点精度每次乘法和加法再把误差往外扩一点。这些误差经过 10 万次累积之后完全可能影响小数点后第二位的四舍五入于是输出结果和标准答案差 0.01被判错。我在这里还专门统计过 double 的“最小分辨率”在 1.67×10^14 这个量级附近double 能表示的两个相邻数之间的间隔大约是 0.03125。你想想连 0.03125 都没法区分小数点后第二位怎么稳得住所以这不是运气问题而是必然翻车。3.3 long double 为什么能救回来在 Linux 的 GCC 环境下long double 是 80 位扩展精度有效数字大约 18 到 19 位十进制比 double 多出 3 到 4 位。同样面对 1.67×10^14 的整数部分它仍然能留出足够的精度给小数点后的位次所以保留两位小数时误差不会干扰到第二位。注意这里有个环境差异Windows 上 MSVC 的 long double 和 double 一样都是 64 位换 long double 等于没换。但 PAT 的评测环境是 Linux 加 GCC所以这个修复是真实有效的。如果你在本地 Windows 用某些编译器测试可能会觉得“明明换成 long double 还是不对”那是因为你本地的 long double 不是真正的 80 位扩展精度换到评测机上就正常了。3.4 乘法顺序里藏着一个更隐蔽的精度杀手就算你把累加变量改成了 long double也不代表万事大吉。看这一行ans x * i * (n - i 1);C 的乘法是从左往右结合的。先算 x × i这时 x 是 doublei 是 int结果是 double精度已经是 double 级别。然后这个 double 再乘 (n-i1)结果还是 double。只有在最后加到 long double 的 ans 时才被转成 long double但前面的乘法过程已经用低精度算完了后面再怎么提升都补不回来。正确写法是让链路中尽早出现 long doubleans x * (long double)i * (long double)(n - i 1);这样第一次乘法就是 double 和 long double 相乘结果立即提升为 long double后面的乘法全程保持高精度。这个细节非常隐蔽很多人以为“只要 ans 是 long double 就安全了”其实中间环节也要管住。顺便说一句x 本身是 double它读入时的精度损失无法恢复。但这是所有方案都要面对的输入误差不影响最终结果到小数点后两位我们需要避免的是后续运算把这个误差放大到不可接受的程度。4. 可提交的 C 代码与几个容易翻车的细节4.1 推荐写法全程 long double 参与运算下面是完整可提交的参考实现#include cstdio int main() { int n; scanf(%d, n); long double ans 0.0L; for (int i 1; i n; i) { double x; scanf(%lf, x); ans x * (long double)i * (long double)(n - i 1); } printf(%.2Lf\n, ans); return 0; }这里做了三件关键的事累加变量设为 long double在乘法链路里主动把整数因子提升为 long double用 printf 的 %Lf 输出 long double 类型很多题解写成ans x * i * (n-i1)虽然评测数据可能放过了但严格来说中间乘法还是 double 精度属于“侥幸过关”。我给出的写法更稳。4.2 备选方案输入放大 1000用整数彻底绕开浮点如果你对浮点极其不放心还有一条更刚的路把每个输入值放大 1000 倍转成整数全程用 long long 累加最后再除以 1000。因为题目输入的数通常最多两位小数放大 1000 后不会引入额外误差。#include cstdio #include cmath int main() { int n; scanf(%d, n); long long ans1000 0; for (int i 1; i n; i) { double x; scanf(%lf, x); long long xi llround(x * 1000.0); ans1000 xi * (long long)i * (long long)(n - i 1); } long double ans (long double)ans1000 / 1000.0L; printf(%.2Lf\n, ans); return 0; }这里有两个细节必须注意第一放大取整时要用 llround 做四舍五入不能直接强转 long long。因为 0.29 × 1000 在 double 里很可能算出 289.99999999999994直接强转整型会得到 289一个“放大千分之三”的误差就埋进去了。llround 会把 289.99999999999994 正确转成 290。第二最终输出时不要用printf(%.2f\n, ans1000 / 1000.0)。前面算过ans1000 最大约 1.67×10^17除以 1000 后是 1.67×10^14这个量级的 double 最小分辨率在 0.03 附近百分位已经不稳了。正确做法是先把 ans1000 转成 long double 再除以 1000.0L最后用 %.2Lf 输出。顺带验证一下整数方案的数值上界ans1000 最大约 1.67×10^14 × 1000 1.67×10^17而 long long 的上限是 9.22×10^18所以完全装得下不用担心溢出。4.3 输出格式与本地自测用 printf 输出 long double 时格式是%.2Lf注意是大写 L。如果你习惯用 cout也可以这样写#include iostream #include iomanip using namespace std; cout fixed setprecision(2) ans endl;C 的 ostream 对 long double 有专门的重载直接这样输出没有问题。但我的个人习惯是在算法题里统一用 printf 处理格式化输出因为代码更紧凑也不容易受到 I/O 流同步设置的影响。本地自测时除了样例之外一定要构造极限数据验证精度100000 1.0 1.0 1.0 ...共 100000 个 1.0这个数据的标准答案就是 N(N1)(N2)/6也就是 166671666700000.00 左右。你可以先用 Python 的浮点高精度或者写个 __int128 版本算一遍再用 C 的 double 版和 long double 版分别跑对比一下输出立刻就能看出 double 版在哪一位开始飘。5. 从这一题带出来的通用经验5.1 遇到“所有子段/子区间”的求和题先想贡献法“求所有连续子段的某种属性的总和”是算法题里非常常见的套路。一旦看到这种描述第一反应不应该是枚举子段而是思考“每个位置的元素被计算了多少次”。1104 是贡献法最经典的入门题公式简洁、推导自然比死记硬背强多了。类似的思路还会出现在很多题目里某个元素在多少个区间里作为最小值、最大值在多少个区间里被包含等等。掌握“贡献法”之后这类题在你眼里就不再是“怎么枚举”而是“怎么数次数”。5.2 见到浮点输出要求先估算答案上界我给自己定了一条规矩凡是输出要求保留小数的题先把答案量级估算一遍再决定用什么浮点类型。答案量级在 10^7 以下double 随便用误差很难影响两位小数答案量级在 10^7 到 10^12 之间double 勉强可用但要注意乘法顺序和累加次数答案量级超过 10^12还要求小数点后精度直接换 long double或者认真考虑整数放大方案1104 的答案量级是 1.67×10^14正好落在“double 已经撑不住”的区间。如果你提前做了这个估算测试点 3 根本不会让你意外。5.3 卡精度时怎么定位不是怀疑公式而是复现误差很多人遇到 WA 的第一反应是改公式这是浪费时间。正确的定位方式是把公式拆成“逻辑”和“数值”两层逻辑对不对用小数据验证数值稳不稳用极限数据验证。我给一个标准的排查流程先用样例小数据确认公式正确再用 N100000 全 1.0 的极限数据跑出结果拿一个高精度参考值比如把 ans1000 全部用 long long 手算出来和当前输出对比如果逻辑全对但极限数据对不上100% 是浮点类型或乘法顺序问题这个方法不仅适用于 1104也适用于所有浮点相关的题目。与其反复提交去猜测试点不如在本地把误差复现出来一次改对。最后再分享一个我个人的体会PAT 甲级里真正卡人的往往不是算法本身而是这些“你自以为知道、但其实没吃透”的语言细节。double 的精度是很多人的盲区因为它在小数据下表现得太完美了。吃过 1104 这个亏之后我每次写浮点累加都会多看一眼类型、多想一步量级这个习惯在后来的刷题路上帮我省下了大量返工时间。