ARC104

· · 个人记录

D

有几个可重集满足以下条件：

  • 元素 \in [1,n]。
  • 平均数为 x。
  • 每个元素出现次数 \le k。
$n,k\le 100

设 f(i,j) 表示选择一些 [1,i] 的数构成可重集，每个数出现 \le k 次，和为 j 的方案数。f(i,j) 这个表可以 O(n\times V_j)=O(n^2k^2) 时间复杂度内预处理（完全背包类似的转移）。

当时场上不会做，，，就是因为不会预处理 f(i,j) /tuu

那么平均数为 i 就是要可重集中 [1,i-1] 中 ( i 减去该数 ) 的和等于 [i+1,n] 中 ( 该数减去 i ) 的和。

前一个问题，因为 x,i-x 在 [1,i-1] 内为双射，所以就等价于 [1,i-1] 中取出一些数，这个数的和。后一个问题，全部减去 i，等价于 [1,n-i] 中 取出一些数，这个数的和。

那么就是 f(i-1),f(n-i) 的点积！

其实整个题还挺 straight forward。

E

长度为 n 的序列 a，整数 a_i 在 [1,r_i] 随机，求序列 a LIS 期望长度。

n\le 6,r_i\le 10^9

考虑枚举相对大小，就 变 成 了 [APIO2016] 划艇。

为什么当时场上不会做？？？

F

长度为 n 的序列 a，整数 a_i 在 [1,r_i] 随机，设 P_i 为 i 前面最后一个比 i 大的位置（没有则为 0），问 P_i 有几种可能。

n\le 100,r_i\le 10^5

注意到 r_i 没什么用，只要 r_i 足够大，P 几乎是任意的，故感觉是 P 会限制 r 至少是多少，如果给的 r 太小，这个 P 就不行。

考虑给定一个 P，如何判断其每个位置 r_i 最小是多少（后面会证明 a_i 能同时取到最小）。a_i 有哪些限制？

注意到，如果有限制 a_j\le a_i，则以 P 为父亲数组，建 [0,n] 的树，j 的子树内都自动全 \le a_i 了。这就是说，第二个限制可以写成：

  1. 将 P_i 的儿子从小到大排序，i 之前的兄弟 j 要满足 a_j\le a_i。

考虑如下贪心算法，来安排 a_i：

显然这样所有 a_i 都取到下界。

注意到这棵树中每棵子树都是一段区间（即单调栈题中的管辖范围），所以可以区间 dp。

设 f(l,r,x) 表示 [l,r] 区间，这棵树是以 l 为根的树，其中 l 上安排的最小 a 值为 x 的区间内 P 数量。要求 x\le r_l。

设 g(l,r,x) 表示 [l,r] 区间有很多棵树，最右边一棵树的根上最小 a 为 x 的区间内 P 数量。

下面这个转移有点容易想错，要认真看一下。

f(l,r,x)=g(l+1,r,x-1)\ (x\le a_l) g(l,r,x)=f(l,r,x)+\sum_{i=l}^{r-1}\sum_{a,b[\max(a,b)=x]}g(l,i,a)f(i+1,r,b)\ (a\le a_{i+1})

注意，只要左右分别 \le x 就可行了，不一定 a\le b（这里只是“最小”，整体平移仍然能行）

使用前缀和优化，O(n^4)。