思路
简单题。
不妨先预处理出每一个区间的 \(\sum\),然后离散化 \(\sum\),对于每个 \(\sum\) 开一个 \(\mathcal vector\) 记录所有区间的左右端点。
然后枚举每个 \(\sum\),求最多的区间,这是一个简单的贪心问题,可以用 \(\mathcal set\) 轻松完成。
代码
#include<bits/stdc++.h>
using namespace std;
int const N=3e6+10;
int a[N],lsh[N];
vector< pair<int,int> >qans,anss;
struct node{int l,r,val;}q[N];
vector< pair<int,int> >ins[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;cin>>n;int k=0;
for (int i=1;i<=n;++i) cin>>a[i];
for (int i=1;i<=n;++i){
int res=0;
for (int j=i;j<=n;++j){
res+=a[j];lsh[++k]=res;
q[k]={i,j,res};
}
}
sort(lsh+1,lsh+k+1);int l=unique(lsh+1,lsh+k+1)-lsh-1;
for (int i=1;i<=k;++i) ins[lower_bound(lsh+1,lsh+l+1,q[i].val)-lsh].push_back({q[i].l,q[i].r});
for (int i=1;i<=l;++i) sort(ins[i].begin(),ins[i].end());
for (int i=1;i<=l;++i){
int len=(int)ins[i].size(),l=0;
set< pair<int,int> >s;
for (int j=0;j<len;++j) s.insert({ins[i][j].second,ins[i][j].first});
int res=0;qans.clear();
while (s.size()){
while (s.size() && (*s.begin()).second<=l) s.erase(s.begin());
if (!s.size()) break;
l=(*s.begin()).first;
qans.push_back({(*s.begin()).second,(*s.begin()).first});
s.erase(s.begin());
}
if (qans.size()>anss.size()) anss=qans;
}
cout<<(int)anss.size()<<'\n';
for (auto i:anss) cout<<i.first<<' '<<i.second<<'\n';
return 0;
}
标签:CF1141F2,Sum,Hard,Same,int,vector,sum
From: https://www.cnblogs.com/tx-lcy/p/16851409.html