ioi2025d1t1

_jimmywang_ · 2025-07-31 16:03:12 · 题解

秒赤，好玩。

很神秘的题意，交互但是目标不是得到某个值而是完成一个目标，第一次见。

我们先把交互库返回的东西处理一下，我们想要返回的几样商品的价值和，而不是剩下的钱。我们记返回值为 [a,b,c,...],x，方括号里的是商品集合，x 是它们的价值和。

首先我们发现询问 \ge P[0] 的值是不合法的，不然 P[0] 就买了；过于小的值也是很危险的，毕竟你不知道 P[n-1] 是什么，万一小于它你就买不到东西，也是不合法的。那么第一步我们能干什么？唯一安全的值应该是 P[0]-1。

知道了这个后，我们来手玩一下小数据，比如 n=3。

第一步问 P[0]-1，会有两种情况：

返回 [1] x。这下我们直接知道 P[1]=x，接着问一次 P[1]-1 就能知道 P[2] 了。
返回 [1,2] x。这该怎么办！1 号商品已经没有剩余购买次数了，下一步只能买一个 2。这意味着我必须找出一个 x'\in[P[2],P[1]) 来询问。容易发现 x'=\lfloor\frac{x}{2}\rfloor 满足条件。

这下 n=3 就解决了，拼盘 39pts 到手。

这个过程中，有几个点很有启发性：

找出一个 x'\in[P[2],P[1]) 来询问：如果我们能够对每个 i\in[1,n-1]，都找到一个 x\in [P[i],P[i-1]) 询问一次，这样获得的信息会构成一组 n-1 元线性方程组，而且是满秩的（因为这样一次询问，i 商品一定会被买，且只有 \ge i 的商品可能会被买，因此是对角线全为 1 的上三角），可以直接消元得到每一个 P[i]。而且如果对于每个 [P[i],P[i-1]) 恰好询问一次，一定能满足 i 被买了 \le i 次，不够的在解出 P[i] 后补上即可。
知道 P[i] 的值后，x'=P[i]-1 一定属于 [P[i+1],P[i])，可以直接用。

有了这些前提后，我们定义一个求解函数 f(S,x) ，其中 S 是一个商品编号集，x 是 S 中商品的价值和（这个信息是由一次向交互库询问得来的）。这个函数做的事情是，求出 \ge \min(S) 的所有商品的具体价值。

记 \min(S)=m，那么显然这个 (S,x) 是上一次询问了一个 x'\in[P[m],P[m-1]) 得来的。为了满足每个 [P[i],P[i-1]) 恰好询问一次，我们需要保证 m 只会作为 \min(S) 出现一次。这个记忆化一下就好。

具体做法是：

每次进入这个函数，所有已知商品价格的 i 一定形成一段后缀（这个是函数本身的进行过程保证的）。我们不断检查 \max(S) 的价格是否已经确定，如果是，就删除 \max(S) 并相应的更新 x。（这一步其实是在消元）
（如果此时 |S|>1）基于启发点 (2)，求出剩余物品的平均价格 avr=\lfloor\frac{x}{|S|}\rfloor 并进行一次询问。注意此时 \min(S) 和 \max(S) 之间的所有值我们应该都不知道，相应的所有 [P[i+1],P[i]) 也都没有被询问过，所以进行这个询问是合理的。询问完以后递归处理。
重复 1，2 两步直到 |S|=1。此时容易发现 \min(S) 应该仍然是 m，这个时候显然 P[m]=x。由启发点 (3)，此时我们获得了 x-1\in[P[m+1],P[m])，如果 m+1 没有被处理过，那么询问一次 x-1 并递归处理。

最开始询问一次 P[0]-1 并调用即可。

最后显然可能有物品没买够的，既然我们已经求出所有物品的价格，询问 P[i] 就能恰好买一个 i，补上即可。

最后补一句，容易发现这个 5000 次交互是假的。每次至少得买一个，总共最多买 1+2+\dots+99=4950 次，根本不怕这个次数上限。