NOI2020 补题记录

有一些阴间题就咕咕了。

题目列表

美食家

矩阵快速幂

由于路径长度$\le 5$，因此可以将一条路拆成若干条单位长度的边。

本题看起来很矩阵快速幂，难度在于有$k$次美食节。

暴力做的复杂度是$O(k(nw)^3\log T)$的。不太能过。

注意到本质上答案是一个向量左乘若干个矩阵得到的。矩阵乘法的复杂度是$(nw)^3$的，但是向量和矩阵的乘法是$(nw)^2$的。这启发我们用$(nw)^3\log T$的时间预处理转移矩阵在$2^k$处的矩阵幂，在计算答案的过程中做$\log T$次向量乘矩阵即可。

这样时间复杂度就优化到了$O(k(nw)^2\log T + (nw)^3\log T)$。

命运

树形 DP 线段树合并

首先这题看起来就很树形 DP。然而状态空间稍显复杂，需要转化。

首先我们发现不是所有的限制都是有用的。包含关系的限制都可以去掉。这样我们可以预处理出$a_u$表示$u$到其祖先$a_u$的边中至少有一条边会被标记（相当于$n$个$(a_i, i)$的限制）。$a$等价于题目中给的$m$个限制。

为了划分子问题，我们站在子树的角度考虑问题。考虑结点$u$及其子树。

A. 完全包含在$u$子树内的限制可以划分到关于$u$的问题上。

B. 我们不关心与$u$的子树无交集的限制。

C. 有一些限制一半在$u$子树内，另一半在$u$子树外，它们的归属有些模棱两可。

注意到 C 类的限制与$(a_u, u)$必然相交且不包含。因此如果我们确定了$(a_u, u)$路径上的边的标记情况，就足以表达 C 类的限制受到子树外的影响。更进一步，我们只用关心$(a_u, u)$中被标记的深度最大的边即可。

因此设$f(u, i)$表示$u$的子树，且$(a_u, u)$的路径上被标记的边的深度最大值是$i$，只考虑$u$子树中的边的满足所有限制方案数（也就是说总方案数是$2^{|T_u| - 1}$的）。

从$u$的儿子$v$转移到$u$时先枚举$(u, v)$这条边是否被标记，然后转移即可：

$$f(u, i) = \prod_{v} f(v, i) + f(v, d_v) \quad (d_{a_u} < i\le d_u)$$

其中$d_u$表示结点的深度。

然后线段树合并优化即可。

时间复杂度$O(n\log n)$。

制作菜品

背包 结论 构造

首先若$\forall i, \,d_i\ge k$，那么很容易构造出方案。方法是把所有的$d_i$调整成$k$的倍数。

若存在$d_i < k$会比较难处理。但注意到本题的$m$范围特殊：$m\ge n - 2$。

当$m \ge n - 1$时可以证明一定存在解。证明的方法是找到$d_i$中的最小值，设为$x$。然后通过平均数放缩之类的方法证明最大值一定$\ge k - x$，即最大值加上最小值一定$\ge k$。这样你就可以凑出一个菜品，消掉最小值，然后就变成了一个规模减一的子问题（归纳法）。

对于$m = n - 2$的情况，我们有一个奇思妙想：将这堆原材料分成两组$A, B$，使得$\sum_{i\in A} d_i = k(|A| - 1)$且$\sum_{i\in B} d_i = k(|B| - 1)$，即拆成两个形如$m = n - 1$的问题。

如果拆不了那么无解。

为啥无解：这个要稍微绕一下。简单来说

1. $m = n - 2$无法直接按照$m = n - 1$做的，必须拆着做。
2. 拆着做的话假设拆成若干个形如$m = n - x_i$的不可再拆子问题。
3. 且$x_i$中必有一个数大于$1$，不然就会拆成两$m = n - 1$的问题。
4. 结合$2, 3$，这个问题就既不能拆也不能做，就无解了。

拆分问题就是个经典的01背包问题，用 bitset 优化一下即可。

总时间复杂度可以做到$O(\frac{n^2k}{\omega} + n + m)$。

超现实树

本题的思考角度稍显刁钻。

本题要判断树的集合是否完备，为此我们从【什么树无法被替换】入手。

但实际上任何树都可以用单个结点的树替换得到，这就变得没啥可分析的了。这说明我们思考问题的角度不够本质。

树的集合完备，本质上等价于：存在一个数$x$，使得深度$\ge x$的所有二叉树都能被替换得到。

因此判断集合是否完备，与树的深度有关。因此我们需要研究【哪些树无法被与它深度相同的树替换得到】，我们将这些树称作作基树。

深度为$n$的基树构成的集合记作$B_n$。

这样我们会发现一些有趣的事情。

一棵树$T$是基树，当且仅当对于其中的任意结点$u$满足下列条件之一：

• $u$是叶子结点
• $u$只有单个儿子
• $u$儿子中至少一个是叶子结点

基树的性质体现在

1. 发现深度为$n$的非基树均可由$B_n$中的某个树替换得到。
2. $B_{n - 1}$可以替换得出$B_n$且仅$B_{n - 1}$可替换得出$B_n$。换言之任意的深度为$n - 1$构成的树的集合如果不完全包含$B_{n - 1}$，那么它就无法替换得出$B_n$。证明显然。

因此树的集合完备，本质上等价于：存在一个数$x$，使得$B_x$中的树都可以被替换得到。

由基树的性质，我们发现非基树是无用的。所以给出的$m$个树中我们只保留基树。

因此问题转化为：给出的基树能否替换出一个$B_x$。

基树的形态酷似一条链，它的分布呈树形结构。基树的非叶子结点有$4$类：

• 没有左儿子
• 没有右儿子
• 左儿子是叶子
• 幼儿子是叶子

这样可以用一棵四叉树表示不同深度的基树构成的集合！

（注意：基树在四叉树上不一定是一条链。例如条件 3 和 4 可以同时满足）

稍微思考可以发现，我们可以在四叉树上定义类似的完备与否，通过简单的 DFS 来判断整个四叉树是否完备。