CodeforcesRound#278(Div.1)解题报告_html/css

来源：懂视网责编：小采时间：2020-11-27 15:59:00

CodeforcesRound#278(Div.1)解题报告_html/css

CodeforcesRound#278(Div.1)解题报告_html/css_WEB-ITnose:A题：Fight the Monster 枚举+二分因为每个元素的数据范围只有100，所以可以用枚举，对于血量用二分，然后判断结果是否可行。代码如下： #include #include #include #include #include #include #include #include #in

推荐度：

点击下载本文 文档为doc格式

导读CodeforcesRound#278(Div.1)解题报告_html/css_WEB-ITnose:A题：Fight the Monster 枚举+二分因为每个元素的数据范围只有100，所以可以用枚举，对于血量用二分，然后判断结果是否可行。代码如下： #include #include #include #include #include #include #include #include #in

A题：Fight the Monster

枚举+二分

因为每个元素的数据范围只有100，所以可以用枚举，对于血量用二分，然后判断结果是否可行。

代码如下：

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int hy, ay, dy, hm, am, dm;int bin_search(int a, int d){ if(d>=am) return hy; int low=0, high=100000, mid, ans, c; c=(hm+(a-dm-1))/(a-dm); while(low<=high){ mid=low+high>>1; if((mid+am-d-1)/(am-d)>c) { ans=mid; high=mid-1; } else low=mid+1; } return ans>hy?ans:hy;}int main(){ int h, a, d, i, j, min1, z; while(scanf("%d%d%d",&hy,&ay,&dy)!=EOF) { min1=INF; scanf("%d%d%d",&hm,&am,&dm); scanf("%d%d%d",&h,&a,&d); for(i=0;i<=200;i++){ for(j=0;j<=200;j++){ if(ay+i<=dm)continue ; z=bin_search(ay+i,dy+j); min1=min(min1,(z-hy)*h+i*a+j*d); } } printf("%d\n",min1); }}

B题： Strip

线段树+DP+二分（或窗口滑动）

这题做了好长时间。。终于AC了。

基本思路是DP。DP[i]表示从第一个到第i个的最小可划分的区间数。然后对于每个数，找到前面可到达的最左端L，对于L的查找可用二分法或者滑动窗口法进行枚举查找，判断当前枚举区间是否可行的时候用线段树对当前区间的最值进行查询。状态转移方程dp[i]=min(dp[L],....,dp[i-lenth])+1；然后对于dp[L]...dp[i-lenth]这段区间查最值可用另一棵线段树在logn的时间内查询。所以需要建两棵线段树。

话说最近换了代码风格。看起来果然比以前的好看多了。。

代码如下：

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64const int INF=0x3f3f3f3f;#define lson l, mid, rt<<1#define rson mid+1, r, rt<<1|1#define root 0, n, 1int minv[400000], maxv[400000], a[110000], q_minv, q_maxv, mindp[400000], q_mindp, s, n;void PushUp(int q, int rt){ if(q==1) { minv[rt]=min(minv[rt<<1],minv[rt<<1|1]); maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]); } else mindp[rt]=min(mindp[rt<<1],mindp[rt<<1|1]);}void Update(int q, int p, int x, int l, int r, int rt){ if(l==r) { if(q==1) minv[rt]=maxv[rt]=x; else mindp[rt]=x; return ; } int mid=l+r>>1; if(p<=mid) Update(q,p,x,lson); else Update(q,p,x,rson); PushUp(q,rt);}void Query(int q, int ll, int rr, int l, int r, int rt){ if(ll<=l&&rr>=r) { if(q==1) { q_minv=min(q_minv,minv[rt]); q_maxv=max(q_maxv,maxv[rt]); } else q_mindp=min(q_mindp,mindp[rt]); return ; } int mid=l+r>>1; if(ll<=mid) Query(q,ll,rr,lson); if(rr>mid) Query(q,ll,rr,rson);}int bin_search(int r){ int low=1, high=r, mid, ans=-1; while(low<=high){ mid=low+high>>1; q_maxv=-INF; q_minv=INF; Query(1,mid,r,root); //if(r==4) //printf("%d %d\n",q_minv,q_maxv); if(q_maxv-q_minv<=s) { ans=mid;high=mid-1; } else low=mid+1; } return ans;}int main(){ int lenth, ans, flag=0, l, i; scanf("%d%d%d",&n,&s,&lenth); for(i=1; i<=n; i++) { scanf("%d",&a[i]); } memset(minv,INF,sizeof(minv)); memset(maxv,-1,sizeof(maxv)); memset(mindp,INF,sizeof(mindp)); Update(-1,0,0,root); for(i=1;i<=n;i++){ Update(1,i,a[i],root); l=bin_search(i); if(l+lenth-1>i) continue ; q_mindp=INF; //printf("%d %d\n",l,i-lenth); Query(-1,l-1,i-lenth,root); if(q_mindp==INF) continue ; Update(-1,i,q_mindp+1,root); } q_mindp=INF; Query(-1,n,n,root); printf("%d\n",q_mindp==INF?-1:q_mindp); return 0;}

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

CodeforcesRound#278(Div.1)解题报告_html/css

推荐度：

点击下载本文 文档为doc格式

标签： )( div round

热门焦点

CodeforcesRound#278(Div.1)解题报告_html/css

CodeforcesRound#278(Div.1)解题报告_html/css

CodeforcesRound#278(Div.1)解题报告_html/css

最新推荐

猜你喜欢

热门推荐