PAT甲级1104：连续子段求和的贡献法推导与long double精度坑-北京尧图网络

PAT甲级题库里1104 这道题我给它的评价是最不像 20 分题的 20 分题。题目叫 Sum of Number Segments给你 N 个浮点数让你求所有连续子段的和。第一反应自然是套两层循环暴力枚举但等你一算复杂度人直接傻眼。这题真正的考点根本不是枚举而是你能不能发现每个元素在整个答案中被统计了多少次。等你高高兴兴写出 O(N) 公式版本后测试点 3 又会教你怎么做人——double 精度那个坑几乎每个认真刷过的人都被它恶心过。这篇文章我会从暴力思路开始讲然后推导数学规律再给终版能稳定 AC 的 C 代码重点拆解测试点 3 的精度问题到底出在哪。适合正在刷 PAT 甲级的朋友也适合遇到过明明思路对了却卡精度这类问题的选手。1. 先看懂题意这不是普通求和是连续子段求和题目输入很简单第一行一个正整数 N第二行 N 个浮点数。要求输出所有连续子段的和保留两位小数。什么叫连续子段比如数组[0.1, 0.2, 0.3]它的连续子段有长度为 1 的[0.1]、[0.2]、[0.3]长度为 2 的[0.1, 0.2]、[0.2, 0.3]长度为 3 的[0.1, 0.2, 0.3]一共 6 个子段把它们的和全部加起来就是答案。对于 N3 这个小数据口算都能算出来但这题的 N 最大能给到 10^5也就是说子段总数是 N*(N1)/2约 50 亿。这还没算求和本身的成本。1.1 暴力枚举的复杂度为什么一定超时最朴素的做法是三联循环枚举左端点、右端点再遍历区间求和。这是 O(N^3)在 N10^5 的时候要执行约 10^15 次操作。哪怕你优化成前缀和枚举左右端点也还是 O(N^2)大概 10^10 次操作依然不可能在 1 秒内跑完。// O(N^3)想都不要想 for (int l 1; l n; l) for (int r l; r n; r) for (int k l; k r; k) sum a[k];用前缀和能砍掉最内层循环// O(N^2)N1e5 时依旧是天文数字 vectordouble prefix(n 1, 0.0); for (int i 1; i n; i) prefix[i] prefix[i - 1] a[i]; double ans 0.0; for (int l 1; l n; l) for (int r l; r n; r) ans prefix[r] - prefix[l - 1];也就是说只要你还停留在枚举子段这个思路上哪怕优化到前缀和这题也过不了。这就逼着你去找子段的结构规律。1.2 为什么说这是一道智力题这种题在 PAT 里经常被叫智力题因为它没有高级算法纯粹考观察力和数学推导。你看出规律后用 O(N) 实现代码不超过二十行看不出来在测试点面前就只能干瞪眼。它属于典型的贡献法计数模型不要想每个子段是什么样而是反过来想每个元素在多少个合法子段里出现过。想通了这一点这个题就从求和问题变成了组合计数问题。2. 核心推导每个数到底被加了多少次假设数组下标从 1 开始当前元素是a[i]。我们要统计的是在所有连续子段中a[i]总共被包含了几次。任意一个连续子段可以写成[L, R]其中1 ≤ L ≤ R ≤ N。这个子段要包含a[i]就必须满足左端点 L 要在 i 的左边或等于 i也就是1 ≤ L ≤ iL 有 i 种取法。右端点 R 要在 i 的右边或等于 i也就是i ≤ R ≤ NR 有 N - i 1 种取法。左端点和右端点的取值是相互独立的所以a[i]被包含的总次数就是次数 i * (N - i 1)这个公式是整个题目的灵魂。2.1 手工验证一遍确保没推错拿 N3 举例。三个元素分别是a[1]、a[2]、a[3]我把所有子段展开写一遍子段包含的元素[1,1]a[1][1,2]a[1], a[2][1,3]a[1], a[2], a[3][2,2]a[2][2,3]a[2], a[3][3,3]a[3]数一下出现次数a[1]出现了 3 次公式计算1 * (3 - 1 1) 3一致。a[2]出现了 4 次公式计算2 * (3 - 2 1) 4一致。a[3]出现了 3 次公式计算3 * (3 - 3 1) 3一致。于是答案可以写成ans a[1] * 1 * 3 a[2] * 2 * 2 a[3] * 3 * 1这样看就非常直观了每个数乘以一个只跟位置 i 和总数 N 有关的系数累加即可。2.2 为什么这个推导能直接决定复杂度有了公式处理第 i 个位置的数时只需要知道 i 和 N。这意味着不需要存储整个数组边读边算空间复杂度 O(1)。只需要一次循环遍历时间复杂度 O(N)。N10^5 时循环十万次几乎瞬间出结果。这就是数学规律带来的质变。如果你在考场上一时推不出来也可以用小规模数据手算找规律比如 N4 或 N5 的时候把每个元素的出现次数列出来很容易看出i * (N - i 1)这个模式。3. 测试点 3 的两个坑int 溢出和 double 精度思路对了代码写得也快但很多人第一次提交就是过不了测试点 3而且本地样例全对。这个测试点就是专门来卡两件事的一是 int 溢出二是 double 精度。3.1 第一个坑i * (N - i 1)在 int 范围内会炸i和N - i 1都是 int 类型当 i 接近 N/2 时两者相乘接近10^5 * 10^5 10^10这已经远远超过 int 能表示的上限了。int 的最大值是 2147483647约 2.1 * 10^9。而 10^10 是它的五倍左右。如果你这样写int cnt i * (n - i 1); ans a[i] * cnt;结果就是溢出cnt 变成一个无意义的负数或者被截断的值最终答案完全错误。正确做法是用 64 位整数承接long long cnt 1LL * i * (n - i 1);关键点是1LL把乘法强制提升到 long long 级别避免中间结果在 int 阶段就溢出。这一步是很多第一次提交的人踩的第一个雷。3.2 第二个坑溢出修好了精度依然会挂如果只是溢出问题换 long long 就够了。但这个题真正阴险的是测试点 3 的精度设计。很多人修完溢出以后代码长这样long double ans 0.0L; for (int i 1; i n; i) { double x; scanf(%lf, x); long long cnt 1LL * i * (n - i 1); ans x * cnt; } printf(%.2Lf\n, ans);你觉得这次总该 AC 了吧并不一定。问题在于x * cnt这一步的运算精度。C 里x是 doublecnt是 long long。计算x * cnt时编译器会把 cnt 转成 double 再运算。于是整个乘法变成了 double 乘法最后相加时虽然被提升到 long double但乘法那一下已经把误差带进去了。double 的结构是 52 位尾数加一个隐含位总计约 53 位二进制精度十进制大概 15 到 17 位有效数字。听起来不少但问题是像0.1、0.2、0.05这类十进制小数在二进制里本身就是无限循环小数存进 double 的那一刻就已经发生了舍入。你可以理解为十进制里的1/3永远写不精确只能写成0.3333...截断到某一位。同理二进制里的0.1也是一个无限循环小数double 只能保存它的近似值。如果只是单独存一个0.1误差极小通常不影响保留两位小数的输出。但这个题里这个近似值要乘以cntcnt 是个接近 10^10 级别的超大整数。一乘误差被放大了几十亿倍。更麻烦的是你需要循环 N 次每一次的误差都会累加到最终结果里。测试点 3 的数据很可能专门设计了一批让误差累积到四舍五入边界附近的值。double 版本的答案可能正好差 0.01输出后与标准答案对不上于是 WA。3.3 为什么 long double 能解决问题long double 在常见的 x86 Linux 评测环境中是 80 位扩展精度格式尾数位约 64 位有效十进制精度接近 18 到 19 位。它虽然也不能精确表示所有十进制小数但每一步的近似误差都比 double 小几个数量级。你可以把 long double 想成一台更精准的秤double 能称到小数点后十来位long double 能称到小数点后快二十位。在这个题的量级下long double 累计出来的误差几乎不会影响到小数点后两位的输出。所以正确的思路是让乘法运算全程在 long double 精度下完成不要中间先转成 double。4. 稳定过测试点 3 的完整 AC 代码下面这段代码是我实际刷题后认为最稳妥的写法之一。它同时规避了 int 溢出和 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); long long cnt 1LL * i * (n - i 1); ans (long double)x * (long double)cnt; } printf(%.2Lf\n, ans); return 0; }这段代码的核心改进就一行(long double)x * (long double)cnt。两边都显式转成 long double保证乘法在扩展精度下进行不会在 double 阶段产生意外舍入。还有另一种更彻底的写法直接用%Lf读入 long double#include cstdio int main() { int n; scanf(%d, n); long double ans 0.0L; for (int i 1; i n; i) { long double x; scanf(%Lf, x); long long cnt 1LL * i * (n - i 1); ans x * (long double)cnt; } printf(%.2Lf\n, ans); return 0; }第二种写法的思路是既然要全程用 long double那连读入都直接用 long double 解析连末尾的(long double)x都省了。注意scanf的 long double 格式符是%Lf大写 L。4.1 两种写法的取舍从逻辑上讲第二种更干净但要注意%Lf的兼容性。在 Linux 下的 GCC 编译环境里完全没问题但如果你在 Windows 本地用某些编译器测试%Lf可能有兼容性问题比如输出乱码或解析不了。如果担心本地调试和评测环境行为不一致第一种写法更保守读入用大家都熟悉的%lf存到 double计算时再转 long double。反正输入数据本身是十进制文本double 读入导致的误差很小经过 long double 乘法后对结果的影响微乎其微。实测下来两种都能稳定 AC。4.2 关于输出格式的一个忠告long double 的输出要用printf(%.2Lf, ans)这里的 L 是大写不能写成%lf也不能写成%.2f。格式符写错轻则输出错误重则未定义行为。有人习惯用 cout#include iomanip cout fixed setprecision(2) ans endl;这会调用 iostream 对 long double 的输出重载也能做到保留两位小数。但如果你同时用了 lots ofprintf和cout记得不要混用同步问题比赛里一般无所谓但省心起见全程用 printf 更统一。5. 常见问题与排查实录我把刷这题时大家踩过的典型问题整理成了一张速查表每个问题都是我见过或者被问过无数次的。症状可能原因处理方法本地自己造样例全对一提交就 WA 测试点 3乘法精度在 double 阶段被舍入用(long double)x * (long double)cnt保证全程 long double答案输出是个负数或者明显不对i * (n - i 1)的 int 乘法溢出改成1LL * i * (n - i 1)或(long long)i * (n - i 1)输出始终是 0.00用了%d读浮点数或读入变量类型不对检查scanf格式符浮点数用%lf/%Lfprintf(%.2Lf)在本地编译不过本地编译器对 long double 支持较弱改用cout fixed setprecision(2)输出内存超限写了数组存全部 N 个数N1e5 其实也不大但没必要用边读边算完全不需要数组公式会写但不知道如何验证不确定推导是否正确手写 N3、N4 枚举全部子段验证系数5.1 测试点 3 到底卡了什么为什么有人 double 能过我遇到过很多读者问为什么我用 double 也过了这里要说明double 能不能过很大程度取决于测试数据和你写乘法的顺序。C 表达式的结合性会改变误差的分布。比如ans x * i * (n - i 1);它实际按左结合执行(x * i) * (n - i 1)x 先乘一个最大 10^5 的整数再乘另一个最大 10^5 的整数。这种顺序下的舍入误差可能和x * (i * (n - i 1))不一样。有些数据下某一种运算顺序的误差刚好不影响四舍五入后的两位小数所以就过了。但这不是稳定的做法。测试点 3 之所以叫坑点就是因为它专门设计了一些让你最普通的写法暴露误差的数据。所以我给的建议是不要赌运气不要依赖乘法顺序碰巧误差小直接上 long double。这种题在 PAT 的判分环境下long double 就是最稳的选择。5.2 如果你非要用 double也有一个补偿方案我知道有些人对 long double 的输出和平台兼容性有顾虑或者想追求只用 double 也能过。这时候可以试试 Kahan 求和算法也就是补偿求和。它的思路是单独维护一个丢失的低位误差变量每次加法时把上一步舍去的误差补回来。double ans 0.0, c 0.0; for (int i 1; i n; i) { double x; scanf(%lf, x); long long cnt 1LL * i * (n - i 1); double y x * cnt - c; double t ans y; c (t - ans) - y; ans t; }这个做法能在一定程度减少累加误差但对单个乘法已经产生舍入的问题帮助有限因为x * cnt这步的误差依然存在。所以我不把它当主力方案只作为一个拓宽思路的补充。擂台赛也罢刷题也罢能简单就别搞复杂long double 一行搞定的事没必要用 Kahan。5.3 边界情况别忽略N1 的时候只有一个子段就是它自己。公式里i 1次数1 * (1 - 1 1) 1结果就是那个数本身保留两位小数没毛病。N0 呢这题显然不会给 N0至少我没见过这种边界。但如果你写通用代码循环不进ans0输出 0.00也不算错。最阴间的情况是输入的数本身带前导空格、换行用标准的scanf都能自动跳过空白符不用额外处理。6. 这类题的经验总结贡献法思维最后说一点超越这道题本身的心得。PAT 里有一类题表面上是求和题实际上是计数题。它们都有一个共同特征数据规模大到你不可能枚举所有元素组合但答案可以表达成每个元素对最终答案的贡献之和。遇到这种题我现在的第一反应不是写循环而是先在草稿纸上算小数据。比如 N3 时把子段全列出来看每个元素被加了多少次。一旦发现次数跟下标位置有稳定的数学关系整个题的复杂度就降下来了。1104 的公式i * (N - i 1)其实非常优美它把左右端点的可能性拆开相乘本质上是一个组合计数。类似的每个元素被统计多少次的套路在很多题目里都能见到。学会这种思维之后再看到一个求和题你会下意识地问自己一句话每一项对答案贡献了多少这个贡献能不能用公式表达另一个教训就是浮点数精度。算法竞赛里能用整数就不要用浮点数必须用浮点数时能用 double 就尽量用 double但如果你发现输出结果差零点几或者差一位小数别急着怀疑逻辑先想想是不是浮点误差被放大了。这种时候换 long double 往往立竿见影。我个人的习惯是涉及大量浮点累加、且对结果精度要求较高的题一上来就直接用 long double 做累加变量省得后面反复提交排查。这个习惯帮我避开了很多莫名其妙的 WA。希望这篇文章也能帮你少踩一次 1104 测试点 3 的坑。

PAT甲级1104：连续子段求和的贡献法推导与long double精度坑

相关推荐

OpenAI SDK平滑迁移，如何零代码重构接入新API？

程序员英语词汇宝典精讲：consumption（消耗）——资源监控、消息消费与性能分析中的高频技术词汇

车辆动力学标定实战：从参数辨识到模型验证的完整流程

更多资讯

广义Hough变换的自适应阈值区间：解决投票累积的调参难题

ChatGPT指令集实战：从PDF拆解到角色扮演稳定输出

基于MP2642GR-Z与MK24FN256VDC12的2S电池主动均衡BMS设计

DeepSeek职场落地实战：结构化提示语与轻量部署指南

海康机器人算法SDK实战：从跑通Demo到工业级部署

覆盖索引与超长分页优化

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？