[AtCoder NDPC2026] Game 题解

FFTotoro · 2026-05-08 18:44:49 · 题解

有个加强版 QOJ9609 幽默还是夢。好像并不需要使用 DP。

首先差分一下，题意相当于给定 n 种物品，每种物品有两个类型：若买大小为 1 的可以得到 x_i 的价值，若买大小为 2 的则可以得到 y_i 的价值，问只考虑一段前缀 [1,d] 中的物品时，买的物品大小之和恰好为 b 时能获得最大价值是多少。

先考虑部分分怎么做。将物品分为两类：第一类满足 x_i\ge y_i-x_i（以下称为一类物品），这种情况下直接把它拆成大小为 1 的、价值分别为 x_i 和 y_i-x_i 的两个独立的物品，之后直接贪心；然而第二类满足 x_i<y_i-x_i（以下称为二类物品），似乎有点棘手。

这个时候考虑到关键结论：若存在两种二类物品，使得它们都买了大小为 1 的，那么必然是不优的，直接调整就能做到更好（相关题目：[PA 2026] 堆煎饼 / Stosy naleśników）；也就是说，大部分的二类物品都是买大小为 2 的。这启发我们直接把它视为一个大小为 2 的、价值为 y_i 的物品，接着按照性价比（物品价值除以物品大小）排序进行贪心，最后进行一些微调（有点类似清仓甩卖）。

现在来讨论“微调”操作的细节：

• 首先按照性价比排序，若这样选择能够恰好选到 b 个物品，就不需要调整了；
• 否则，只可能是购买的最后一个物品大小为 2，使物品大小之和来到了 b+1。先退掉这个物品，此时大小之和为 b-1，于是有两种选择：
  • 在前面删掉一个价值最低的一类物品，接着把这个被退掉的二类物品加回去；
  • 在后面选择一个价值最高的一类物品，或选择一个 x_i 最大的二类物品 i，并购买大小为 \textbf{1} 的这个物品获得 x_i 的价值。

直接模拟就可以获得 d=N 的部分分。接下来尝试解决“前缀询问”：将所有询问按照 d 升序排序后做扫描线，使用线段树维护当前可用的物品。具体地，线段树上的下标为该物品按性价比排序后的排名，当 d-1\to d 时加入原始下标为 \textbf{d} 的物品。查询时先线段树二分出分界点（即左边可用物品大小之和 \le b 的最靠右的位置），若和为 b-1 则需要模拟微调操作：对于这种需求，还得再开两棵线段树维护微调操作所需的前缀 \min / 后缀 \max，在做扫描线的时候同步更新。

时间复杂度 O(T(N+Q)\log N)，可以轻松通过。

参考代码（GNU C++20, with AtCoder Library）：

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int,ll> S;
const ll I=2e18;
inline S op(S x,S y){
  return S(x.first+y.first,x.second+y.second);
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,q; cin>>n>>q;
    vector<ll> d(n);
    vector<array<int,2> > a(n);
    for(int i=0;i<n;i++){
      int x,y,z; cin>>x>>y>>z;
      d[i]=x,a[i]={y-x,z-y};
    } // 差分构造物品
    partial_sum(d.begin(),d.end(),d.begin());
    vector<pair<pair<int,int>,int> > l;
    for(int i=0;i<n;i++){
      if(a[i][0]>=a[i][1]){
        l.emplace_back(S(1,a[i][0]),i);
        l.emplace_back(S(1,a[i][1]),i);
      } // 一类物品
      else l.emplace_back(S(2,a[i][0]+a[i][1]),i); // 二类物品
    }
    int m=l.size();
    sort(l.begin(),l.end(),[&](auto &x,auto &y){
      return x.first.second*y.first.first>x.first.first*y.first.second;
    }); // 按照性价比排序
    vector<vector<int> > v(n);
    for(int i=0;i<m;i++)
      v[l[i].second].emplace_back(i);
    vector<vector<pair<int,int> > > qr(n);
    for(int i=0;i<q;i++){
      int d,b; cin>>d>>b;
      qr[d-1].emplace_back(b,i);
    } // 离线询问
    segtree<S,op,[&](){return S();}> t1(m);
    segtree<ll,[&](ll x,ll y){return min(x,y);},[&](){return I;}> t2(m);
    segtree<ll,[&](ll x,ll y){return max(x,y);},[&](){return -I;}> t3(m);
    vector<ll> w(q);
    for(int i=0;i<n;i++){
      for(int p:v[i]){
        auto [c,w]=l[p].first;
        t1.set(p,S(c,w));
        if(c==1)t2.set(p,w),t3.set(p,w);
        else t2.set(p,a[i][1]),t3.set(p,a[i][0]);
      } // 加入可用物品
      for(auto [b,p]:qr[i]){
        int r=t1.max_right(0,[&](S x){return x.first<=b;}); // 找分界点
        if(S s=t1.prod(0,r);s.first==b)w[p]=s.second;
        else w[p]=s.second+max(t3.prod(r,m),l[r].first.second-t2.prod(0,r)); // 进行微调
        w[p]+=d[i];
      }
    }
    for(ll i:w)cout<<i<<'\n';
  }
  return 0;
}