F2. Same Sum Blocks (Hard) - 题解

比赛与标签

比赛: Codeforces Round 547 (Div. 3) 标签: data structures, greedy, *1900 难度: *1900

题目大意喵~

主人，这道题是这样子的：给你一个整数数组 a，你的任务是找到尽可能多的不相交的连续子数组（也就是“块”），并且所有这些块的元素之和都必须相等的说。

简单来说，就是要找一个和为 S 的值，使得数组中能找到最多的、互不重叠的、和都为 S 的子数组。最后，你需要输出最多能找到多少个这样的块，以及每个块的起始和结束位置（下标从1开始哦）。

举个栗子，如果数组是 [4, 1, 2, 2, 1, 5, 3]，我们可以找到三个和都为 3 的块：[3] (在位置7)，[1, 2] (在位置2-3)，和 [2, 1] (在位置4-5)。它们互不重叠，所以答案就是3个块啦！

解题思路呐~

看到这道题，小猫娘的直觉告诉咱，既然要求所有块的和都相同，那这个“和”一定是一个非常关键的突破口！如果我们能把所有和相同的块都找出来，问题是不是就简单多啦？

所以，我们的思路可以分成几个清晰的步骤，喵~

第一步：暴力枚举所有可能的块和它们的和

首先，我们得知道数组里到底能凑出哪些和，以及每个和对应了哪些块。一个很自然的想法就是，枚举所有可能的子数组（块）。我们可以用两个循环，一个定左端点 l，一个定右端点 r，这样就能找到所有的块 a[l...r]。

但是，每次都重新计算 a[l...r] 的和太慢啦，复杂度会飙到 O(n³)，肯定会超时的说！这里有个超级好用的技巧——前缀和！

我们可以先预处理一个 prefix 数组，prefix[i] 表示原数组前 i 个元素的和。这样一来，任何子数组 a[l...r] (0-indexed) 的和都可以用 prefix[r+1] - prefix[l] 在 O(1) 的时间内算出来！通过这种方式，我们可以在 O(n²) 的时间内枚举出所有子数组和它们各自的和。

第二步：用哈希表将块按和分组

现在我们有了所有子数组和它们的和，下一步就是把和相同的子数组放在一起。用什么数据结构好呢？当然是 std::unordered_map (哈希表) 啦！

我们可以创建一个 unordered_map<long long, vector<pair<int, int>>> sumMap。

key (键) 就是子数组的和。
value (值) 是一个 vector，里面装着所有和为这个 key 的子数组的 (左端点, 右端点) 对。

我们遍历所有 O(n²) 个子数组，把它们一个个塞进这个 sumMap 里。这样，我们就成功地把问题转化成了：对于 sumMap 中的每一个 sum，找出它对应的那一堆块中，最多能选出多少个互不重叠的块。

第三步：对每个和，求解最大不相交区间数

对于一个固定的和 S，我们现在有一堆区间（块）[(l_1, r_1), (l_2, r_2), ...]。我们的目标是从中选出最多的区间，使得它们两两不相交。

这不就是经典的 区间调度问题 (Interval Scheduling Problem) 嘛！解决这个问题有一个非常经典的贪心策略：

将所有区间按照右端点 r 从小到大排序。
初始化一个变量 last_r = 0，表示上一个选定区间的右端点。
遍历排序后的区间 (l, r)：
- 如果当前区间的左端点 l 大于 last_r，说明这个区间和之前选的区间不重叠！太棒了，我们就选择它！
- 然后，更新 last_r = r，并继续向后寻找下一个符合条件的区间。

通过这个贪心策略，我们就能为每个 sum 值找到对应的最大不相交块数。

第四步：找到全局最优解

最后一步就很简单啦！我们对 sumMap 中的每一个 sum 都执行一次第三步的贪心算法，记录下每次得到的块的数量和块的列表。然后，我们只需要比较所有 sum 值得到的结果，找出那个能选出最多块的方案，就是我们的最终答案啦！

总结一下整个流程：

计算前缀和。
O(n²) 枚举所有子数组，用哈希表按和分组。
遍历哈希表中的每个和。
对每个和对应的区间列表，用贪心算法（按右端点排序）找出最大不相交子集。
在所有和的结果中，取块数最多的那个作为答案输出。

是不是感觉思路清晰多啦？喵~ 让我们看看代码是怎么实现的吧！

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    // 读取数组长度 n
    int n;
    cin >> n;
    
    // 读取数组元素
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 步骤一：计算前缀和数组，方便 O(1) 查询区间和
    // prefix[i] 存储 a[0]...a[i-1] 的和
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }

    // 步骤二：用哈希表按和分组
    // key 是和，value 是所有和为 key 的区间的 (左端点, 右端点) 列表
    unordered_map<long long, vector<pair<int, int>>> sumMap;
    
    // O(n^2) 枚举所有可能的子数组
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // 使用前缀和计算区间 a[i...j] 的和
            long long s = prefix[j + 1] - prefix[i];
            // 将区间 (i+1, j+1) (1-based index) 存入对应和的列表中
            sumMap[s].push_back(make_pair(i + 1, j + 1));
        }
    }

    int best_count = 0; // 记录全局最优解的块数
    vector<pair<int, int>> best_blocks; // 记录全局最优解的块列表

    // 步骤三 & 四：遍历每个和，用贪心算法求解，并找到全局最优解
    for (auto& p : sumMap) {
        auto& intervals = p.second; // 当前和对应的所有区间

        // 贪心策略第一步：按区间的右端点从小到大排序
        sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second < b.second;
        });

        vector<pair<int, int>> selected; // 存储当前和选出的不相交区间
        int last = 0; // 记录上一个选中区间的右端点

        // 贪心策略第二步：遍历排序后的区间，选择不重叠的
        for (auto& inter : intervals) {
            int l = inter.first;
            int r = inter.second;
            // 如果当前区间的左端点 > 上一个选中区间的右端点，说明不重叠
            if (l > last) {
                selected.push_back(inter); // 选中这个区间
                last = r; // 更新 last 为当前区间的右端点
            }
        }
        
        // 如果当前和能选出的块比已知的最优解还多，就更新最优解
        if (selected.size() > best_count) {
            best_count = selected.size();
            best_blocks = selected;
        }
    }

    // 输出最终答案
    cout << best_count << endl;
    for (auto& block : best_blocks) {
        cout << block.first << " " << block.second << endl;
    }

    return 0;
}

复杂度分析

时间复杂度: O(n² * log(n)) 的说
- 计算前缀和是 O(n)。
- 枚举所有子数组并存入哈希表是 O(n²)。
- 遍历哈希表中的每个和：
  - 对每个和的区间列表进行排序是主要开销。所有区间的总数是 O(n²)。在最坏的情况下，所有 O(n²) 个区间都可能有相同的和，此时排序需要 O(n² * log(n²)) = O(n² * log(n)) 的时间。
  - 贪心选择部分对每个和的区间列表只遍历一遍，总共是 O(n²)。
- 因此，总的时间复杂度由排序主导，为 O(n² * log(n))。对于 n=1500 来说，这个复杂度是可以通过的！
空间复杂度: O(n²) 的说
- prefix 数组需要 O(n) 的空间。
- sumMap 是空间消耗大户。在最坏情况下，我们需要存储 O(n²) 个区间的信息，所以空间复杂度是 O(n²)。

知识点与总结

这道题真是一次愉快的挑战呢！它完美地融合了多种算法思想，让小猫娘学到了很多~

前缀和: 解决子数组和问题的万能钥匙！一定要熟练掌握喵~
哈希表 (unordered_map): 当需要根据某个属性（比如“和”）对事物进行分组时，哈希表是你的不二之选。它能帮你快速地将复杂问题分解。
贪心算法: 本题的核心是识别出区间调度模型，并应用其经典的贪心解法（按结束时间排序）。记住这个模型，以后遇到类似“选择不冲突的活动”问题就能迎刃而解啦！
问题分解: 将一个看似复杂的问题（找和相同且不相交的最多块）分解成“枚举所有和” -> “对每个和，找最大不相交子集”，是解题的关键思路。

希望这篇题解能帮到正在努力的你！算法之路充满乐趣，只要我们一步一个脚印，就一定能不断进步的！加油喵~ >w<

F2. Same Sum Blocks (Hard) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路呐~ ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​