题解：CF1141F2 Same Sum Blocks (Hard)

Austin0116 · 2025-05-10 16:09:05 · 题解

分析

首先，我们可以发现 n \le 1500，O(n^2) 左右时间复杂度完全可过。

我们可以先预处理出所有区间的和，然后对每个和处理出区间和等于它的区间 [l,r]。然后就可以转化为经典的线段覆盖问题，最后处理出最多的区间即为答案。时间复杂度为 O(n^2 \log n)。

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[1505],sum[1505],l,r,s,summ;
struct ha{
    int x,l,r;
    inline bool operator < (const ha &o) const{//排序
        if(x!=o.x) return x<o.x;
        if(r!=o.r) return r<o.r;
        return l<o.l;
    }
};
vector<ha> b; 
vector<pair<int,int>> c,d;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int l=1;l<=n;l++) for(int r=l;r<=n;r++) b.push_back(ha{sum[r]-sum[l-1],l,r});//处理出各个区间和
    sort(b.begin(),b.end());
    for(int i=0;i<(int)b.size();i++){
        if(!i) l=i;
        else if(b[i].x!=b[i-1].x){
            r=i-1;
            s=summ=0;
            c.clear();
            for(int j=l;j<=r;j++) if(s<b[j].l){//处理线段覆盖问题
                summ++;
                s=b[j].r;
                c.push_back({b[j].l,b[j].r});
            } 
            l=i;
            if(summ>(int)d.size()){
                d.clear();
                for(pair<int,int> x:c) d.push_back(x);
            }
        }
    }
    r=(int)b.size()-1;
    s=summ=0;
    c.clear();
    for(int j=l;j<=r;j++) if(s<b[j].l){
        summ++;
        s=b[j].r;
        c.push_back({b[j].l,b[j].r});
    } 
    if(summ>(int)d.size()){
        d.clear();
        for(pair<int,int> x:c) d.push_back(x);
    }
    printf("%d\n",(int)d.size());
    for(pair<int,int> x:d) printf("%d %d\n",x.first,x.second);
    return 0;
}