To do list #1 : CEOI 2019

· · 个人记录

Building Skyscrapers

题目链接

注意到要求字典序最大是从 n 到 1 的字典序最大，这与我们常规的对字典序的要求不太一样，是一个提示，暗示我们应该反过来做。

把建造变成拆除，考虑拆除顺序的字典序最大即可。

显然存在方案的充要条件是所有大楼均连通，那么在拆除过程中，一旦发现图不连通，则无解，说明刚才拆错了。

那么一栋大楼能够被删除当且仅当：

考虑这个东西该怎么判。

先判断前者。我们不妨把整张网格图建出来，有尚未被拆除的大楼的点标记为黑点，反之为白点。最外层的白点是可以到达无穷远处的，与可以到达无穷远处的白点四连通的点是可以到达无穷远处的。

可以用并查集来合并，不过其实没必要。因为我们注意到每次将一个黑点变成白点的时候一定只会将至多一个白色连通块合并到能到达无穷远处的连通块上，而不会对其他白色连通块产生影响，每个点的合并次数都是 O(1) 的，所以可以直接暴力合并。

可是这个平面是 10^9 \times 10^9 的，真把图建出来时空都要炸了。不过发现黑点个数只有 n 个，我们可以只添加所有黑点以及黑点周围的 8 个点，这样点数就是 O(n) 级别的了。

然后考虑后者如何判断。无向图动态删点维护连通性，这东西做不了一点。不过好在这道题比较特殊，是在一个网格图上，那么只需要判一下周围八个点的状态即可。

一个点是割点有且只有两种情况：

A*B
A#B
A*B

A*B
*#B
BBB

其中 # 代表这个点，* 代表一个白点，A 和 B 对应两个不同的区域。

如果两个 * 在同一个连通块里，且 A 区域和 B 区域都至少有一个黑点，那么这个 # 是割点。

实际上情况有六种，第一种情况旋转后总共有两种情况，第二种情况旋转后总共有四种情况。我们可以预处理打表把这六种情况都记录下来，这样在代码实现上更加简洁。

注意到每次只有删除的点的周围的八个点的状态可能会变，这确保了我们的操作数是 O(n) 的，可以直接暴力大模拟来解决。

Dynamic Diameter

题目链接

带权树求树上直径，可以使用树形 DP 来做。现在边权动态变化，考虑使用动态 DP 来做。

首先一个 trick 是边权不好处理，我们转换成点权来做。把每条边的边权挂在儿子节点上当做点权即可。

设 f(i, 0 / 1) 表示 i 子树内从 i 出发的最大值 / 从任意点出发的最大值。首先考虑静态时是怎么做的：

f(i, 1) = \max_{x \in son_i}(f(x, 0) + w(x) + f(i, 0)) f(i, 0) = \max_{x \in son_i}(f(x, 0) + w(x))

接下来边权带修，考虑如何 DDP。

首先按照 DDP 的标准套路，我们把 i 的儿子拆成 i 的重儿子和 i 的其他所有轻儿子两部分，令 h_i 表示 i 的重儿子，g(i, 0 / 1) 表示 i 的所有轻儿子的贡献，有：

f(i, 0) = \max(f(h_i, 0) + w(h_i), g(i, 0)) f(i, 1) = \max(f(h_i, 0) + w(h_i) + g(i, 0), g(i, 1))

定义一种广义矩阵乘法，用加法代替原本矩阵乘法中的乘法运算，用 \max 运算代替原本矩阵乘法中的加法运算，考虑构造转移矩阵。

\begin{bmatrix} w(h_i) && -\inf && g(i, 0) \\ g(i, 0) + w(h_i) && 0 && g(i, 1) \\ -\inf && -\inf&& 0 \end{bmatrix} \times \begin{bmatrix} f(h_i, 0) \\ f(h_i, 1) \\ 0 \end{bmatrix} = \begin{bmatrix} f(i, 0) \\ f(i, 1) \\ 0 \end{bmatrix}

需要注意的是：树的叶子节点的转移矩阵应该是全 0 的矩阵，不能存在 -\inf，否则转移过程中会出现问题。

Cubeword

题目链接

首先枚举正方形的边长，然后考虑对于某个边长该怎么做。

首先注意到只有角上的字母会重复使用，因此我们可以直接枚举八个角上的字母，然后两两计算贡献即可。

令字符集大小为 |\sum|，复杂度 O(l|\sum|^8)。

考虑怎么优化这个玩意。

注意到对于一个顶点，它会且仅会与三个顶点共用一条边。如果我们确定了另外三个与它共用一条边的顶点填什么并计算出了贡献，那么这个顶点填什么都无所谓了。

这样就可以减掉一个顶点的枚举，降低一维的复杂度。

那么最多可以减掉几个顶点的枚举呢？

注意到，只需要枚举正方体底部正方形对角线上的两个点和顶部正方形另一条对角线上两个点即可，剩下四个点都与刚才枚举过的某三个点共用一条边。

于是复杂度被降低到了 O(l|\sum|^4)。

Amusement Park

题目链接

考虑一个 DAG 在边全部反转之后仍然会是 DAG，那么如果有一种反转 x 条边的方案，就一定有一种与之对应的反转另外 m - x 条边的方案。所以我们只需要求出总方案数，然后乘上 \dfrac{m}{2} 即可。

那么怎么求总方案数呢？

考虑状压 DP，设 f(S) 表示 S 点集的导出子图反转之后变成 DAG 的方案数。

我们知道 DAG 里一定有一些入度为 0 的点，删除这些入度为 0 的点后，我们会得到一个小的 DAG。考虑枚举这些入度为 0 的点，然后可以从小 DAG 转移。

枚举 S 的子集 T，将 S 拆成 T 和 S - T，当 T 是一个独立集的时候，f(S) 可以从 f(S - T) 转移而来。

但问题是这样做会算重复。比如我们枚举的一个合法的 T 是 0011，那么 0010 和 0001 一定也是合法的，这样同一种方案就被记重了。

考虑一个老生常谈的容斥，当 T 中点的个数是奇数个时，令它有 1 的贡献，当点的个数是偶数个时，令它有 -1 的贡献。

于是做完了，最终复杂度 O(3^n + n^22^n)。

Magic Tree

设 f(i, j) 表示 i 的子树在第 j 天前被全部割掉的最大收益，考虑 i 位置的果实贡献。

如果不收割 i 位置的果实，有 f(i, j) = \sum_{x \in son_i} f(x, j)。

如果收割 i 位置的果实，有 f(i, j) = w + \sum_{x \in son_i} f(x, d)。

二者取 \max 即可。

暴力转移，复杂度 O(nk)，考虑优化。

考虑线段树合并。

发现收割 i 位置的果实时，这个贡献一定是个定值，计算出这个定值，令其为 x，扔到线段树上做区间推平下界。

区间推平下界的具体做法是：维护每个区间的 \min 和 \max。暴力 + 剪枝，当 \max 小于等于 x 时整块修改，当 \min 大于等于 x 时不用修改。这是个比较老套的套路了，复杂度是正确的。

加法操作的标记很难下传，标记永久化即可。

Scissors and Tape

计算几何 + 大模拟，不会且懒得写，摆了。