P9378 [THUPC 2023 决赛] 物理实验 题解

· · 题解

某网校讲了这个题，并且发现还可以交题解，那我来了。

我们这样去理解这个题目：有两个人 SD 和 LTF，还有 n 个物品。SD 要选 n-m 个，LTF 会在 SD 取了 a_i 个之后抢走一个，并且第 i 次他会按照一个优先级排列 p_i 抢走还在场上的优先级最高的那个物品，并且每次的优先级不一定相同。

现在你就是 SD，我是 LTF。你要找到一个方案让字典序最小。

先从简单的方面来看，让字典序更小是很好考虑的。假设最后你选择的物品塞进了一个集合 S，一开始他是空的，所以你的任务就是：已知一个集合 S ，问是否有方案得到 S。

注意到 2^{-i}\geq \sum_{k = i + 1}^{n}2^{-k}(i\geq 1)，优先满足前面的显然更优，于是你就让编号从小往大开始枚举。

那我就要开始打乱你的计划了。

假设这是我第一次取，我找到一个 t，使得 p_1, p_2, \cdots, p_{t - 1} 所对应的物品全部被你拿走了，但是 p_t 对应的物品正好没有，那按照优先级从高到低的规则，我肯定要拿走这个物品，换句话说，p_1, p_2, \cdots, p_{t - 1} 必须在前 a_1 次取走。

但是你这时候就能尝试第二次取了吗？不行！因为你不知道我第一次取了什么。

但你又发现，p_t 在第 a_1+1 次之后肯定是选不了的，要么是你选了要么是我选了。选不了的你不如就直接放掉让我抢走。

这样子再来考虑我的第二次抢夺，那就变成了和第一次一样的问题。

这样你依次考虑我每次抢夺，得到最初的集合 S 中所有元素最晚在什么时候取走。按照最晚取走的时间排序填入方案并判断是否合法即可。