题解：P13535 [IOI 2025] 纪念品（souvenirs）

· · 题解

容易发现我们需要让每个物品（除了第 0 个）都作为第一个买的一次（即每个 [p_i,p_{i-1}) 里都询问一个数）。这样子每个数的次数都不会超标。其实可以做到找到每个 p。

考虑我们一开始只能问 p_0-1。我们发现如果一个询问可以得到一个物品的价格是很舒服的。我们定义 solve(i) 表示我们得到了 p_i，然后求出 p_{i+1,\dots,n-1}。这样如果我们询问直接得到了某个值就递归到后缀的子问题，然后可以把这个后缀删掉。

如果一开始得到的是多个物品的价值之和呢？可以发现我们能猜的只有平均价，因为要保证猜的价格不超过最大值，又要高于最小值。我们每次不妨每次找到所有未解决的询问里的最靠右的一个，如果它只有一个数，那就把这个后缀删掉，更新其他询问的信息；否则你就猜平均数，这样可以保证新加入的这个询问在当前的最后一个询问和最后一个没删的数之间，显然是不会和之前重复的。

重复这个过程一定可以结束。最后已经得到了所有物品的价格，把剩下的次数补上即可。

#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define ll         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
int n;
int cnt[105];
ll val[105];
deque<int>dq[105];
ll cost[105];
ll ask(ll x,int y){
    //(2z+y-1)*y/2<=x
    return (x*2/y+1-y)/2;
}
void clear_(){
    REP(i,0,n)if(dq[i].size()&&dq[i].back()==n-1)dq[i].pop_back(),cost[i]-=val[n-1];
    --n;
}
void solve(int x){
    if(x==n-1)return;
    auto [t,c]=transaction(val[x]-1);
    ++x;
    for(auto i:t)++cnt[i];
    cost[x]=val[x-1]-1-c;
    for(auto i:t)if(val[i]==-1)dq[x].pb(i);
    else cost[x]-=val[i];
    while(x<n){
        int lst=x;
        REP(i,x,n)if(dq[i].size()&&val[lst]==-1)lst=i;
        if(dq[lst].size()==1){
            val[lst]=cost[lst];
            solve(lst);
            clear_();
            continue;
        }
        ll p=ask(cost[lst],dq[lst].size());
        auto [t,c]=transaction(p);
        int y=t[0];
        cost[y]=p-c;
        for(auto i:t)++cnt[i];
        for(auto i:t)if(val[i]==-1)dq[y].pb(i);
        else cost[y]-=val[i];
    }
}
void buy_souvenirs(int N, ll lst) {
    n=N;
    REP(i,0,n)cnt[i]=0,cost[i]=-1,val[i]=-1,dq[i].clear();
    val[0]=lst;
    solve(0);
    REP(i,0,N){
        while(cnt[i]<i)transaction(val[i]),++cnt[i];
    }
}