Codeforces1141F_Same Sum Blocks

• 2019 年 10 月 22 日
• 筆記

题意

给定一个序列，求最多的不相交区间满足区间和相同。

分析

• 从暴力的角度想，是枚举区间再求和，反过来想，直接记录每个和对应是那些区间，然后排个序求最大不相交即可。

代码

#include <bits/stdc++.h>  using namespace std;  typedef long long ll;  const int N=1550;  int n;  ll a[N],p[N];  vector<pair<int,int>> ans,t;  map<ll,vector<pair<int,int>>> mp;  int main(){      scanf("%d",&n);      for(int i=1;i<=n;i++){          scanf("%lld",&a[i]);          p[i]=p[i-1]+a[i];      }      for(int l=1;l<=n;l++){          for(int r=l;r<=n;r++){              ll s=p[r]-p[l-1];              mp[s].push_back({r,l});          }      }      for(auto mx:mp){          auto v=mx.second;          int siz=v.size();          sort(v.begin(),v.end());          int tmp=0;          int lst=0;          for(int i=0;i<siz;i++){              if(v[i].second>lst){                  lst=v[i].first;                  tmp++;              }          }          if(tmp>ans.size()){              ans.clear();              lst=0;              for(int i=0;i<siz;i++){                  if(v[i].second>lst){                      lst=v[i].first;                      ans.push_back({v[i].second,v[i].first});                  }              }          }      }      int siz=ans.size();      printf("%dn",siz);      for(int i=0;i<siz;i++){          printf("%d %dn",ans[i].first,ans[i].second);      }      return 0;  }