perm 烫发

WeLikeStudying · 2022-05-28 08:53:35 · 题解

• 以前作者的措辞可能不太恰当，但是我觉得这是能够理解的，毕竟作者早已退役，\text{APIO} 比赛，就算规模再大，对我来说只有思维训练的价值而已。
• 如果各位不嫌弃我的祝福的话，我希望大家不要留下遗憾。

题意

• 输出一个排列，满足它存在恰好 k 个递增子序列（包括空序列）。
• 你需要使得排列长度不大于 90，k\le 10^{18}。
• 多测，测试组数不超过 100。

分析

• 一个小的部分分：k\le 90。
• 输出长度为 k-1 的逆序排列代码，信息复杂度 O(k)，最坏情况显然是需要用 10^{18}-1 个数表示 10^{18}，理论得分 10，实际得分 10。
• 你采取任何一种合法构造方法都能拿到这 10 分，因为这已经是可能构造出来的最长排列了。
• 是构造题呢，仔细思考一下，构造这样一种排列：所有合法的不下降子序列都不能跨过一个范围。
• （上图实际的形状：多段连续的上升子序列，其中相对前面的段的元素严格大于后面的段）
• 现在问题就变成了：给定 n\le90 个数 a_i，满足： \sum_{i=1}^n(2^{a_i}-1)=k-1
• 然后就可以构造了，不论怎么样都不会超过 90 个数吧（flag）（upd：flag 没了）。
• 代码，信息复杂度 O(\log^2k)，更具体地，它需要用 1713 个数来表示 2^{59}+2^{58}-58，理论得分 65.49，实际得分 71.2。
• 我似乎建立了一个钢琴的模型，如下图：
• （上图实际的形状：一个严格上升序列，一个严格下降序列，交错摆放，且上升序列的数严格大于下降序列）
• 考虑每个黑点右上方有多少个红点，那么黑点的贡献是关于二的指数，可以发现这个结构很适合拆位，代码，信息复杂度 O(\log k)，更具体地，它需要用 117 个数来表示 2^{59}+2^{58}-1，理论得分 91，实际得分 91.36。
• 类题，接下来进入玄学领域：卡常，因为能用长度不超过 n 的数列表示的数（不论它具体是啥）大小显然绝对不超过 \lceil \log_2 k\rceil（毕竟你至少要表示得出这么大的数才行）。
• 所以 O(\log k) 是一个不可逾越的理论下限，在这个时候，常数就极其重要了，我们刚才的算法信息复杂度理论上是 \lfloor\log_2k\rfloor+\operatorname{popcount}(k)-1，即常数最坏为 2，但是这道玄学题目的常数最坏是 1.5。
• 奆佬的赛时想法，既然明确了正解不是它，那么它很可能得到满分（如果你有足够的代码实现功底的话）。
• 以下是和奆佬讨论的结果，奆佬的信息学直觉：2^{60} 恰好在 10^{18} 左右，而 90=60\times 1.5，实在是太整了，不像是乱搞的信息复杂度，正因为有了奆佬的提醒，才能有以下的思考，它的简洁和优美显示它确实是正解。
• 首先那个骨架是很难少的，所以我们就要针对 \operatorname{popcount} 的常数下功夫。
• 如何做呢，容易发现这样一个性质：
• 具体是为啥呢，原因就是如果其它的贡献单独考虑，而且把高上去的点与前两个点相互作用产生的权值累加的话，那么等价于这个高的黑点权值乘 3。
• 也就是说：如果我们在前面先定下了两个 1，那么后面就可以用一个 1 来代表连续的两个 1。
• 看起来这种做法很有希望呢，那么采用这种做法最多要放几个黑颜色的点呢？假设 k 足够大，我们最多放 \lfloor0.5\log_2k\rfloor+1 个点，因为如果我们放两个 1，那么可以等价为 11 占了两位，如果我们被迫放一个 1，那么可以等价为 10 占了两位（或者到了结尾），总之：常数被卡到了 1.5，我们可以等着做出这题了。
• 这个做法的实现稍微麻烦一点，不过代码并不因此超过 1\text{KB}：代码，信息复杂度 O(\log k)，更具体地，它需要 89 个数来表示 2^{59}+2^{58}-1，理论得分 100。