专栏文章

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

MMirasycle
P13535题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miokkjeg
此快照首次捕获于
2025/12/02 20:43
3 个月前
此快照最后确认于
2025/12/02 20:43
3 个月前
查看原文
有意思的题目。但是不难，因为这题的约束太强了，导致你在每种情况下基本只能进行一种操作（有一些可能合法但是显然无意义的操作就不去考虑了），所以顺着这个模拟就可以 AC 了！
记 coico_i 表示 ii 的价格。solve(i,M) 表示已知 coi−1>c≥coico_{i-1}> c\ge co_i 的情况下求解 coico_i，并且会递归求出所有 co1,co2…coico_1,co_2\dots co_i。这个函数带记忆化功能，也就是求解过的 coico_i 被调用了会跳过。下文的除法默认下取整。
你会发现初始为了去求 co1co_1 只能询问 P0−1P_0-1，也就是 solve(1,P0−1){\rm solve}(1,P_0-1)。
假设返回了 {id1,id2…idm}\{id_1,id_2\dots id_m\}，并且通过询问和返回的钱数我们知道了 ∑coidi=C\sum co_{id_i}=C。这个时候 id1id_1 已经不能再询问了，而我们必须保证不能问到空的，这两个条件很强，所以我们应该去寻找一个介于 coidmco_{id_m} 到 coid1co_{id_1} 之间的数。由于和一定，且 coco 单调递减，所以 coid1>Cm>coidmco_{id_1}>\dfrac{C}{m}>co_{id_m}。
于是直接询问 Cm\dfrac{C}{m} 会得到一个以原序列中的某个数字 idiid_i 开头的序列。调用 solve(idi,Cm){\rm solve}(id_i,\dfrac{C}{m}) 之后，我们可以求出 coidi,coidi+1…coidmco_{id_i},co_{id_{i+1}}\dots co_{id_m}。
于是可以将上述问题 {id1,id2…idm}\{id_1,id_2\dots id_m\} 缩小到 {id1,id2…idm′}\{id_1,id_2\dots id_{m'}\}，其中 m′=i−1m'=i-1。不断执行这个过程，我们就可以得到 coid1co_{id_1} 了，也就完成了 solve(coid1)\rm {solve}(co_{id_1}) 的任务。这样子就可以解出所有的 coico_i 了。
下面分析使用购买次数的问题，要求购买 ii 的次数为 ii，我们不怕买少了，因为可以最后求出所有的 coico_i 之后再补。由于 ii 最多在求解 co1,co2…coico_1,co_2\dots co_i 的时候每次各购买一个，所以不会买多。
这个问题就完美解决了。
CPP
#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]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...