F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)
2024-10-10 09:45:01
Codeforce 1141 F2. Same Sum Blocks (Hard) 解析(思維、前綴和、貪心)
今天我們來看看CF1141F2(Hard)
題目連結
題目
給你一個數列\(a\),要你從中找出若干個數字和一樣的disjoint的連續區段,輸出最多的段數和是哪些段。
前言
一開始還是陷入和以前一樣的誤區,總感覺如果暴力把所有可能都找出來要\(O(2^n)\),但其實因為區段是連續的,所以全部找出來只要\(O(n^2)\)
想法
暴力把所有區段找出來,並且以區段和的值當作Key存在map裡,因為區段是連續的,所以全部找出來只要\(O(n^2)\)。
當然,直接全部找很有可能區段會重疊,但其實只要稍微思考一下,如果我們從\(1\)開始枚舉區段的結束位置,並且慢慢從長度\(1\)到長度\(i\)(\(i\)是區段結束的位置)的區段考慮,如果發現同樣的\(sum\)(區段和)在前面已經有出現過了,那就檢查之前那個區段是否和目前檢查的有重和,沒重和才會加進map裡。
我們這樣做能成功的原因是:如果想要找到最多區段,那麼只要區段和是\(sum\),我們都會選「占用最少有潛能的格子」的區段,回到上面所說的找法,如果我發現我目前所看的區段和前面的重合了,如果我硬是把前面已經找到的區段刪掉了,那麼區段和為\(sum\)的區段少一個又多一個,完全沒好處,並且很有可能有結束得比目前區段後面的區段的和會是\(sum\),因此我們可以用這種貪心的做法。
程式碼:
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
最新文章
- (转载)html中table的使用方法
- Lua游戏时区问题
- jQuery的动画处理总结
- Web 开发最有用的50款 jQuery 插件集锦——《综合篇》
- BZOJ 3999 旅游
- SQL事务隔离级别
- HTML网页中添加音频视频动画...(转)
- 记一次调试串口设备Bug的经历
- 编写高质量代码—javascript的分层—base层
- fiddler2请求参数乱码
- Python 实现 Html 转 Markdown(支持 MathJax 数学公式)
- SpringBoot四大核心
- windows生成库文件
- c语言——单链表分拆——头插法创建链表,尾插法生成链表
- 敏感词汇过滤DFA算法
- Git Gerrit Code Review
- ZooKeeper注册中心安装详细步骤(单节点)
- Word Embedding与Word2Vec
- 反转ListBox的ListBoxItem(控件级别,不是数据的反转)
- w10下Oracle 11g完全干净卸载