题解：P13538 [IOI 2025] Festival

· · 题解

这个题是拼尽全力无法战胜之后学习了 lhx 大神的代码，茅塞顿开！为什么人类可以这么智慧？

首先这个 (P,T) 的东西买一次会把 x 的钱变成 Tx-TP。这是一个一次函数 f(x)=kx-b。相当于选若干个函数迭代，每一步都不能小于 0。

这个东西就是经典的 exchange argument。把函数 ax-b 和 cx-d 迭代起来得到：c(ax-b)-d 和 a(cx-d)-b，相当于比较 bc+d 和 ad+b。也就是比较 \frac{b}{a-1} 和 \frac{d}{c-1}。这里需要特殊处理斜率为 1：由于作用纯菜，显然是把所有 T=1 的放最后，然后按 P 升序。然后排完序可以通过 sub5。

然后有一个暴力的平方 dp：f_{i,j} 表示前 i 个函数选了 j 个，当前最多剩多少钱。可以获得没多少分。拼所有包可以获得 66。

然后观察一下 sub6 的性质，只能得到如下结论：注意到如果一段前缀会让钱变多，那选上这个就不劣。剩下的东西一定会让钱变少。

然后有一个写乱搞的想法就是控制 j 的值域。但是我们竟然可以分析出 j 的值域真的很小！不妨设 T 相同。记价格是 p_i 序列。找到第一个会让钱严格变少的地方开始 dp，然后第一次会让钱变成 T(x-p_i)<x。这里至少会让钱数变少 1。然后在买第二份的时候，这个 -1 会放到前面的括号里，至少乘上 T，然后后面的 -T\times p_i 由于排序的原因一定会变小。于是整个东西都会变小，而且第 i 次买至少会比原来少 2^i！！！（因为这个 delta 每次都至少会乘 T）

于是显然只考虑 T>1 的情况下，j 的范围只有 O(\log V)。最后和 T=1 拼一下就好了。

时间复杂度 O(n\log V)。注意 long long 问题。

#include "festival.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()
ll inf=1'000'000'000'000'000ll;
struct node{
    ll k,b;int id;
    bool operator <(node a){
        return k*a.b+b<a.k*b+a.b;
    }
    ll calc(ll x){return min(k*x+b,inf);}
};
int n,M=100;
ll f[200005][105];
vector<int>max_coupons(int AA,vector<int>P,vector<int>T){
    ll A=AA;
    vector<node>a,b;n=P.size();
    REP(i,0,n)if(T[i]>1)a.pb({T[i],-1ll*P[i]*T[i],i});
    else b.pb({0,P[i],i});
    sort(all(a));sort(all(b));
    vector<int>res;
    int st=0;
    REP(i,0,a.size())if(a[i].calc(A)>=A){
        res.pb(a[i].id);
        A=a[i].calc(A);
        ++st;
    }else break;
    REP(i,st,a.size())a[i-st]=a[i];
    int m=a.size()-st;
    REP(i,0,m+1){
        REP(j,0,M+1)f[i][j]=-1;
    }
    f[0][0]=A;
    REP(i,0,m){
        REP(j,0,M)if(a[i].calc(f[i][j])>=0){
            f[i+1][j+1]=max(f[i+1][j+1],a[i].calc(f[i][j]));
        }
        REP(j,0,M+1)f[i+1][j]=max(f[i+1][j],f[i][j]);
    }
    vector<int>t;
    int x=m,y=M;
    while(f[x][y]<0)--y;
    vector<ll>s;ll sum=0;
    REP(i,0,b.size())s.pb(sum+=b[i].b);
    int mx=-1,mp=0;
    REP(i,0,y+1){
        int t=i+(upper_bound(all(s),f[m][i])-s.begin());
        if(mx<=t)mx=t,mp=i;
    }
    y=mp;
    while(x){
        if(y&&a[x-1].calc(f[x-1][y-1])==f[x][y])t.pb(a[x-1].id),--y;
        --x;
    }
    reverse(all(t));
    for(auto i:t)res.pb(i);
    A=f[m][mp];
    for(auto &[k,b,id]:b)if(A>=b)res.pb(id),A-=b;
    return res;
}