【Codeforces Round #547 (Div. 3) F1.F2. Same Sum Blocks 】贪心+区间覆盖问题

F1.F2. Same Sum Blocks

题意

给你一个长度为n的数组，找出尽量多的不相交的区间并且他们的区间和相等。

$1\le n\le 1500$

做法

由于$n=1500$，区间和只有$1500\times 1500$ 种，所以我们这些区间和作为最终的答案，对于每种区间和可以得到很个区间，对于每种区间和的问题就转化为给你n个区间找出最多的不相交区间的问题，这个问题按照r排序之后贪心的从左到右选即可，之后对每种区间和的答案取$max$，这道题就做完了。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<unordered_map>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 1e6+5;
#define pb push_back
#define Se second
#define Fi first
int a[maxn];
vector<pii> anss;
vector<pii>tmp;
map<int,int> r;
unordered_map<int,vector<pii>>  mp;
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) a[i]=a[i-1]+a[i];int ans=1;anss.push_back(pii(1,1));vector<int> rr;for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
    int tmp=a[i]-a[j-1];if(r.find(tmp)==r.end()||r[tmp]<j){
    mp[tmp].pb(pii(j,i));r[tmp]=i;}}}for(unordered_map<int,vector<pii> >::iterator it=mp.begin();it!=mp.end();++it){
    if((*it).Se.size()>ans){
    ans=(*it).Se.size();anss=(*it).Se;}}printf("%d\n",ans);for(int i=0;i<ans;i++) printf("%d %d\n",anss[i].Fi,anss[i].Se);return 0;
}