凉肝的比赛
2020-01-18 16:00:44来源:博客园 阅读 ()
凉肝的比赛
对于这场比赛,我真的是有点划水了,做了俩题,做第三题的时候实在是不知道什么地方卡住了,然后我家来了客人,被带出去吃饭去了,ε=(´ο`*)))唉!!!
B - Just Eat It!
这道题是个经典的DP题,我对于递推还不是特别熟悉,得找到题目的状态转移方程。
B[ i ] = max{ A[ i ] , B[ i - 1] + A[ i ] };
令B[ i ]表示以A[ i ]作为末尾的连续序列的最大和,通过设置一个B数组,数组最大连续子序列和其实就是B数组里的最大值,还有就是找到的最大值有可能也是所有的总和,所以先设置一个数,让它统计已经连续了多少,对于这种情况进行排除,然后对先前求出的总和进行比较,就能得到答案。
(这个方法我是从算法笔记上看到的,还有太多没看了...)
#include<bits/stdc++.h> using namespace std; const int xa=2e5+5; long long a[xa],b[xa]; int main() { int t; cin>>t; long long n; long long sum; long long shu; bool pan; while(t--){ cin>>n; sum=0; shu=0; pan=false; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } b[0]=a[0]; for(int i=1;i<n-1;i++){ if(a[i]<=b[i-1]+a[i]){ b[i]=b[i-1]+a[i]; shu++; }else{ b[i]=a[i]; shu=0; } } if(shu==n){ pan=true; } int k=0; for(int i=1;i<n;i++){ if(b[i]>b[k]){ k=i; } } if(b[k]>=sum&&!pan){ cout<<"NO"<<endl; }else{ cout<<"YES"<<endl; } } }
E - Deadline
这题看起来挺简单的,但是这个数学问题的解法比赛的时候我是怎么都没想到,比赛的时候也是匆匆看了一眼就去看B题去了。
听大佬们说这个题是均值不等式
由题意得,n>=x+[d/(x+1)]=x+1[d/(x+1)]-1>=2sqrt(d)-1;
所以就解出来了 ~。~
呜呜呜~~
#include<bits/stdc++.h> using namespace std; int t; long long n,d; int main(){ cin>>t; while(t--){ cin>>n>>d; if((n+1)*(n+1)/4>=d) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
原文链接:https://www.cnblogs.com/yclW/p/12207720.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:寒假集训第一天---并查集题解
下一篇:BFS和队列
- 朋友(翻转树边权值比赛)——依然是思维 2020-04-12
- X Round 2(毒瘤比赛qwq) 2019-08-16
- vs2013下配置x64版c++ 2019-04-18
- debug?用对拍! 2018-07-22
- 第八届蓝桥杯参赛心得 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash