题解：qoj8190 Jaw-Dropping Set

BPG_ning · 2025-10-04 17:29:52 · 题解

？

传送门

猜测 \max \text{size} =\lceil\frac{n}{2}\rceil。

证明：把每个数转化为 k\times 2^x 格式，选出来的 k 互不相同，所以 \max \text{size} \leq\lceil\frac{n}{2}\rceil；

选择 \lfloor\frac{n}{2}\rfloor+1,\cdots n，其大小为 \lceil\frac{n}{2}\rceil，所以 \max \text{size} \geq\lceil\frac{n}{2}\rceil。

我们设 f_{k} 表示选择了 k\times 2^{f_{k}}。

那么我们要满足 \forall x|y,f_x>f_y，也就是不能存在 k 和 f_k 被偏序。

美怄哥天才的想到，令 f_{k}=\lfloor\log_3\frac{n}{k}\rfloor 即可。

时间复杂度 O(T\log_3n)。