如果你刷过 PAT 甲级题库一定见过这道“智力题”味的题目1104 Sum of Number Segments (20分)。题面只有一句话意思就是给一串正数求所有连续子段各自的和再把所有和加起来。听起来是个人都会做三层循环一写样例一跑妥妥的。可一旦把测试数据放大到 100000 个数暴力和前缀和全部歇菜只有找到那个隐藏在排列组合里的数学规律才能在二十行代码内一次性 AC。更阴的是就算你想通了公式测试点 3 还会用两个经典坑继续卡你一个藏在 C 的 int 溢出里一个藏在 double 精度里。这篇博文就把从暴力到正解、从推导到避坑全流程讲透帮正在备考 PAT 甲级或准备公司机试的朋友少走弯路。1. 题意拆解这题到底在算什么1.1 题目在说什么先还原一下题面。输入一个整数 N接下来给 N 个正数要求计算所有连续子段的和的总和。这里的“连续子段”也叫“子列”或“子数组”指的是原序列中位置连续的一段长度可以是 1也可以是整个序列。样例是这样的4 0.1 0.2 0.3 0.4输出是5.0为什么是 5.0把长度从 1 到 4 的全部连续子段列出来再一个个求和长度 10.1、0.2、0.3、0.4和是 1.0长度 20.10.20.3、0.20.30.5、0.30.40.7和是 1.5长度 30.10.20.30.6、0.20.30.40.9和是 1.5长度 40.10.20.30.41.0四行加起来是 1.0 1.5 1.5 1.0 5.0正好对上。如果你第一次看到这题就写出三层循环不丢人。N 小的时候确实能过但题目不会这么好心N 的上限是 100000。三层循环是 O(N³) 数量级这谁都扛不住退一步用前缀和优化成两层循环复杂度 O(N²)也就是最多要跑一亿次级别的运算在竞赛环境下依然会超时。所以这道题被很多人喊作“智力题”就是因为正确做法根本不是“枚举”而是“统计贡献”。1.2 为什么不能老老实实枚举我最初刷这题时思路是先用前缀和把区间和查询变成 O(1)然后两层循环枚举左右边界。代码倒是好写样例也过结果提交以后眼前一黑测试点 3 直接超时。事后算了一下N100000 时所有连续子段总数是 N*(N1)/2也就是大约 50 亿个区间。就算每个区间用 O(1) 的前缀和查询50 亿次运算在一秒钟内也跑不完。更不要说如果傻乎乎地三层循环对每个区间再累加一遍那计算量直接奔着万亿级别去了。这个“50 亿”给了我一个很重要的提示既然子段数量本身巨大我们就不可能真的去遍历每个子段。换个角度想一个子段的值是由里面每个元素累加出来的那能不能反过来不去枚举子段而是枚举每个位置的数算它一共被多少个不同的子段包含如果能把这个“包含次数”算出来答案就是所有 a[i] 乘上对应次数的总和。这就是这道题的核心突破口。2. 核心公式推导贡献法一次讲透2.1 一个位置出现多少次假设原序列一共有 N 个数下标从 0 开始数也就是 0 到 N-1。现在随便挑其中一个位置 i问在所有连续子段里有多少个子段会把下标 i 这个元素算进去设一个连续子段用区间 [L, R] 表示L 是子段左端点的下标R 是右端点的下标。要想包含位置 i必须满足 L ≤ i ≤ R。于是问题被拆成两个独立的部分左端点 L 能取哪些值因为 L 不能超过 i最小可以是 0所以 L 的取值范围是 0, 1, ..., i一共 i1 种。右端点 R 能取哪些值因为 R 不能小于 i最大可以是 N-1所以 R 的取值范围是 i, i1, ..., N-1一共 N-i 种。L 和 R 互相独立根据乘法原理包含位置 i 的连续子段数量就是count(i) (i 1) * (N - i)所以要求的最终答案就是ans Σ a[i] * (i 1) * (N - i) i 从 0 到 N-1如果你习惯从 1 开始编号比如 i 表示第 i 个数但从 1 数起那公式会写成ans Σ a[i] * i * (N - i 1)两种写法本质一样关键是别把坐标系的偏移搞混。我写代码时偏爱 0 下标那套因为数组本来就是从 0 开始的。2.2 用生活化类比加深印象这个概念可以用一个很土的类比来记把数组里的每个位置想象成一条街道上的门牌号 i连续子段就是从某个门牌 L 一路连续走到某个门牌 R 的一段路。你要问“门牌 i 会被多少条可能的路线覆盖”那答案就是路的起点可以是 i 左边任意一家含自己共 i1 家路的终点可以是 i 右边任意一家含自己共 N-i 家。起点选在左边终点选在右边一条路线就唯一确定所以总共就是 (i1)(N-i) 条。这个类比我每次给同学讲都很好用因为它把抽象的计数器变成了一个“选左端点、选右端点”的组合问题不容易记错。2.3 拿小样例验证公式用题目给的样例验算一遍。N4数组是 0.1、0.2、0.3、0.4。下标 i元素值出现次数 (i1)(N-i)贡献00.11×440.410.22×361.220.33×261.830.44×141.6四行贡献加一起0.4 1.2 1.8 1.6 5.0和前面手动枚举子段的结果完全一致。这说明公式没问题。想通这一步以后代码就变得极其平凡读一个数算一次出现次数乘进去累加。整个过程只需要一层循环一眨眼就完成。3. 代码实现与两个致命坑点3.1 错误写法整数先乘直接溢出公式这么简单代码写起来却有几个暗坑。最容易踩的就是下面这种写法int n; cin n; double ans 0; for (int i 0; i n; i) { double x; cin x; ans (i 1) * (n - i) * x; // 错误示范 }注意看这一行(i 1) * (n - i) * x。在 C 里乘法的结合顺序是从左到右所以会先算(i 1) * (n - i)。问题是i 1和n - i都是 int 类型它俩先乘结果还是 int。当 N100000 时i 取中间位置时(i1)*(n-i)能达到大约 25 亿已经超过 int 能表示的上限 2147483647于是发生整数溢出。溢出后的结果可能是一个负数也可能是一个被截断的乱值再乘上浮点数去累加答案自然是错的。这个坑很阴险因为小数据的时候它完全不爆样例怎么跑怎么对。只有测试点 3 这种 N 拉满的数据才会触发所以很多人在测试点 3 WA 了一整天才发现是类型问题。3.2 推荐写法让浮点数先参与运算正确思路是让浮点数在乘法链的最前面出现比如ans x * (i 1) * (n - i);这时候第一个乘法是x * (i 1)由于 x 是 double(i1) 会被自动转换成 double后面的(n - i)同理整个乘法链全程都是 double不会走 int 乘法自然不存在整数溢出。如果担心别人读代码时不理解为什么这么写也可以更显式地强转ans x * (long long)(i 1) * (n - i);先转成 long long避免 int 乘法溢出再和 double 相乘。两种写法都能 AC但我个人更推荐让浮点数先乘那种因为代码短而且从第一眼就能看出你不是“不小心”写出来的。3.3 精度坑float 真的会挂第二个坑出在变量类型上。用 float 去读元素、甚至用 float 去累加答案在测试点 3 会精度不足。float 有效数字大约只有 7 位而这题 N 最大 100000答案累计量级可能很大加上大量小数位的运算误差最后保留一位小数时非常容易差出 0.1 或者更多。double 有效数字大约 15~16 位配合正确乘法顺序精度是完全够用的。如果还不放心可以上 long double精度更高。但要注意 long double 的读入和输出格式跟 double 不一样读入要用%Lf输出用%.1Lf一旦格式写错输出会变成 0.00非常容易把自己搞懵。所以我的建议是用 double 读入、用 double 累加这是最稳的默认选择不要用 float不要用 int 做中间乘法除非你对 long double 的 IO 格式很有把握否则优先 double如果数据量极大且题目答案非常接近整数边界long double 可以作为保险但要记得统一格式。3.4 输出格式别忘保留一位小数题目明确要求结果保留一位小数所以输出用printf(%.1f\n, ans)最直接。如果你喜欢用 cout需要这样写cout fixed setprecision(1) ans \n;不要以为样例输出是5.0就能不处理小数位直接输出 5 也是不行的格式错误照样扣分。我见过有人用 long double 做累加最后却用%lf输出结果输出 0.0排查了半天才发现是格式符和变量类型不匹配。4. 完整可提交代码与本地自测4.1 一份可以直接提交的 C 代码把前面的推导和避坑经验收拢到一起一份保险、简短、能过测试点 3 的完整代码如下#include cstdio int main() { int n; scanf(%d, n); double ans 0.0; for (int i 0; i n; i) { double x; scanf(%lf, x); ans x * (i 1) * (n - i); } printf(%.1f\n, ans); return 0; }这个版本只用了 O(N) 时间、O(1) 额外空间N100000 跑完几乎不耗时测试点 3 不会超时也不会踩 int 溢出和 double 精度不足的雷。如果你本地的编译器对 double 不太放心也可以改成 long double 版本#include cstdio int main() { int n; scanf(%d, n); long double ans 0.0L; for (int i 0; i n; i) { long double x; scanf(%Lf, x); ans x * (i 1) * (n - i); } printf(%.1Lf\n, ans); return 0; }大部分 Linux 环境下的 g 对%Lf支持良好PAT 在线评测环境没问题。不过如果你在自己 Windows 上用 MinGW 测试偶尔会遇到 long double 输入输出不对的怪事这时候切回 double 版本就好。4.2 一个省内存的小技巧注意代码里没有开数组而是读一个数就立刻算贡献。这背后有个很重要的原因公式只依赖当前下标 i 和总数 n不依赖后面还没读进来的数。所以完全可以边读边算省掉 N 个 double 的存储空间。如果题目把输入限制在普通范围内这招能省下接近 1MB 内存对 PAT 这种内存管得不严的题没什么本质差别但思路本身值得养成习惯能在线处理就别急着存数组。4.3 本地自测用例写完代码不要急着提交先跑这几个用例确认自己的公式和输出格式没写错输入4加0.1 0.2 0.3 0.4输出5.0。这是题目样例必须对。输入1加0.5输出0.5。只有一个数时连续子段只有这一项答案就是它本身出现次数 1×11。输入2加0.1 0.2输出0.6。手动算一下三个子段分别是 0.1、0.2、0.10.20.3总和 0.6。输入3加0.1 0.1 0.1输出1.0。三个单元素子段、两个二元素子段、一个三元素子段总和 0.30.40.31.0。输入5加1 2 3 4 5输出整数意味的33.0我不会直接告诉你建议你用公式自己算一遍再和两个不同写法的程序对拍这是检验公式理解是否到位的好办法。单个样例不够最好再写个随机数据生成器生成 N100000 的小数用“正确版本”和“故意写错的版本”跑一遍输出差异你能更直观地感受测试点 3 到底在测什么。5. 常见问题排查与考场经验5.1 高频问题速查表我在做这道题过程中以及帮同学排查代码时收集了一堆高频问题整理成表症状可能原因解决方案测试点 3 WA(i1)*(n-i)两个 int 先乘溢出把浮点数写在乘法链前面或强转 long long测试点 3 WA用了 float 类型读入或累加换成 double 或 long double输出 0.0long double 用了%lf输出格式不匹配用%Lf读入、%.1Lf输出测试点 1、2 WA下标公式写错比如少乘了 1检查是否漏了(i1)或(N-i)建议先用小样例手推运行超时用了 O(N²) 前缀和枚举左右端点改用贡献公式把循环压到 O(N)答案比预期大循环从 1 到 N但公式用了 0 下标版本坐标系统一要么全 0 下标要么全 1 下标这张表里最显眼的是第一行和第二行两者都集中在测试点 3。所以你在搜题解时会看到有人喊“测试点3 double精度坑点”其实里面既包含浮点精度不够的问题也包含 int 中间乘法溢出的问题两个根因都可能让同一个测试点挂掉。5.2 考场上怎么快速想到贡献法很多同学问我“这种题我考场上怎么才知道要用数学推导”我的判断标准很简单看数据范围。N 到 100000 甚至 200000而题目又要求枚举所有子区间那八成不是让你真枚举而是让你找一个统计规律。更直接地说只要题面出现“所有子数组”“所有连续子段”“所有区间”再加上“求和”三个关键词优先往贡献法上想每个元素对答案产生多少次影响。不是暴力去组合出所有区间而是单独计算每个点被计入的次数。这是区间类题目里非常通用的一种建模思路。还有一个很实用的考场动作先手推 N2、N3 的小样例把每个位置的出现次数列出来比如 N3 时三个位置出现次数分别是 3、4、3。看到这个数列你很容易发现它并不均匀而中间最大两侧对称这就和(i1)*(N-i)的图像对上了。一旦你手推出了对称模式公式基本就水落石出。5.3 同源题型扩展贡献法不止能用在这道题。比如二维矩阵里求所有子矩阵元素和的总和做法是每个格子 a[i][j] 的贡献等于(i1)(n-i)(j1)(m-j)行列方向各自算包含次数再相乘。又比如统计数组里所有子数组的极差和、所有子序列的某个属性很多都能拆成“每个元素作为最大/最小/边界时被计数多少次”。刷题量上去了以后你会发现PAT 甲级里这类“枚举会爆炸、计数是正解”的题其实有一小撮1104 是最典型也最友好的一道。5.4 我个人的提交血泪史最后说点题外话。这道题我第一次提交用的是前缀和版本测试点 3 果然超时。当时没找到数学规律去查题解看到公式第一反应是“这么短”然后自己动手推了一遍才心服口服。改完算法以后我又因为在乘法链里把整数写到前面测试点 3 从 TLE 变成了 WA当时整个人都是懵的。后来 printf 调试发现(i1)*(n-i)在 N100000 时会算出负数才明白 int 溢出的可怕之处。这道题给我留下的最大收获不是那个公式本身而是三条解题习惯第一看到区间枚举先算复杂度N 超过 10000 就要警惕 O(N²) 方案 第二写乘法链时把浮点数放最前面看不到任何风险才提交 第三提交前用大数据自测一遍专门制造 A 大条件触发溢出和精度问题别只测样例。这三条习惯后来帮我在好几次机试里躲过了类似的坑也推荐给你。如果你正在刷 PAT 甲级遇到 1104 这道题别急着一遍遍试错。先拿张纸把包含次数推清楚再回来写代码你会觉得这 20 分拿得明明白白。