首页 > 其他 > 详细

HDU - 3954 Level up--打怪升级装备全靠爆(线段树小进阶)

时间:2020-07-09 23:31:56      阅读:92      评论:0      收藏:0      [点我收藏+]

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3954

题目大意:给你n个人初始状态都是1级0经验,有qw次操作,‘W‘操作,放一波怪,区间$[l,r]$的人去砍一波怪,然后对于$k$级的人得到的经验是$e_i\times k$,每级的的经验是$a_i$,升完级后经验保留,最大级是$limt$。‘Q‘操作,询问区间$[l,r]$中经验最多的是多少

Sample Input

2
3 3 5
1 2
W 1 1 1
W 1 2 1
Q 1 3
W 1 3 1
Q 1 3

5 5 8
2 10 15 16 
W 5 5 9
W 3 4 5
W 1 1 2
W 2 3 2
Q 3 5
W 1 3 8
Q 1 2
Q 3 5

Sample Output

Case 1:
3
6

Case 2:
9
18
25

emmm,很明显是跑个线段树,不过怎么跑是个关键,我们维护一下每个区间的最大级和最大经验(实际上这两个肯定是同一个人),维护一个最小升级需求。这个最小升级需求我们要全部转化为1级的经验来方便计算。

当这个怪送的经验$e_i$大于等于该区间最小升级需求的时候,我们需要将其更新到根节点,否则打个标记就完事了,其update函数如下:

void update(int l,int r,int rt,int L,int R,int val)
{
    if (l>=L && r<=R){
        if (val>=tree[rt].need){//如果能升级,直接更新到根节点
            if (l==r){
                tree[rt].exp+=tree[rt].level*val;
                while(tree[rt].exp>=lev_exp[tree[rt].level]) tree[rt].level++;
                int last=lev_exp[tree[rt].level]-tree[rt].exp;
                int p=last/tree[rt].level;//把需要的经验全部转换为1级的经验
                if (last%tree[rt].level) p++;
                tree[rt].need=p;
            }
            else {
                if (tree[rt].up) push_down(rt);
                int mid=(l+r)>>1;
                if (mid>=L) update(lson,L,R,val);
                if (mid<R) update(rson,L,R,val);
                push_up(rt);
            }
        }
        else {
            tree[rt].up+=val;
            tree[rt].exp+=tree[rt].level*val;
            tree[rt].need-=val;
        }
        return;
    }
    if (tree[rt].up) push_down(rt);
    int mid=(l+r)>>1;
    if (mid>=L) update(lson,L,R,val);
    if (mid<R) update(rson,L,R,val);
    push_up(rt);
}

就是update函数麻烦了点,其他的和普通的线段树并没有太大的差别。

以下是AC代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lc rt<<1
#define rc rt<<1|1
const int mac=1e4+10;
const int inf=1e9+10;

struct node
{
    int level,exp,up,need;
}tree[mac<<2];
int lev_exp[15];

void build(int l,int r,int rt)
{
    tree[rt].level=1;
    tree[rt].exp=tree[rt].up=0;
    tree[rt].need=lev_exp[1];
    if (l==r) return;
    int mid=(l+r)>>1;
    build(lson);build(rson);
}

void push_up(int rt)
{
    tree[rt].level=max(tree[lc].level,tree[rc].level);
    tree[rt].exp=max(tree[lc].exp,tree[rc].exp);
    tree[rt].need=min(tree[lc].need,tree[rc].need);
}

void push_down(int rt)
{
    tree[lc].up+=tree[rt].up;
    tree[rc].up+=tree[rt].up;
    tree[lc].exp+=tree[lc].level*tree[rt].up;
    tree[rc].exp+=tree[rc].level*tree[rt].up;
    tree[lc].need-=tree[rt].up; tree[rc].need-=tree[rt].up;
    tree[rt].up=0;
}

void update(int l,int r,int rt,int L,int R,int val)
{
    if (l>=L && r<=R){
        if (val>=tree[rt].need){//如果能升级,直接更新到根节点
            if (l==r){
                tree[rt].exp+=tree[rt].level*val;
                while(tree[rt].exp>=lev_exp[tree[rt].level]) tree[rt].level++;
                int last=lev_exp[tree[rt].level]-tree[rt].exp;
                int p=last/tree[rt].level;//把需要的经验全部转换为1级的经验
                if (last%tree[rt].level) p++;
                tree[rt].need=p;
            }
            else {
                if (tree[rt].up) push_down(rt);
                int mid=(l+r)>>1;
                if (mid>=L) update(lson,L,R,val);
                if (mid<R) update(rson,L,R,val);
                push_up(rt);
            }
        }
        else {
            tree[rt].up+=val;
            tree[rt].exp+=tree[rt].level*val;
            tree[rt].need-=val;
        }
        return;
    }
    if (tree[rt].up) push_down(rt);
    int mid=(l+r)>>1;
    if (mid>=L) update(lson,L,R,val);
    if (mid<R) update(rson,L,R,val);
    push_up(rt);
}

int query(int l,int r,int rt,int L,int R)
{
    int ans=0;
    if (l>=L && r<=R) return tree[rt].exp;
    int mid=(l+r)>>1;
    if (tree[rt].up) push_down(rt);
    if (mid>=L) ans=max(ans,query(lson,L,R));
    if (mid<R) ans=max(ans,query(rson,L,R));
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int t,Case=0;
    scanf ("%d",&t);
    while (t--){
        int n,lim,qw;
        scanf ("%d%d%d",&n,&lim,&qw);
        lev_exp[lim]=inf;
        for (int i=1; i<lim; i++)
            scanf ("%d",&lev_exp[i]);
        printf("Case %d:\n",++Case);
        build(1,n,1);
        while (qw--){
            char s[5];
            int l,r,e;
            scanf ("%s%d%d",s,&l,&r);
            if (s[0]==W){
                scanf ("%d",&e);
                update(1,n,1,l,r,e);
            }
            else printf("%d\n",query(1,n,1,l,r));
        }
        printf("\n");
    }
    return 0;
}

 

HDU - 3954 Level up--打怪升级装备全靠爆(线段树小进阶)

原文:https://www.cnblogs.com/lonely-wind-/p/13276764.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!