perm 烫发
WeLikeStudying · · 题解
- 以前作者的措辞可能不太恰当,但是我觉得这是能够理解的,毕竟作者早已退役,
\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 。