题解：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 问题。

CPP

#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;
}

题解：P13538 [IOI 2025] Festival

文章操作

相关推荐

评论

题解：P13538 [IOI 2025] Festival