2021 CCCC 西电选拔赛 L2-03
我太菜了啊 😔😫😭
给出集合$S$的递归定义:
- $a \in S$
- $2a + 1, 3a + 1 \in S$
(还有一条是啥来着我忘了, 不过不影响理解题意)
给出$a$, 求$S$中所有元素从小到大排序以后的第$k$个数.
(数据范围忘了, 大概要$O(k)$才能过)
对于集合中的每个数的 $2a+1$ 和 $3a+1$ 分开看, 能够得到两个单调的序列, 然后把这两个单调的序列合并成一个单调队列, 就做完了.
有点类似于归并排序合并两个序列, 只不过这 “两个序列” 是边做才能边构造出来的, 因为需要知道单调队列最后一个数是什么才能算出两个序列中的值.
没有代码
还是基础不扎实, 考场想到了分开看, 但不知道怎么样确定最终顺序. 实际上类似归并, 应该抽象出 “所有通过 $2a+1$ 产生的数"的序列 和 “所有通过 $3a+1$ 产生的数"的序列 合并成一个序列, 而不是考虑当前这个数产生的两个数应该在哪个位置, 因为这样实际上就是想着"做完就丢进去”.
瞎扯, 我也不知道该怎么表达. 我太菜了.