---
# System prepended metadata

title: Codeforce 1141 F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)

---

---
title: Codeforce 1141 F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)
description: "Codeforce 1141 F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1141 F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)">
<!-- toc -->

# Codeforce 1141 F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)
今天我們來看看CF1141F2(Hard)
[題目連結](https://codeforces.com/problemset/problem/1141/F2)

> **題目**
給你一個數列$a$，要你從中找出若干個數字和一樣的disjoint的連續區段，輸出最多的段數和是哪些段。

### 前言
一開始還是陷入和以前一樣的誤區，總感覺如果暴力把所有可能都找出來要$O(2^n)$，但其實因為區段是連續的，所以全部找出來只要$O(n^2)$
![](https://i.imgur.com/09nvm0Y.jpg)

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
暴力把所有區段找出來，並且以區段和的值當作Key存在map裡，因為區段是連續的，所以全部找出來只要$O(n^2)$。
當然，直接全部找很有可能區段會重疊，但其實只要稍微思考一下，如果我們從$1$開始枚舉區段的結束位置，並且慢慢從長度$1$到長度$i$($i$是區段結束的位置)的區段考慮，如果發現同樣的$sum$(區段和)在前面已經有出現過了，那就檢查之前那個區段是否和目前檢查的有重和，沒重和才會加進map裡。
我們這樣做能成功的原因是:如果想要找到最多區段，那麼只要區段和是$sum$，我們都會選「**占用最少有潛能的格子**」的區段，回到上面所說的找法，如果我發現我目前所看的區段和前面的重合了，如果我硬是把前面已經找到的區段刪掉了，那麼區段和為$sum$的區段少一個又多一個，完全沒好處，並且很有可能有結束得比目前區段後面的區段的和會是$sum$，因此我們可以用這種貪心的做法。

### 程式碼:
```cpp=
const int _n=1510;
int t,n,a[_n],pre[_n];
struct B{int st,ed;};
map<int,vector<B>> mp;
vector<B> tmp;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;rep(i,1,n+1)cin>>a[i];rep(i,1,n+1)pre[i]=pre[i-1]+a[i];
  rep(i,1,n+1)per(j,0,i){
    int sum=pre[i]-pre[j];
    if(!mp.count(sum)){
      tmp.clear();tmp.pb({j+1,i});
      mp[sum]=tmp;
      continue;
    }
    if(mp[sum].back().ed<=j)mp[sum].pb({j+1,i});
  }
  PII maxx={0,0};for(auto it=mp.begin();it!=mp.end();it++){
    if(SZ(it->se)>maxx.fi)maxx.fi=SZ(it->se),maxx.se=it->fi;
  }cout<<maxx.fi<<'\n';
  rep(i,0,maxx.fi)cout<<mp[maxx.se][i].st<<' '<<mp[maxx.se][i].ed<<'\n';
  return 0;
}
```
標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/1141/submission/91192683)