有一些阴间题就咕咕了。

题目列表

美食家

矩阵快速幂

由于路径长度,因此可以将一条路拆成若干条单位长度的边。

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

暴力做的复杂度是的。不太能过。

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

这样时间复杂度就优化到了

命运

树形 DP 线段树合并

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

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

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

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

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

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

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

因此设表示的子树,且的路径上被标记的边的深度最大值是,只考虑子树中的边的满足所有限制方案数(也就是说总方案数是的)。

的儿子转移到时先枚举这条边是否被标记,然后转移即可:

其中表示结点的深度。

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

时间复杂度

制作菜品

背包 结论 构造

首先若,那么很容易构造出方案。方法是把所有的调整成的倍数。

若存在会比较难处理。但注意到本题的范围特殊:

时可以证明一定存在解。证明的方法是找到中的最小值,设为。然后通过平均数放缩之类的方法证明最大值一定,即最大值加上最小值一定。这样你就可以凑出一个菜品,消掉最小值,然后就变成了一个规模减一的子问题(归纳法)。

对于的情况,我们有一个奇思妙想:将这堆原材料分成两组,使得,即拆成两个形如的问题。

如果拆不了那么无解。

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

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

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

总时间复杂度可以做到

超现实树

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

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

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

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

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

深度为的基树构成的集合记作

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

一棵树是基树,当且仅当对于其中的任意结点满足下列条件之一:

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

基树的性质体现在

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

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

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

因此问题转化为:给出的基树能否替换出一个

基树的形态酷似一条链,它的分布呈树形结构。基树的非叶子结点有类:

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

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

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

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