专栏文章

题解：CF1651F Tower Defense

hhoko
CF1651F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miogx5oq
此快照首次捕获于
2025/12/02 19:01
3 个月前
此快照最后确认于
2025/12/02 19:01
3 个月前
查看原文

题目传送门

题目大意

给出 nn 个塔，排列在数轴 1∼n1\sim n 的位置上，每个塔有一个魔力值上限 cic_i 和一个恢复速度 rir_i，每秒魔力值 aia_i 会变成 min⁡(ci,ai+ri)\min(c_i,a_i+r_i) ，每个塔的魔力值初始为 cic_i。之后会有 mm 个怪兽，每一个怪兽会在 tit_i 秒的时候出现在第一个塔面前，之后只要怪兽还有血，就会每秒往后移动一个单位。当怪兽到达塔面前时，塔的魔力值会减少 min⁡(hi,ci)\min(h_i,c_i)，这时怪兽的血量也会扣除对应值。有些怪兽在经过了 nn 个塔后还有血，要求出这些怪兽的血量和。

解题思路

注意到数据范围，发现 O(nn)O(n\sqrt n) 可以过。所以我们考虑分块。
我们对塔进行分块，块的大小为 n\sqrt n。对于一个块，如果怪兽的血量足以支持他走完这一个块，那么说明这个块中的塔就被推平了。对于这种情况，我们可以直接计算，其余情况就要暴力计算。
现在考虑怎么预处理出每个块在经过 ii 的时间后的恢复血量。这个我们先考虑单个塔是怎么回血的。每个塔如果可以恢复 rir_i 的血量那就恢复 rir_i，否则就恢复 ci mod ric_i\bmod r_i。
所以我们可以先对每个块增加 rir_i 的那一段进行差分，再做一次前缀和。之后在对恢复 ci mod ric_i\bmod r_i 的那一段做一次前缀和。
之后如果怪物血量大于等于块的血量，就直接对块进行操作，否则就暴力计算。
代码如下：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3010101;
ll n,m,tot,a[N],c[N],h[N],r[N],L[N],R[N],vis,t[N],f[N],ans;
void js(ll x,ll y,ll s,ll t){
    vis=0;
    for(int i=L[x];i<=R[x];i++){
        a[i]=min(c[i],a[i]+(s-t)*r[i]);
        if(a[i]<=h[y]){
            h[y]-=a[i];
            a[i]=0;
        }
        else{
            a[i]-=h[y];
            h[y]=0,vis=1;
        }
    }
}
void solve(ll x){
    vis=1;
    ll ti=0;
    for(int i=0;i<=5e5;i++)f[i]=0;
    for(int i=L[x];i<=R[x];i++){
        f[1]+=r[i];
        f[c[i]/r[i]+1]-=r[i];
    }
    for(int i=1;i<=5e5;i++)f[i]+=f[i-1];
    for(int i=L[x];i<=R[x];i++)f[c[i]/r[i]+1]+=c[i]%r[i];
    for(int i=1;i<=5e5;i++)f[i]+=f[i-1];
    for(int i=1;i<=m;i++){
        if(!h[i])continue;
        ll now=L[x]+t[i]-1;
        if(vis)js(x,i,now,ti);
        else{
            if(h[i]<f[now-ti])js(x,i,now,ti);
            else h[i]-=min(f[now-ti],h[i]);
        }
        ti=now;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    tot=sqrt(n)+1;
    for(int i=1;i<=n;i++)cin>>c[i]>>r[i],a[i]=c[i];
    for(int i=1;i<=tot;i++){
        L[i]=R[i-1]+1;
        R[i]=min(n,i*tot);
    }
    cin>>m;
    for(int i=1;i<=m;i++)cin>>t[i]>>h[i];
    for(int i=1;i<=tot;i++)solve(i);
    for(int i=1;i<=m;i++)ans+=h[i];
    cout<<ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...