题解：P9838 挑战 NPC IV

· · 题解

题面

总优美度 Val 定义为所有区间的优美度之和。一个位置 i 上的数会被包含在 i(n-i+1) 个区间中，因此

Val=\sum_{i=1}^nf(p_i) \cdot i(n-i+1)

记权重 w_i=i(n-i+1)。问题变成：把 f(1),f(2),\cdots,f(n) 这 n 个值重新排列，放到 w_1,w_2,\cdots,w_n 上，求第 k 小的 \sum f\cdot w。

观察 f

因为

f(x)=1 + \log_2 \operatorname{lowbit}(x)

所以满足 f(x)=y 的 x 的个数为

cnt_y=\left\lfloor \frac{n}{2^{y-1}} \right\rfloor-\left\lfloor \frac{n}{2^{y}} \right\rfloor

层数 L=\lfloor \log_2 n \rfloor+1。

所以有 n < 32，L \le 5，记好了，之后要用。

k=1

我们有一个很显然的贪心：把大的 f 放到小的 w 上最优。所以从最大层开始，依次填入权重升序序列。

设前缀权重和函数

sum(p)=\sum_{\text{前 }p\text{ 个最小权重}} w

则

\min Val=\sum_{y=L}^1 y \cdot (sum(r_y)-sum(l_y-1))

其中 l_y,r_y 是第 y 层对应的权重区间。

计算 sum(p)

设 q=\left\lfloor \frac{p}{2} \right\rfloor，r=p \bmod 2。

\begin{aligned} sum(p)&=2\sum_{i=1}^q i(n-i+1)+r(q+1)(n-q)\\ &=2(n+1)\sum_{i=1}^q i-\sum_{i=1}^q i^2+r(q+1)(n-q) \end{aligned}

关键性质

最小总优美度对应的排列数至少为

\prod_{i=1}^L cnt_i!

因为固定层后，第 i 层的 cnt_i 个数可以任意放到该层的 cnt_i 个位置上，有 cnt_i! 种。而且权重相同的层可以交换。

最小总优美度对应的排列数只会多不会少。

代入计算，发现 n=30 时

\begin{aligned} cnt_1&=30-15=15\\ cnt_2&=15-7=8\\ cnt_3&=7-3=4\\ cnt_4&=3-1=2\\ cnt_5&=1-0=1 \end{aligned}

所以

\prod_{s=1}^{5} cnt_s! =15!\cdot 8!\cdot 4!\cdot 2!\cdot 1!

其中

15!=1\,307\,674\,368\,000 8!=40\,320,\qquad 4!=24,\qquad 2!=2,\qquad 1!=1

因此

\prod_{s=1}^{5} cnt_s!=2\,530\,820\,664\,852\,480\,000

约为

2.5308\times 10^{18}

最小总优美度对应的排列数已经超过 k 的上界 10^{18}。所以当 n\ge30 时，第 k 小一定就是最小值。

因为有 n < 32，L \le 5，状态只有 5 个维度。定义 dfs(_1,_2,_3,_4,_5,s) 为各层还剩 \_1,\cdots,\_5 个数，目标剩余优美度为 s 时，有多少种层分配方案。转移直接暴力枚举这一位放哪一层即可。再从小到大枚举得出答案。

优化


::::