【线段树分治 01背包】loj#6515. 「雅礼集训 2018 Day10」贪玩蓝月

考试时候怎么就是没想到线段树分治呢？

题目描述

《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备，每件装备有一个特征值 $w$ 和一个战斗力 $v$ 。在每种特定的情况下，你都要选出特征值的和对 $\rm MOD$ 取模后在一段范围内的装备，而角色死亡时自己的装备会爆掉。每个角色的物品槽可以看成一个双端队列，得到的装备会被放在两端，自己的装备爆掉也会在两端被爆。

现在我们有若干种事件和询问，如下所示：

IF w v：在前端加入一件特征值为 $w$ 战斗力为 $v$ 的装备
IG w v：在后端加入一件特征值为 $w$ 战斗力为 $v$ 的装备
DF：删除最前端的装备
DG：删除最后端的装备
QU l r：在当前的装备中选取若干装备，他们的和对 $\rm MOD$ 取模后在 $[l, r]$ 中，使得这些装备的战斗力之和最大

为了锻炼你的水平，请尽量使用在线做法。

题目分析

做法一：线段树分治

考虑一下w,v强制在线的做法。

注意到这个在线是个“半在线”：因为虽然w,v是被加密过的，但是操作种类是可见的。那么就可以预先处理处每一个物品的存在时间区间，因此这样对操作进行线段树分治就是个离线问题了。

 #include<bits/stdc++.h>

 typedef long long ll;

 const int maxn = ;

 int m,p,tag;

 ll ans[maxn];

 struct QRs

 {

     char opt[];

     int l,r;

 }qr[maxn];

 struct Opt

 {

     int s,t,w,v;

     Opt(int a=, int b=, int c=, int d=):s(a),t(b),w(c),v(d) {}

 }rec[maxn];

 struct node

 {

     ll f[],g[];

     void init()

     {

         memset(f, -0x3f3f3f3f, sizeof f), f[] = ;

     }

     void update(int w, int v)

     {

         for (int i=; i<p; i++) g[i] = f[i];

         for (int i=; i<p; i++)        //x+w=i

             f[i] = std::max(f[i], g[(i-w+p)%p]+v);

     }

     ll query(int l, int r)

     {

         ll ret = -;

         for (int i=l; i<=r; i++) ret = std::max(f[i], ret);

         return ret;

     }

 }sta;

 typedef std::vector<Opt> vec;

 std::deque<int> deq;

 vec opt;

 int read()

 {

     char ch = getchar();

     int num = , fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = -;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     return num*fl;

 }

 void solve(int l, int r, vec opt, node sta)

 {

     vec L,R;

     int mid = (l+r)>>;

     for (int i=, mx=opt.size(); i<mx; i++)

     {

         int s = opt[i].s, t = opt[i].t;

         if (s <= l&&r <= t) sta.update(opt[i].w, opt[i].v);

         else{

             if (s <= mid) L.push_back(opt[i]);

             if (t > mid) R.push_back(opt[i]);

         }

     }

     if (l==r){

         if (qr[l].opt[]=='Q') ans[l] = sta.query(qr[l].l, qr[l].r);

     }else solve(l, mid, L, sta), solve(mid+, r, R, sta);

 }

 int main()

 {

     scanf("%*d"), m = read(), p = read();

     for (int i=, tmp; i<=m; i++)

     {

         scanf("%s",qr[i].opt);

         if (qr[i].opt[]=='I'){

             qr[i].l = read()%p, qr[i].r = read(), ++tag;

             if (qr[i].opt[]=='F') deq.push_front(tag);

             else deq.push_back(tag);

             opt.push_back(Opt(i, m, qr[i].l, qr[i].r));

         }

         if (qr[i].opt[]=='Q')

             qr[i].l = read(), qr[i].r = read();

         if (qr[i].opt[]=='D'){

             if (qr[i].opt[]=='F')

                 tmp = deq.front(), deq.pop_front();

             else tmp = deq.back(), deq.pop_back();

             opt[tmp-].t = i-;

         }

     }

     sta.init();

     solve(, m, opt, sta);

     for (int i=; i<=m; i++)

         if (qr[i].opt[]=='Q') printf("%lld\n",ans[i]);

     return ;

 }

做法二：思维题栈启发式

可能要先咕着

巴特西

【线段树分治 01背包】loj#6515. 「雅礼集训 2018 Day10」贪玩蓝月

题目描述

题目分析

做法一：线段树分治

做法二：思维题栈启发式

最新文章

热门文章

巴特西

【线段树分治 01背包】loj#6515. 「雅礼集训 2018 Day10」贪玩蓝月

题目描述

题目分析

做法一：线段树分治

做法二：思维题 栈 启发式

最新文章

热门文章

做法二：思维题栈启发式