专栏文章

题解：qoj8190 Jaw-Dropping Set

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minpcpk5
此快照首次捕获于
2025/12/02 06:09
3 个月前
此快照最后确认于
2025/12/02 06:09
3 个月前
查看原文
？
传送门
猜测 max⁡size=⌈n2⌉\max \text{size} =\lceil\frac{n}{2}\rceil。
证明：把每个数转化为 k×2xk\times 2^x 格式，选出来的 kk 互不相同，所以 max⁡size≤⌈n2⌉\max \text{size} \leq\lceil\frac{n}{2}\rceil；
选择 ⌊n2⌋+1,⋯n\lfloor\frac{n}{2}\rfloor+1,\cdots n，其大小为 ⌈n2⌉\lceil\frac{n}{2}\rceil，所以 max⁡size≥⌈n2⌉\max \text{size} \geq\lceil\frac{n}{2}\rceil。
我们设 fkf_{k} 表示选择了 k×2fkk\times 2^{f_{k}}。
那么我们要满足 ∀x∣y,fx>fy\forall x|y,f_x>f_y，也就是不能存在 kk 和 fkf_k 被偏序。
美怄哥天才的想到，令 fk=⌊log⁡3nk⌋f_{k}=\lfloor\log_3\frac{n}{k}\rfloor 即可。
时间复杂度 O(Tlog⁡3n)O(T\log_3n)。

评论

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

正在加载评论...