AtCoder Beginner Contest 153 题解


A. Serval vs Monster

签到题

int a,b;
int main()
{
    cin>>a>>b;
    cout<<ceil((double)a/(double)b)<<endl;
    return 0;
}

B. Common Raccoon vs Monster

签到+1

int a,n,sum;
int main()
{
    cin>>a>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        sum+=x;
    }
    if(sum>=a) puts("Yes");
    else puts("No");
    return 0;
}

C. Fennec vs Monster

签到+2

int n,k;
int a[maxn];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+n+1);
    if(k>=n) puts("0");
    else
    {
        ll sum=0;
        for(int i=1;i<=n-k;i++) sum+=a[i];
        cout<<sum<<endl;
    }
    return 0;
}

D. Caracal vs Monster

题意简述

一个怪物有$n$点血量,假如血量为$0$死亡,假如怪物血量为$1$攻击一次直接死亡,否则会分裂为两个怪物血量都为$\lfloor \frac{n}{2}\rfloor$,问至少多少次能将怪物全杀死

题解

其实就是一个递归树,每一层都是上一层的一半,只要找到比$n$小的最大的$2^x$,答案就是递归树求和为$2^{x+1}-1$

AC代码

ll n;
int main()
{
    cin>>n;
    ll x=1,i=0;
    while(x<=n) 
    {
        i++;
        x=(1ll<<i);
    }
    i--;
    cout<<(1ll<<(i+1))-1<<endl;
    return 0;
}

E. Crested Ibis vs Monster

题意简述

一个怪物有$H$点血量,假如血量小于等于$0$死亡,勇士有$n$种攻击方式,每种方式产生$A_i$的攻击(每种攻击可以使用任意次),会消耗$B_i$的力量,请问至少消耗多少力量能让怪物死亡

题解

完全背包的变形,总体积看起来不确定,不过我们可以分析一下,设所有攻击方式中最耗体力的值为$maxx$,那么背包体积为$H+maxx$即可,因为再插入显然会比原来更多,所以这是最大的可能的情况,然后跑一个完全背包即可

AC代码

const int maxn=1050;
const int maxm=20000010;
int h,n,v[maxn],w[maxn],f[maxm],maxx;
int main()
{
    cin>>h>>n;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i],maxx=max(v[i],maxx);
    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=h+maxx;j++)
            f[j]=min(f[j],f[j-v[i]]+w[i]);    
    }
    int ans=inf;
    for(int i=h;i<=h+maxx;i++) ans=min(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}

F. Silver Fox vs Monster

题意简述

有$n$个怪物,每个怪物的坐标为$X_i$,血量为$H_i$,在$X$处施展一次攻击会对$X-d$到$X+d$的左边产生$A$的攻击,怪物血量小于等于$0$死亡,求至少攻击多少次所有怪物都能死亡

题解

这是一个贪心题,一开始可能无从下手,不妨先排序一下,首先攻击的顺序肯定是不重要的,而最左边的点假如要被消灭的话一定会被攻击$\lfloor \frac{H_i+A-1}{A} \rfloor$次,把攻击的血量累计到总伤害,然后后面$2\cdot d$的距离都会收到影响,我们需要知道最近的不受影响的点,这可以二分一下,距离大于$2\cdot d$的最小的点,然后可以运用差分的思想建一个数组,把这个坐标的值加扣的血量,每次到一个点我们的总伤害先减去差分数组,这样就能维护当前被影响的血量

AC代码

const int maxn=200050;
ll n,d,t,c[maxn];
PLL a[maxn];
int main()
{
    cin>>n>>d>>t;
    for(int i=1;i<=n;i++)
    {
        read(a[i].first);read(a[i].second);
    }
    sort(a+1,a+n+1);
    ll i=1;
    ll temp=0,ans=0;
    d*=2;
    while(i<=n)
    {
        temp-=c[i];
        a[i].second-=temp;
        if(a[i].second>0)
        {
            ll tt=(a[i].second+t-1)/t;
            ans+=tt;
            temp+=t*tt;
            int l=0,r=n+1;
            while(l<r)
            {
                int mid=l+r>>1;
                if(a[mid].first>a[i].first+d) r=mid;
                else l=mid+1;
            }
            if(l!=n+1) c[l]+=t*tt;
        }
        i++;
    }
    cout<<ans<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
最大团与极大团算法 最大团与极大团算法
本片笔记主要介绍了极大团与最大团的概念,记录一种dfs计算最大团的方法,介绍了用于求解极大团的Bron-Kerbosch算法及相关优化
下一篇 
CF Good Bye 2019 题解 CF Good Bye 2019 题解
时隔许久的题解,A到D题,感觉全是构造题啊) A. Card Game题意简述:有两个人玩游戏,第一个人有$k1$张牌,第二个人有$k2$张牌,一共有$n$张牌且牌值从$1$到$n$,每一次两人分别抽出一张牌,谁的牌大就拿走这两张牌,最后
  目录