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

· · 题解

有意思的题目。但是不难，因为这题的约束太强了，导致你在每种情况下基本只能进行一种操作（有一些可能合法但是显然无意义的操作就不去考虑了），所以顺着这个模拟就可以 AC 了！

记 co_i 表示 i 的价格。solve(i,M) 表示已知 co_{i-1}> c\ge co_i 的情况下求解 co_i，并且会递归求出所有 co_1,co_2\dots co_i。这个函数带记忆化功能，也就是求解过的 co_i 被调用了会跳过。下文的除法默认下取整。

你会发现初始为了去求 co_1 只能询问 P_0-1，也就是 {\rm solve}(1,P_0-1)。

假设返回了 \{id_1,id_2\dots id_m\}，并且通过询问和返回的钱数我们知道了 \sum co_{id_i}=C。这个时候 id_1 已经不能再询问了，而我们必须保证不能问到空的，这两个条件很强，所以我们应该去寻找一个介于 co_{id_m} 到 co_{id_1} 之间的数。由于和一定，且 co 单调递减，所以 co_{id_1}>\dfrac{C}{m}>co_{id_m}。

于是直接询问 \dfrac{C}{m} 会得到一个以原序列中的某个数字 id_i 开头的序列。调用 {\rm solve}(id_i,\dfrac{C}{m}) 之后，我们可以求出 co_{id_i},co_{id_{i+1}}\dots co_{id_m}。

于是可以将上述问题 \{id_1,id_2\dots id_m\} 缩小到 \{id_1,id_2\dots id_{m'}\}，其中 m'=i-1。不断执行这个过程，我们就可以得到 co_{id_1} 了，也就完成了 \rm {solve}(co_{id_1}) 的任务。这样子就可以解出所有的 co_i 了。

下面分析使用购买次数的问题，要求购买 i 的次数为 i，我们不怕买少了，因为可以最后求出所有的 co_i 之后再补。由于 i 最多在求解 co_1,co_2\dots co_i 的时候每次各购买一个，所以不会买多。

这个问题就完美解决了。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=110;
int n,cnt[maxn]; ll co[maxn];
pair<vi,ll> transaction(ll M);
void to(ll M);
void calc(pair<vi,ll> vec,ll M){
    vi id=vec.fi,tmp;  M-=vec.se;
    for(auto z:id)
        if(co[z]) M-=co[z];
        else tmp.pb(z);
    id.clear(); for(auto z:tmp) id.pb(z);
    while(id.size()>1){
        to(M/id.size());
        while(co[id.back()]) M-=co[id.back()],id.pop_back();
    }
    co[id.front()]=M;
}
void solve(int pos,ll M,pair<vi,ll> vec){
    for(auto id:vec.fi) cnt[id]--;
    if(!co[pos]) calc(vec,M);
    while(co[pos+1]&&pos+1<=n) pos++;
    if(pos<n) to(co[pos]-1);
}
void to(ll M){
    pair<vi,ll> res=transaction(M);
    solve(res.fi.front(),M,res);
}
void buy_souvenirs(int N,ll P0){
    memset(co,0,sizeof(co));
    for(int i=1;i<=N-1;i++) cnt[i]=i;
    n=N-1; to(P0-1);
    for(int i=1;i<=n;i++)
        while(cnt[i]--) transaction(co[i]);
}