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