Codeforces Round #278 (Div. 1) 解题报告 A.B.

2024-08-24 21:32

本文主要是介绍Codeforces Round #278 (Div. 1) 解题报告 A.B.,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A题:Fight the Monster

枚举+二分

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

代码如下:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL __int64
const 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;}elselow=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 <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define root 0, n, 1
int 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]);} elsemindp[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]);} elseq_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;
}


这篇关于Codeforces Round #278 (Div. 1) 解题报告 A.B.的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103655

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor