Codeforces Round #752 Extreme Extension 题解 (Java/C++)

题解

显然,我们不需要考虑操作顺寻。因此我们直接考虑对某一个数会如何执行若干次操作。
同样是显然的,经过若干次操作后,我们希望拆分出的数字尽可能平均。
以4为例,如果我们要将4拆成2个数,一定是拆成2和2,而非1和3。因为如果拆成1和3,一方面会迫使前面的数字拆分成更小的数字,二方面会使最大值增大。

于是我们发现,对于任意的$a_i$,经过若干次拆分后的值只有$\sqrt a_i$种可能。
以$a_i=100$为例,假设$a_{i+1}=40$。我们不会将$a_i$拆分成$[20, 40, 40]$,而是拆分成$[33, 33, 34]$。
再以$a_i=100$,$a_{i+1}=3$为例。显然,我们会将其拆分为32个3和2个2,总共34个数。而不难发现,同样的以3为最大值,2为最小值,还有拆分成35个数的方法,但是其实我们只关注最小的拆分。

于是对于$a_i$,我们维护拆分后的最大值与拆分所需的操作数之间的映射。我们分两块来维护:

  1. 令m表示操作次数,对于$m \leq \sqrt a_i$的,$map[\left\lceil \frac{a_i}{m} \right\rceil]=m-1$。
  2. 对于$m>\sqrt a_i$的,令k表示若干次操作后剩下的最大值,显然有$m=\left\lceil \frac{a_i}{k} \right\rceil$,且$k<\sqrt a_i$。于是有$map[k]=\left\lceil \frac{a_i}{k} \right\rceil$

因此对于每一个$a_i$都可以在$O(\sqrt a_i)$的时间内完成映射。
我们用$count[a_i][j]$来表示将$a_i$拆分成最大值为j,需要多少步。这里需要注意的是,j并不连续。

有了这个映射,我们就能给出如下的dp定义:dp[i][j]表示以$a_i$结尾的子串,拆分后最后一位为j时(也就是最大值为j时),extreme values的总和。同样的,需要注意,j并不连续。
于是有:$dp[i][j]=count[a_i][j] \cdot i \cdot dp[i-1][k]$,其中k是dp[i-1]中,存在的,且是小于等于j的,最大可能的值。同时,因为以$a_i$结尾的子串共有i个,因此count[a_i][j]需要乘以i。

而最终的答案就是$\sum dp[i][a_i]$。

最后,同时考虑内存开销和时间开销,我们要做以下优化:

  1. 因为dp[i]只与dp[i-1]有关,因此显然是可以应用状态压缩。
  2. 虽然$count[a_i][j]$和$dp[i][j]$中的j并不连续,但我们发现,在计算count和dp过程中,j不论是在查询时还是写入时,都是有序的。因此,我们可以使用数组和下标而非map来完成记录和查询。使用map的复杂度为:$O(n\cdot \sqrt a \cdot log(\sqrt a))$,而不使用map的复杂度是:$O(n\cdot \sqrt a)$。

代码

Java

Submission #134567923 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134568064 - Codeforces
Codeforces. Programming competitions and contests, programming community