目录

AtCoder Beginner Contest 153 题解

这次的AtCoder明显变水了居然我都能AK。题目质量有所下降,好多板子啊(逃

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

今年的第一篇博客,要是肺炎来了怕不是就是最后一篇力(呸呸呸)。

A - Serval vs Monster

题意

给你\(H\)\(A\),问你多少个\(A\)\(H\)大。

做法

输出$\lceil \frac H A \rceil \(即可,可以转化为\)\lfloor \frac {H+A-1} A \rfloor\(,此处\)\lceil a \rceil\(和\)\lfloor a \rfloor\(分别代表对\)a$上取整和下取整。

程序

#include<bits/stdc++.h>
using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int h,a;
    cin>>h>>a;
    cout<<(h+a-1)/a<<endl;

    return 0;
}

B - Common Raccoon vs Monster

题意

给你\(H\)\(N\)\(N\)个数组成的数组\(A\),问你数组里的数都减一次能不能把\(H\)减到\(0\)及以下。

做法

判断数组所有元素的和是否大于等于\(H\)即可。

程序

#include<bits/stdc++.h>
using namespace std;

int h,n;
int a[100005];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>h>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        h-=a[i];
    }
    if(h>0){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }

    return 0;
}

C - Fennec vs Monster

C开始不解释题目意思了,大家肯定都看得懂(就是我懒)。

做法

贪心地找出HP最大的\(K\)个怪物先用技能打死,之后的只能平A了。

程序

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,k;
int h[200005];
ll ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>h[i];
    sort(h,h+n);
    for(int i=0;i<n-k;i++){
        ans+=h[i];
    }
    cout<<ans<<endl;

    return 0;
}

D - Caracal vs Monster

做法

定义一个操作是对场上当前的所有怪物都攻击一次。这样场上的怪物一直都是相同的血量,例如:

  • 开始有\(1\)只HP为\(4\)的怪物
  • 攻击\(1\)次后有\(2\)只HP为\(2\)的怪物
  • 攻击\(2\)次后有\(4\)只HP为\(1\)的怪物
  • 攻击\(4\)次后所有怪物死亡

总共\(7\)次攻击。

为什么呢?方便计算啊。只要记录场上怪物的HP和总数就好了。

之后做法显然

程序

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll h,cnt,ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>h;
    cnt=1;
    while(h){
        ans+=cnt;
        h>>=1;
        cnt<<=1;
        //>>和<<不是cincout操作符,是位运算的右移和左移,可自行查阅文档了解
        //也可替换成:
        //h/=2;
        //cnt*=2;
    }
    cout<<ans<<endl;

    return 0;
}

E - Crested Ibis vs Monster

做法

背包板子啊,AtCoder你变力。

直接DP上,定义dp[i][j]为计算完前i个咒语造成了j点伤害最少使用的MP量。那么状态转移方程是显然的:
\[ dp[i][j]=\min(dp[i-1][j],dp[i][j-a[i]]+b[i]) \]
好了,问题解决了,边界条件详见程序。

程序

#include<bits/stdc++.h>
using namespace std;

int h,n;
int a[1005],b[1005];
int dp[1005][20005];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>h>>n;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        for(int j=0;j<=h+10000;j++){//由于可能伤害不是正好杀死,一定要预留一点伤害的量
            if(j+a[i]<=h+10000)dp[i][j+a[i]]=min(dp[i][j+a[i]],dp[i][j]+b[i]);
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);//此处为计算方便我正着dp了
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=h;i<=h+10000;i++){
        ans=min(ans,dp[n][i]);
    }
    cout<<ans<<endl;

    return 0;
}

F - Silver Fox vs Monster

做法

首先,正常人都会选择把这些怪物们按坐标排个序。

然后,我们可以看出,对于每一个怪物\(A\),我们都可以找到一个它右边的怪物\(B\)\(A\)\(B\)可以被同一个炸弹炸到,但\(B\)右边的怪物不可以,这个可以用two pointers(中文是尺取法来着?)在\(O(N)\)时间里计算。可以看这篇博客了解。

我们就从左到右地循环怪物\(A\),每一次都炸很多次把它炸死。可以证明,此时炸弹位置在波及到\(A\)的情况下,越向右放越好,也就是波及了\(A\)\(B\)的所有怪物。这个用线段树维护每个怪物的血量就好了。又是板子,AtCoder出题人偷懒(

程序

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,d,a,sz;
ll data[800005];
ll lazy[800005];
pair<int,int> mon[200005];

void build(int bk,int l,int r){
    if(l==r){
        if(l<=n){
            data[bk]=mon[l].second;
        }
        return;
    }
    build(bk<<1,l,(l+r)>>1);
    build(bk<<1|1,((l+r)>>1)+1,r);
    data[bk]=data[bk<<1]+data[bk<<1|1];
}

void upd(int bk,int l,int r,int ql,int qr,ll val){
    if(qr<l||r<ql)return;
    if(ql<=l&&r<=qr){
        lazy[bk]+=val;
        data[bk]+=val*(r-l+1);
        return;
    }
    lazy[bk<<1]+=lazy[bk];
    data[bk<<1]+=lazy[bk]*((r-l+1)>>1);
    lazy[bk<<1|1]+=lazy[bk];
    data[bk<<1|1]+=lazy[bk]*((r-l+1)>>1);
    lazy[bk]=0;
    upd(bk<<1,l,(l+r)>>1,ql,qr,val);
    upd(bk<<1|1,((l+r)>>1)+1,r,ql,qr,val);
    data[bk]=data[bk<<1]+data[bk<<1|1];
}

ll qry(int bk,int l,int r,int ql,int qr){
    if(qr<l||r<ql)return 0;
    if(ql<=l&&r<=qr){
        return data[bk];
    }
    lazy[bk<<1]+=lazy[bk];
    data[bk<<1]+=lazy[bk]*((r-l+1)>>1);
    lazy[bk<<1|1]+=lazy[bk];
    data[bk<<1|1]+=lazy[bk]*((r-l+1)>>1);
    lazy[bk]=0;
    return qry(bk<<1,l,(l+r)>>1,ql,qr)+qry(bk<<1|1,((l+r)>>1)+1,r,ql,qr);
}

ll ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>d>>a;
    sz=1;while(sz<n)sz<<=1;
    for(int i=1;i<=n;i++){
        cin>>mon[i].first>>mon[i].second;
    }
    sort(mon+1,mon+1+n);//读入,对怪物排序
    build(1,1,sz);//建立线段树
    int l=1,r=1;
    while(l<=n){
        while(mon[r+1].first-mon[l].first<=d+d&&r<n){
            r++;
        }//尺取法
        ll lft=qry(1,1,sz,l,l);//cerr<<lft<<endl;
        if(lft<=0){//如果怪物死了就不计算了,我还因为这个wa了一次qaq
            l++;
            continue;
        }
        ll tms=(lft+a-1)/a;//杀掉这个怪物需要多少炸弹
        ans+=tms;
        upd(1,1,sz,l,r,(-tms)*a);//我也不知道为什么要加上括号qaq
        l++;
    }
    cout<<ans<<endl;

    return 0;
}

感谢

感谢阅读,我写得很烂您还读完了。太感谢了qaq

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄