SP186 LITELANG - The lightest language 题解

▶

INFO 题意

给定 个字符，第 个字符的代价是 ，现在你需要用这 个字符构造出 个互相不为前缀的字符串，使得总共的权值和最小。字符串的权值是所有字符的权值和。

我们发现这个等价于在一棵无限大的 Trie 树上找到 个叶子节点，使得叶子节点的深度之和最小。

一个简单的想法是每次选择最浅的叶子，将其视作非叶子节点，把 个儿子加入候选集合，如果叶子个数大于 的话就选前 小的。

你会发现这个显然是错的。因为你可以直接令 ， 选择一个比较小的数。此时选择若干个 显然优于直接选择 。

但是我们在这个时候可以继续贪心，继续分裂最小的叶子，插入其所有的叶子，每次选择前 小的。

重复进行 次分裂取最小值。你会发现这就对了。复杂度是 。

我们现在考虑证明一下。首先直接考虑叶子比较难考虑，我们不妨来考虑非叶子（树的内部节点）有几个。

下面不妨考虑权值数组 是事先排好序的，下文说的第 个儿子也是指的权值第 小的儿子。

引理 ：令 表示在所有有 个内部节点的解中的最优解，则 的所有内部节点一定是深度最小的 个。给第 小的节点编号 ，相同大小顺序随意，但是保证编号唯一。

证明考虑比较选择深度最小的 个内部节点的解 和不选择的解 。考虑找到一个只在 中有的内部节点，将这个子树剪下来，拼到只在 中有的内部节点上（可以证明一定存在这样的节点可以拼上去，因为树的深度单调，前 小一定构成包含根节点的一个子树），此时由于 的内部节点是前 小的，子树的整体深度会减少，因此子树里的字符串代价会减少。

引理 ：选择了最小的 个节点之后，选择代价最小的 个叶子就是 的答案，如果有多个相等的，那么我们就取父节点编号更小的。这样构造出来的树是唯一的。

原因和上面一样，你可以把大的叶子剪下来拼到小的叶子上。

引理 ：最优解是 中的一个。

显然。考虑反证，数一数内部节点个数，替换成 一定更优。

我们第 次构造出来的树就是 。

引理 ：在 的前提下，定义合法树为：所有的 个钦定为内部节点的点至少有两个儿子的树。则在合法树中一定存在一个最优解。

这个也比较显然。对于一个没有儿子的被钦定为内部节点的点，把这个点取消钦定为内部节点会得到一样的解法。对于一个只有一个儿子的内部节点，我们把这个儿子直接接到当前点上深度变小，答案更优。

引理 ：最优解最多不超过 个内部节点。

因为 个内部节点显然是非法树。此时你有 个给内部节点增加度数的机会，但是你有 个节点要增加，每个节点是 个增加不过来。

因此我们的算法是正确的。

此时还有一个小优化可以把复杂度优化成 。

引理 ：考虑编号为 的节点的第 个叶子，如果 ，那么这个叶子永远不会是答案。

因为内部节点不超过 个，总共的节点不会超过 ，此时已经有 个比这个叶子小的节点了，这个节点无论如何都不可能在最优方案中。

考虑这样一张无限大表格辅助理解，假设 。

对应的是这张图，之后的节点就不画了：

列 行表示的就是第 个节点的第 个叶子，格子里填的是深度。容易发现一个格子左上角全是小于这个格子的元素，因此 的格子就不需要考虑。

枚举行号，可以发现，候选节点一共是 ，是 级别的。

因而只需要考虑 的节点就可以把该算法复杂度优化到 的。

之后还有一些优化。其中一个优化就是如果某次分裂之后权值增加了，那么算法就可以立刻停止了。我们只需要证明答案关于 是单峰的即可。

证明比较复杂。一个感性的理解是，之后想要替换掉原先前 小的节点会越来越困难，而每次新加入的节点会越来越深，想要代价变小就会越来越困难。

引理 ：在有至少 个叶子之后， 权值单谷。

下面我们将分成若干步来证明。

引理 ：满足 是合法树的 是一个区间。

显然区间左端点就是第一次有 个叶子的时刻。

我们只需要证明， 一旦不是合法树，那么 也不合法。

首先考虑使得 非法的那个节点，这个节点最小的儿子是 ，假设此时 的叶子集合为 ，显然有任意 ，以及 。

此时增加了一个内部节点 ，此时，不妨假设 的儿子中 对应的儿子是 。显然 ，这是因为 的父节点比 先被钦定为内部节点，因此 的父节点深度更小，由于儿子是对应的，连向父亲的边的长度也是相等的，因此 深度不会比 浅。另外 的父亲比 的父亲先选择，因而编号更小。因此 无论如何都会比 先加入。

此时 中还剩下了 个元素，这些元素比 小，因此也比 小（注意这里的”小“是先比深度，再比父节点编号）。加上 自己有 个元素比 小了，因此 不可能在 中， 的父节点会使得 是一个非法树（请注意 选择的是和 对应的节点，由于 父亲使得 非法，因此这两个节点要么都是最小的叶子，要么都是次小的叶子）。

下面我们将这个区间记作 。

引理 ：对于 的 ，其权值单调递增。

考虑此时 中删除了 。由于我们证明了 会在 中使得 非法，因此 下面最多 个叶子会进入 。

考虑是谁替代了 ：

• 是 下面的第一个叶子。此时显然答案会增加。
• 不是 的叶子。根据我们 的定义可以得知，这些叶子权值均大于 中点的权值。因此答案也会增加。

引理 ：， 权值单谷，并且下凸。

不妨考虑从 构造 （， 合法）。

首先，假设 从 中被删除作为内部节点，则 的第一个叶子一定在新的 中。否则 会使得 非法。由于根据我们的定义，所有不在 中的其它叶子权值必然大于 中元素，因此这些元素可以直接不用考虑，我们只需要考虑新的节点加进来了哪些叶子即可。

因此，我们分两步构造出 ：

• 选择节点 ，钦定 为内部节点，并将 的最小叶子加入 。这个操作会使得代价增加固定的 。
• 从小到大考虑 剩下的所有叶子 。找到 中深度最大的叶子，如果其深度大于 ，用 替换它。

请注意操作 至少发生一次，否则 会只有一个叶子， 非法，并且操作之后 中的最大值显然会变小（因为被用更小的值替换了），因此从 到 时 中的最大值显然会减少。

因此每次的代价就是 减去替换时减少的代价。

接下来我们考虑 这三棵树。

考虑 到 的过程和 到 这部分的代价变化。显然 就直接抵消掉了。

考虑第二个操作。假设 中替换掉 中元素的最后一个叶子是 。

因为替换了 中 大的元素，因此新的 中的第 大元素肯定小于 中的第 大元素（），因为这些元素被替换之后，浮上来成为新的第 大的肯定是更小的元素。

如果现在考虑从 到 这个过程，用 的叶子来替换 中的元素。

• 如果 ，那么此时不仅替换的代价增加了，第 大元素还减少了，因此这部分的代价肯定是小于 替换 中的第 大元素的。
• 如果 ，这显然不可能发生。因为 深度比 小还没有替换掉，因此 也不可能替换掉。之前替换的叶子 的深度显然也小于 。

因此，你的变化是单调递减的，因此自然也是单谷底。一旦答案的变化为正了，此时就可以直接停止了。

因此我们的算法是正确的。

此外还有一些卡常技巧。

我们不暴力加入所有 的节点，而是在每次分裂之后，直接加入最小的叶子，依次考虑之后的每个儿子，尝试替换掉原来叶子中最大的节点，如果不能替换了则停止，就像我们从 构造出 时的那样。

注意到某个叶子在父节点被钦定为内部节点的时候如果没能替换掉原来的叶子，那么这个节点在之后就没有用了。

考虑在构造的时候这个叶子何时会加入。唯一会加入的时候是，在当前钦定为内部节点的 的最小叶子 连前 小都进不去的时候，此时这个叶子才有可能变成前 小。

但是此时不论是拿这个叶子替换还是直接拿最小的儿子替换，代价显然会增加，算法会在这里直接停止。

另外一个技巧就是，假设权值很不平均，一开始加入的节点会很快被替换出去，这样是很浪费的。

考虑我们有哪几种方式新增一片叶子。

• 加入一个父亲已经钦定为内部节点，但是当前节点尚未加入成为叶子的节点。
• 将一个叶子钦定为内部节点，加入第一个和第二个儿子。

第一种的代价是 ，第二种则是 。我们先贪心的增加 个叶子（每次选择代价最小的操作选择 次），之后尝试用当前代价最小的操作替换掉当前深度最大的叶子，如果当前最小代价的操作代价大于深度最大的叶子的深度就停止。

具体的，我们分开维护当前代价最小的操作 和操作 。最小的操作 只需要使用 std::set 维护当前的叶子即可。

但是进行一次操作 之后可能解锁 个新的操作 （即当前节点的第 个到第 个儿子），不过我们发现，只有当第 个儿子通过操作 加入成为叶子之后，第 个儿子才有可能通过操作 加入成为叶子（这是因为父亲深度相同但是第 个儿子的 更小）。因此我们在第 个儿子对应的操作进行之后再把第 个儿子加入候选集合。候选集合使用堆维护即可。

不难发现，假设最终进行了 次操作 ，这样构造出来的就是 。因为这个算法实际上和我们从一开始依次构造是等价的，我们选择了深度最小的 个节点作为内部节点并且选择了深度最小的 个叶子。

另外一方面，在至少有 个叶子之后，用代价最小的叶子替换掉深度最大的叶子这个行为显然是导致代价减少的，因此不会跨过低谷。

最后我们再切换回原算法继续跑得出正确答案。

注意加入这个优化之后其实并不是很容易跑满，实际上 应该是可以比较容易的通过的（有卡满的数据发我一份谢谢）。

此时还有一个优化，可以将 优化成 。我们注意到，在堆中的第 种叶子（指的是，父亲的第 个儿子）的父亲的编号实际上是一个连续的区间。

从引理 的证明不难看出，如果第 种叶子在某次没有能替换掉 中的叶子，在后续的所有替换中第 种叶子都无法替换。而每次选择的都是最小的叶子从 中删除，因此我们只需要维护这 个区间的左端点和右端点即可。复杂度 。

在我们证明了单峰性之后，还有一种做法，就是你直接三分，找到这个谷底。实际上整数上的三分可能会遇到一段平坦区间的问题，但是我们在刚刚已经证明了顶点前权值严格递减，顶点后权值严格递增，因此我们只需要二分找到最后一个差分非正的位置即可。

check 的时候依旧考虑我们的那张表格，假设现在要求 个内部节点时的答案，我们截取前 列，并且先弹出前 小的元素（这些元素被钦定成为了内部节点），在剩下的矩阵中求前 小即可。 由于每一行都是递增的，因此容易使用多路归并的技巧维护一个堆在 的复杂度内来解决。

后续可以使用分组二分的技巧优化到 。

进一步的，注意到大多数时间都浪费在了二分的 check 上面了，我们可以考虑用类似单次 check 的多路归并的做法先把前 个元素预处理出来，按照父亲节点排序，然后使用分组二分。将这 个父亲分成 组，每组不超过 个有效叶子。

二分先求出来最优解在哪一组，复杂度是 次 check 乘上 的单次 check 复杂度。

此时这一组父亲节点中只有 个叶子，我们继续跑一遍原来的算法就可以使用 次堆操作就可以求出答案。

Choi 和 Golin 在论文《Lopsided Trees: Analyses, Algorithms, and Applications》更是将复杂度做到了 ，但是过于复杂，这里不再讲解。

上述做法便可以通过加强版数据。

参考资料

• 不知道哪里来的题解。
• 不知道哪里来的另一篇题解。
• 论文《PREFIX CODES: EQUIPROBABLE WORDS, UNEQUAL LETTER COSTS》

如果你知道题解的来源的话，请提醒我标注，感谢。