题目链接: [https://codeforces.com/contest/1141/problem/F2]

题解:很巧妙的一道题,不妨我们枚举出所有的区间,然后用map来处理区间和为kk的所有[l,r][l, r] ,对于所有的kk我们可以将用贪心的思想来求最多不相交区间即可

最多不相交区间:贪心的取,排序以rr为第一优先级,ll为第二优先级,将rr从小到大,并且当rr相等时,ll为从大到小。

为何可行 ? 因为我们是从11开始取到nn 也就是说我们要尽量使得rr尽量的小来保证后面的线段能取到的尽量多。

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1500 + 5;
int a[N],sum[N],cnt;
int n;
struct node {
    int l,r;
};
vector<node> b[N * N];
vector<node> res[N * N];
map<int, int> f;
bool cmp(node a, node b) {
    if(a.r == b.r) return a.l > b.l;
    else return a.r < b.r;
}
int cal(int x) {
    sort(b[x].begin(), b[x].end(), cmp);
    int ans = 0, last = -INF;
    for(int i = 0; i < b[x].size(); i++) {
        if(b[x][i].l > last) {
            res[x].push_back(b[x][i]);
            last = b[x][i].r;
            ans++;
        }
    }
    return ans;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            if(!f[sum[i] - sum[j]]) {
                f[sum[i] - sum[j]] = ++cnt;
                //cout << sum[i] - sum[j] << "\n";
            }
            b[f[sum[i] - sum[j]]].push_back((node) {j + 1, i});
        }
    }
    int ans = 0, p;
    for(int i = 1; i <= cnt; i++) {
       /* for(int j = 0; j < b[i].size(); j++) {
            cout << b[i][j].l << " " << b[i][j].r << endl;
        }
        cout << "\n";*/
        int t = cal(i);
        if(t > ans) {
            ans = t;
            p = i;
        }
    }
    cout << ans << "\n";
    for(int i = 0; i < res[p].size(); i++) {
        cout << res[p][i].l << " " << res[p][i].r << "\n";
    }
    return 0;
}