CF1141F2 Same Sum Blocks (Hard) 题解

题目链接：CF1141F2 Same Sum Blocks (Hard)

题意：

这个问题有两个版本，它们唯一的不同之处在于对数值 \(n\) 的约束。

给定一个整数数组 \(a_1,a_2,\ldots,a_n\)。一个块是由连续的元素 \(a_l, a_{l+1}, \ldots, a_r\) （\(1 \leq l \leq r \leq n\)）构成的序列。因此，一个块由一对索引 \((l, r)\) 定义。

找到一组块 \((l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)\)，使得：

1. 它们不相交（即它们是不相交的）。形式化地，对于每对块 \((l_i, r_i)\) 和 \((l_j, r_j)\)（其中 \(i \neq j\)）要么 \(r_i < l_j\)，要么 \(r_j < l_i\)。
2. 对于每个块，其元素的总和相等。形式化地，\(a_{l_1} + a_{l_1+1} + \ldots + a_{r_1} = a_{l_2} + a_{l_2+1} + \ldots + a_{r_2} = \ldots = a_{l_k} + a_{l_k+1} + \ldots + a_{r_k}\)。
3. 块集合中的块数是最大的。形式化地，不存在满足上述两个条件且 \(k' > k\) 的块集合 \(\left(l_1^{\prime}, r_1^{\prime}\right),\left(l_2^{\prime}, r_2^{\prime}\right), \ldots,\left(l_{k^{\prime}}^{\prime}, r_{k^{\prime}}^{\prime}\right)\)。

因为题目描述里没有萌妹纸 cxy ，所以她生气地把这道题扔给了你。

输入格式：

第一行包含整数 \(n\)（\(1 \leq n \leq 50\)）——给定数组的长度。

第二行包含元素序列 \(a_1, a_2, \ldots, a_n\)（\(-10^5 \leq a_i \leq 10^5\)）。

输出格式：

在第一行中打印整数 \(k\)（\(1 \leq k \leq n\)）。接下来的 \(k\) 行应该包含块，每行打印一对索引 \(l_i, r_i\)（\(1 \leq l_i \leq r_i \leq n\)）——第 \(i\) 个块的边界。您可以以任何顺序打印块。如果存在多个答案，则打印任何一个。

注意到 \(n\) 很小（easy version 就更小了）

因此我们可以暴力统计每个区间的和，然后把和相同的区间放到一块。接着就是无脑贪心选了。

这道题的难点在于代码，我是按着官方题解写的，不得不说有很多细节的东西

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1515))

int n,a[N];
map<int,vector<pii>> mp; vector<pii> best;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int r = 1; r <= n; r++) {
        for(int l = r, sum = 0; ~l; l--) {
            sum += a[l]; mp[sum].emplace_back(l,r);
        }
    }
    int res = 0;
    for(auto &i : mp)
    {
        vector<pii> &vec = i.second;
        int cur = 0, r = 0; vector<pii> now;
        for(pii &j : vec) if(j.first > r) {
            ++cur; now.push_back(j); r = j.second;
        }
        if(cur > res) { res = cur; best = now; }
    }
    cout << res << '\n';
    for(pii &i : best) cout << i.first << ' ' << i.second << '\n';
    return 0;
}

---

参考文献：

[1] https://codeforces.com/blog/entry/66062