蓝桥杯国赛“和与乘积”题解：从暴力枚举到数学洞察的算法优化

1. 项目概述从“和与乘积”看蓝桥杯国赛的思维跃迁拿到“蓝桥杯国赛 和与乘积”这个标题很多C选手的第一反应可能是去搜索现成的答案。但作为一名带过不少学生打比赛的老兵我想说这道题的价值远不止一个AC代码。它是一道典型的、能够清晰区分“背题选手”和“思维选手”的国赛级题目。题目本身描述起来并不复杂给定一个长度为 n 的整数数组你需要找出有多少个连续子数组满足该子数组所有元素的和等于所有元素的乘积。听起来是不是有点像一道简单的枚举题但国赛的坑往往就藏在“简单”的描述之下。这道题的核心是逼迫你在暴力枚举的朴素思维上进行多层次的优化和数学洞察最终在有限的时间和内存内通常是1秒128MB优雅地解决问题。它考察的不仅仅是C语法和STL的熟练度更是对问题性质的分析能力、对算法复杂度的掌控力以及将数学结论转化为高效代码的工程实现能力。接下来我就带你彻底拆解这道题不仅给你答案更要给你一套遇到类似“计数类”、“连续子数组”问题的通用思考框架和优化工具箱。2. 核心思路解析为什么暴力枚举会“爆炸”我们先从最直观的想法开始枚举所有可能的连续子数组然后计算它们的和与乘积判断是否相等。一个长度为 n 的数组其连续子数组的总数是n*(n1)/2这个量级是 O(n²)。对于每个子数组计算和与乘积需要 O(子数组长度) 的时间。最坏情况下总时间复杂度会逼近 O(n³)。当 n 达到 10^5 的级别时n³ 是 10^15 的数量级这显然是不可接受的在1秒的时间限制内必然超时。所以第一个优化点来了我们能否在枚举子数组的同时快速计算其和与乘积而不是每次都从头算起这就是经典的“前缀和”与“前缀积”思想。预处理出前缀和数组prefixSum[i]表示前i个元素的和和前缀积数组prefixProduct[i]表示前i个元素的积。那么对于子数组[l, r]下标从1开始其和 prefixSum[r] - prefixSum[l-1]其积 prefixProduct[r] / prefixProduct[l-1]。这样判断一个子数组是否满足条件的时间就降到了 O(1)。整体复杂度优化到了 O(n²)。对于 n10^3 或许还能勉强一试但对于国赛数据n10^5 时O(n²) 仍然是 10^10 级别还是不行。注意使用前缀积要非常小心零元素因为一旦遇到0前缀积就变成0并且后续一直都是0除法会失效除零错误。这是第一个需要处理的边界条件也暗示了题目可能包含0。既然 O(n²) 不行我们就必须寻找 O(n log n) 甚至 O(n) 的解法。这就需要深入挖掘题目中“和等于积”这个条件的数学性质。这是本题思维跃迁的关键。2.1 数学性质挖掘非1元素的数量限制让我们思考在什么情况下一串正整数的和会等于它们的积 假设子数组包含 k 个元素a₁, a₂, ..., aₖ。 我们知道对于正整数只有当大部分元素都是1时和才有可能追上积。因为乘法比加法增长快得多。 更精确地我们可以考虑非1元素即大于等于2的元素的个数。结论1在一个和等于积的正整数子数组中非1元素≥2的个数不能超过1个。我们来证明一下 假设有两个非1元素 a 和 ba, b ≥ 2。 那么它们的乘积至少是 ab而它们的和最多是 ab当其他元素都是1时。 我们需要 ab ≤ ab。 移项得 a*b - a - b ≤ 0 (a-1)(b-1) ≤ 1。 由于 a, b ≥ 2则 (a-1) ≥ 1, (b-1) ≥ 1所以 (a-1)(b-1) ≥ 1。 等号成立的条件是 a2 且 b2此时 (2-1)(2-1)1。 也就是说仅当两个非1元素都是2时才有可能满足。但此时子数组为 [2, 2]和为4积为4确实相等。如果还有第三个非1元素c≥2那么 (a-1)(b-1)(c-1) ≥ 1且加上c后积的增长会远大于和的增长等式不可能成立。因此所有满足条件的子数组根据其包含的非1元素个数只能分为三类全1子数组任意长度的连续1组成的子数组。此时和长度积1所以只有长度为1的全1子数组即单个1满足条件。长度为L(L1)的全1子数组和是L积是1并不相等。这是一个非常重要的陷阱包含一个非1元素记为x子数组形式为 [1, 1, ..., 1, x, 1, ..., 1]。设左边有p个1右边有q个1。则和 p q x积 x。满足条件需 p q x x p q 0。这意味着p和q必须都为0即子数组就是 [x] 本身。所以任何单个非1元素x ≥ 2本身就是一个满足条件的子数组因为和与积都是x。包含两个非1元素且必须都是2子数组形式为 [1, ..., 1, 2, 1, ..., 1, 2, 1, ..., 1]。设两个2之间的1的个数为m第一个2左边的1的个数为p第二个2右边的1的个数为q。则总长度 L p m q 2。和 S p 2 m 2 q p m q 4。积 P 2 * 2 4。满足 S P即 p m q 4 4 p m q 0。这意味着 p, m, q 必须都为0。所以子数组只能是[2, 2]。综上所述满足“和等于积”的连续子数组只有三种可能单个元素[1]。单个元素[x](x ≥ 2)。两个元素[2, 2]。这个结论极大地简化了问题我们不需要再枚举所有 O(n²) 个子数组只需要在整个数组中扫描找出所有上述三种模式的子数组即可。时间复杂度瞬间降为 O(n)。2.2 处理零和负数的扩展思考上面的分析基于正整数。如果题目明确说明数组元素是正整数蓝桥杯很多题目默认如此那么结论完美适用。但如果题目没有明确或者数据包含非正整数我们需要进一步分析元素0任何包含0的子数组其乘积为0。要使和等于积0该子数组的和也必须为0。这意味着我们需要寻找和为0且包含0的子数组。这会变成一个“和为0的子数组”计数问题可以用前缀和配合哈希表在O(n)内解决但情况比正整数复杂。负数情况会变得非常复杂。因为负数的乘积可以正可负破坏了之前的单调性分析。通常蓝桥杯国赛题为了控制难度会约定数组元素为正整数。在实际做题时务必仔细阅读题目描述的数据范围我们接下来的实现基于“元素为正整数”的假设这也是最常见的情况。3. 算法设计与实现详解基于2.1得出的强力结论我们的算法变得异常清晰。整个算法流程可以描述为一次线性扫描识别并计数所有符合三种情况的连续子数组。3.1 算法步骤拆解初始化读取整数 n 和数组arr。设置答案变量ans 0。线性扫描遍历数组的每个元素arr[i](i从0到n-1)。情况1与2单个元素子数组[arr[i]]。如果arr[i] 1或arr[i] 2它都满足条件因为和与积都是它本身。所以每一个元素本身都构成一个合法子数组。因此我们可以直接让ans n。这是所有单个元素的情况。情况3双元素子数组[2, 2]。我们需要检查所有连续的两个元素[arr[i], arr[i1]]如果它们都等于2则找到一个合法子数组ans。输出结果遍历结束后输出ans。等等是不是太简单了这里有一个关键点情况1单个1和情况2单个x≥2我们已经通过ans n一并处理了。情况3需要单独检查相邻的2。时间复杂度O(n)一次遍历。空间复杂度O(1)仅使用常数个变量。3.2 C代码实现与逐行解析下面给出完整的C实现代码并附上详细注释。#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint arr(n); for (int i 0; i n; i) { cin arr[i]; } long long ans 0; // 使用long long防止答案过大溢出 // 情况1 2: 每个元素本身就是一个满足条件的子数组 // 对于任意正整数a子数组[a]的和与积都是a必然相等。 ans n; // 情况3: 检查所有相邻的 [2, 2] 子数组 for (int i 0; i n - 1; i) { if (arr[i] 2 arr[i 1] 2) { ans; } } cout ans endl; return 0; }代码关键点解析long long ans这是非常关键的一步。虽然n可能只有10^5但答案最大可能是n (n-1)≈ 2*10^5仍在int范围内。然而在竞赛中养成使用long long存储答案的习惯是很好的防御性编程避免因一时疏忽导致溢出。特别是当题目可能让你输出答案对某个大数取模的结果时中间计算过程更需要long long。ans n这行代码一举处理了前两种情况。它是基于我们推导出的数学结论。很多初学者可能会试图去遍历每个元素判断是否等于1或大于等于2但实际上没必要因为对于正整数数组每个元素都满足“自身和等于自身积”。循环条件i n - 1在遍历寻找[2,2]时我们访问arr[i1]所以要确保i1不越界。输入输出使用cin/cout在蓝桥杯竞赛中通常数据量不大使用cin/cout即可。如果担心效率可以关闭同步流ios::sync_with_stdio(false); cin.tie(nullptr);。但本题O(n)复杂度完全不必担心。3.3 测试与验证我们来构造几组测试数据验证算法的正确性。测试1基础案例输入 5 1 2 3 2 1单个元素子数组有5个 - [1], [2], [3], [2], [1]。[2,2]子数组没有连续的2。输出应为 5。 程序输出5。测试2包含连续2输入 6 1 2 2 1 2 2单个元素子数组6个。[2,2]子数组下标(1,2)和(4,5)两处。注意(2,3)是[2,1]不符合。输出应为 6 2 8。 程序输出8。测试3全1数组陷阱案例输入 4 1 1 1 1单个元素子数组4个 - 每个[1]都合法。[2,2]子数组0个。注意子数组[1,1]和为2积为1不合法。[1,1,1]等更长的也不合法。输出应为 4。 程序输出4。测试4大数和非2输入 3 100 500 1000单个元素子数组3个 - [100], [500], [1000] 都合法。[2,2]子数组0个。输出应为 3。 程序输出3。4. 从解题到举一反三连续子数组问题通用技巧虽然这道题因为特殊的数学性质有了极简的解法但它的思考过程极具教学意义。我们来总结一下处理“连续子数组”计数/判断类问题的通用武器库4.1 前缀和与哈希表用于“和为K”类问题这是最经典的组合。当需要快速求解“有多少连续子数组的和等于K”时前缀和预处理后问题转化为寻找有多少对(i, j)使得prefixSum[j] - prefixSum[i] K即prefixSum[j] prefixSum[i] K。在遍历过程中用一个哈希表unordered_map记录每个前缀和值出现的次数可以在O(n)时间内解决。// 示例和为K的子数组个数 int subarraySum(vectorint nums, int k) { unordered_mapint, int prefixSumCount; prefixSumCount[0] 1; // 初始状态前缀和为0出现1次 int currentSum 0, ans 0; for (int num : nums) { currentSum num; // 当前前缀和 // 如果存在一个之前的前缀和 currentSum - k则找到一个子数组 if (prefixSumCount.find(currentSum - k) ! prefixSumCount.end()) { ans prefixSumCount[currentSum - k]; } prefixSumCount[currentSum]; } return ans; }4.2 滑动窗口用于“满足某种单调条件”类问题当需要寻找“最大/最小的满足条件的连续子数组”时滑动窗口是利器。通常用于子数组和、乘积、不同字符数等问题。维护一个窗口[left, right]根据当前窗口状态动态移动left和right指针保证窗口内始终满足或不满足条件同时更新答案。// 示例乘积小于K的连续子数组个数 int numSubarrayProductLessThanK(vectorint nums, int k) { if (k 1) return 0; long long product 1; int left 0, ans 0; for (int right 0; right nums.size(); right) { product * nums[right]; while (product k) { // 窗口条件被破坏移动左指针 product / nums[left]; left; } // 以right结尾的满足条件的子数组个数为 (right - left 1) ans (right - left 1); } return ans; }4.3 贡献法用于“所有子数组的XX之和”类问题有时候问题不是求满足条件的子数组个数而是求所有子数组的某个属性如和、最大值、最小值的总和或某种运算结果。这时可以换个角度思考每个元素对最终答案的贡献是多少。例如“所有子数组的最大值之和”问题可以计算每个元素在多少个子数组中作为最大值出现。4.4 问题特性的深度挖掘本题的启示像“和与乘积”这道题一样很多题目看似需要复杂算法但其数据范围或问题本身可能隐藏着特殊的数学性质或限制例如本题中非1元素个数≤2。解题的第一步永远是仔细分析题目描述特别是数据范围。1 n 100000和1 a_i 100000这样的范围直接排除了 O(n²) 的暴力法提示你需要 O(n log n) 或 O(n) 的解法。然后尝试从小规模数据n1,2,3入手手动枚举寻找规律。大胆猜想小心验证。本题中通过枚举 n1,2,3 的情况很容易发现只有 [a], [2,2] 满足进而可以尝试证明。5. 常见误区与实战调试技巧即便知道了正确解法在实战编码和调试中依然可能踩坑。下面分享几个针对本题和类似问题的经验。5.1 本题专属陷阱误认为全1子数组都合法这是最大的思维陷阱。一定要亲手算一下[1,1]的和是2积是1不相等。只有单个的[1]才合法。忽略单个非1元素的合法性认为只有1和[2,2]合法忘记了[3], [4]等单个元素自身也合法。记住对于任何正整数a[a]的和与积都是a。数据类型溢出虽然本题答案不大但直接ans n时如果n是intans也是int没有问题。但养成使用long long的习惯至关重要。在计算前缀积等场景中溢出是常客。边界条件处理不周在扫描[2,2]时循环结束条件必须是i n-1否则arr[i1]会访问越界。5.2 蓝桥杯C编程实战技巧输入输出加速对于大量数据输入10^5使用scanf/printf或关闭同步流的cin/cout。ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 如果交互题可能需要使用全局数组或vector根据数据范围选择。如果n最大为10^5定义全局数组int arr[100010]或使用vectorint arr(n)都是可以的。Vector更安全方便。调试输出在本地调试时可以在关键步骤后输出中间变量值。提交前务必注释掉所有调试输出。测试用例设计自己设计几组极端数据最小输入n1元素1或2或100。最大输入n100000全1或全2或随机数。包含连续2的案例。所有元素都大于2的案例。使用freopen重定向输入输出在本地测试时将输入数据保存在in.txt使用freopen(“in.txt”, “r”, stdin);可以避免每次手动输入。5.3 思维定式破除遇到“连续子数组”问题不要立刻开始写前缀和二重循环。按照以下步骤思考暴力法是否可行估算时间复杂度。O(n³)和O(n²)对于大数据通常不可行。能否优化枚举引入前缀和/积、滑动窗口、二分查找等将复杂度降一维。问题是否有特殊性质像本题一样分析数学约束可能直接得到惊人结论。是否转化为已知模型例如子数组和问题转化为前缀和差问题再用哈希表优化。这道“和与乘积”题就像一位严格的教练它用看似简单的表象考核了你对问题本质的洞察力、数学推导能力以及将理论转化为简洁代码的实现力。掌握这种从暴力到优化、从表象到本质的思考链条比你多刷十道普通题更有价值。在竞赛和实际工作中这种能力才是区分优秀与平庸的关键。下次再看到“连续子数组”希望你脑海中能自动浮现出我们今天讨论的这套工具箱从容地选择最合适的那一把钥匙。