标签：dots frac 题解可以 ICPC 2021 text 顶点我们

ICPC 2021–2022，NERC – 北欧欧亚总决赛题解翻译

圣彼得堡，阿拉木图，巴尔瑙尔，明斯克，埃里温，2022年4月13日

问题 A. 可接受的地图 (Admissible Map)

问题作者和开发者：Ilya Zban

我们称形如“RLRL...RL”的任何字符串为平凡字符串。

引理

任何非平凡字符串最多只能有一个构成可接受地图的方式。

证明

考虑字符串 $s_0s_1 \dots s_{|s|-1}$，令 $i$ 为第一个偶数，满足 $s_i s_{i+1} \neq "RL"$。可以有以下几种情况：

$s_i = "L"$：字符串无法构成可接受的地图，因为第 $i$ 个符号要么位于矩阵的左边缘（其边缘没有指向任何其他单元格），要么指向左边的“RL”，导致相邻的“L”有两个传入边（或指向矩阵外部）。
$s_i = "U"$：字符串无法构成可接受的地图，因为第 $i$ 个符号要么位于矩阵的上边缘（其边缘没有指向任何其他单元格），要么指向某对“RL”，而它们应相互匹配。
$s_i = "R"$：由于 $s_{i+1} \neq "L"$，第 $i$ 个单元格唯一的传入边只能是“U”。我们可以注意到它只能是字符串中的第一个“U”，因为否则第一个“U”会指向矩阵外或某个“RL”对。因此，如果 $s_j$ 是最左边的“U”，字符串可以构成为一个 $j-i$ 的地图。
$s_i = "D"$：假设 $k = i$ 且 $s_{i+1} \dots s_k = "LLL..L"$。子串 $s_i \dots s_k$ 应位于矩阵的同一行，由于 $s_{k+1} \neq "L"$，根据上述相同的论点，我们可以看到字符串中的第一个“U”应指向 $s_k$。因此，字符串只能构成为一个 $j-k$ 的地图。

因此，任何非平凡子串 $s_l s_{l+1} \dots s_r$ 的矩阵形状 $n \times m$ 仅由第一个“U”的位置决定。我们可以计算一个数组 $m_l$，意味着任何子串 $s_l s_{l+1} \dots s_r$ 应构成 $r - l + 1$ 个 $m_l \times m_l$ 的矩阵。这个数组可以直接从证明中在线性时间内计算出来。

使用 $m_l$，我们可以迭代所有 $r = l + t \cdot m_l$（对于所有 $t$），并检查所有子串 $s_l s_{l+1} \dots s_r$。我们需要快速确定子串 $s_i \dots s_{i+m_l-1}$ 是否可以是构成的矩阵的顶部、中部或底部行。这可以在 $O(1)$ 时间内完成。

考虑中间行的情况（其他情况类似）。我们想检查是否没有来自 $s_i \dots s_{i+m_l-1}$ 的边超出矩阵，并且每个单元格恰好有一个传入边。首先，我们需要检查 $s_i \neq "L"$ 且 $s_{i+m_l-1} \neq "R"$。可以使用哈希来测试传入边的条件。我们选择一个哈希基数 $x$，并构建四个数组 $a_{c0} \dots a_{|s|-1}$（其中 $c$ 为“ULDR”）：

如果 $s_j = "U"$，则 $a_{Uj} = x^j$；
如果 $s_j = "D"$，则 $a_{Dj} = x^j$；
如果 $s_j = "R"$，则 $a_{Rj} = x^{j+1}$；
如果 $s_j = "L"$，则 $a_{Lj} = x^{j-1}$；
所有其他值为零。

然后我们可以看到，如果每个单元格 $s_i \dots s_{i+m_l-1}$ 都有一个传入边，则公式成立：

\[x^{m_l} \sum_{t=i-m_l}^{i-1} a_{Dt} + \sum_{t=i}^{i+l-1} (a_{Lt} + a_{Rt}) + x^{-m_l} \sum_{t=i+m}^{i+2m-1} a_{Ut} = \sum_{t=i}^{i+l-1} x^t \]

这个检查可以使用预计算的前缀和数组在常数时间内完成。

使用这些检查，我们可以迭代所有非平凡子串，测试它们并补充遗漏的平凡字符串。这个解决方案的复杂度为 $O(s^2)$。

我们还可以进一步注意到，对于每个 $l$，我们迭代所有可能的 $r$ 值，并以 $m_l$ 为步长计算。我们可以统计具有相同 $m_l$ 且 $l \mod m_l$ 相同的所有 $l$，因为我们在这个情况下会重复许多工作。这种优化使我们得到了一个非常快速的解决方案，其最坏情况下的复杂度为 $O(s \cdot \min(\text{cnt}_m, m)) = O(s \sqrt{s})$（其中 $\text{cnt}_m$ 是每个 $m$ 的不同余数 $l \mod m_l$ 的数量）。

问题 B. 预算分配 (Budget Distribution)

问题作者和开发者：Pavel Kunyavskiy

首先解决单一主题问题。如果没有项目分配了太多的钱（超过它们最终应得的，包括未分配的钱），答案就是 0。否则，分配给哪个项目并不重要，只要不给任何项目分配过多的钱。因此，对于已经分配了过多钱的项目集，非最优性函数是线性分数形式，即它的形式是 $ \frac{ax + b}{cx + d} $。此外，很容易检查导数是递增的（它是负数，并逐渐接近零），所以整体函数是分段凸线性分数函数。

要解决整个问题，我们需要找到一种方法来结合不同主题的解决方案。令 $f_i$ 为第 $i$ 个主题的非最优性函数。实际上，我们需要找到函数 $f(x) = \min_{\sum x_i = x, x_i \geq 0} f_i(x_i)$。稍后我们将看到，这个函数也是一个分段凸线性分数函数，有线性数量的部分。

为了使一组 $x_i$ 局部最优，应该不可能找到一对索引 $i$ 和 $j$，使得减少 $x_i$ 一点，增加 $x_j$ 一点可以减少该函数。实际上，这意味着所有左导数都应该小于所有右导数（绝对值更大，因为它们是负数）。直观地看，如果我们考虑分配资金的连续过程，它应该是这样的：将下一个无穷小的资金量分配给具有最小导数的所有主题（那些减少最快的主题），以使它们的导数保持相同。在这一点上，结果函数的导数等于右导数的最小值。

因此，我们通过扫描其导数来构建一个函数。每个主题函数的每一部分在导数范围内都需要添加该函数。我们知道在每个点切换时的导数，并且该部分具有唯一的与该导数相对应的点。唯一剩下的部分是显式找到每个部分的函数，当已知我们将资金分配给哪些主题集时。

为了方便起见，令 $f_i(x) = \frac{a_i^2}{x - b_i + c_i}$。任何具有负导数的线性分数函数都可以写成这种形式。直观地，$b_i$ 和 $c_i$ 是双曲线中心的坐标，而 $a_i$ 只是递减速度的因子。这个形式很方便，因为我们可以简单地忽略 $b_i$ 和 $c_i$，因为 $c_i$ 只会将结果值偏移一个常数，$b_i$ 只会将参数偏移一个常数。因此，我们可以找到形式为 $ \frac{a_i^2}{x} $ 的函数的结果，然后

简单地将其偏移，以使它连接到前一部分的值和导数正确。

对于这些类型的函数，使导数相同意味着 $ \frac{x_i}{x_j} = \frac{a_i}{a_j} $ 对所有 $i$ 和 $j$ 成立。这意味着 $ x_i = \frac{a_i}{\sum a_i} x $。而总函数为 $ \frac{(\sum a_i)^2}{x} $。

问题 C. 连接点 (Connect the Points)

问题作者和开发者：Dmitry Yakutov

解决这个问题有很多方式：

暴力法。取所有给定点的 X 坐标和 Y 坐标，构建一个由九个点组成的“网格”。取出这九个点之间的18条线段，并迭代它们的所有子集。选择最优的子集。
处理不同情况。用标签标记三个点，按 X 坐标排序。然后按 Y 坐标对这些点排序并观察标签。总共有六种不同的排序方式。可以为每种排序方式构建最优的线段集合。
中位点。令 $x_m$ 为所有点的 X 坐标的中位数，$y_m$ 为所有点的 Y 坐标的中位数。中位点 $M = (x_m, y_m)$ 可能在输入点集中，也可能不在。可以证明，你可以用最短的方式将三个点与 $M$ 相连，并输出结果线段集合。
中位线段。令 $x_m$ 为 X 坐标的中位数，$y_{\min}$ 和 $y_{\max}$ 分别是最小和最大的 Y 坐标。取从 $ (x_m, y_{\min}) $ 到 $ (x_m, y_{\max}) $ 的垂直线段，然后用水平线段将三个点与这条垂直线段相连。可以证明，这种线段集合是正确的。

问题 D. 可删编辑 (Deletive Editing)

问题作者：Dmitry Yakutov
问题开发者：Roman Elizarov

这个问题可以通过直接的方法解决。关键观察是，在这个游戏中，字母的调用顺序并不重要。我们只需要知道从初始单词 $s$ 到最终单词 $t$ 的每个字母被调用的次数。

首先，我们计算从 'A' 到 'Z' 的每个字母在单词 $s$ 和 $t$ 中的出现次数。我们将这些计数分别称为 $s_a$ 和 $t_a$（每个字母 a 的出现次数）。
通过这些计数，我们可以计算每个字母需要调用的次数，即对于每个字母 $a$，调用次数为 $s_a - t_a$。
如果对于某个字母 $a$，有 $s_a - t_a < 0$，则答案为“NO”。
否则，有可能答案为“YES”。然而，我们还需要验证字母的顺序是否正确。最简单的验证方式是模拟这个游戏，删除掉每个字母 a 的前 $s_a - t_a$ 次出现，然后将结果与 $t$ 进行比较。

问题 E. 平均划分 (Even Split)

问题作者和开发者：Egor Kulikov

首先，我们找出最短的线段长度，并使用二分搜索确定最小可能的最长线段长度。假设我们需要测试长度为 len 的线段是否足够长。我们可以证明：如果可以找到 n 条长度为 len 的线段（它们可能相互重叠）并覆盖整个 Segmentland，并将它们与 n 个房屋对应，那么可以认为这段线足够长。可以用贪心算法从左到右构造这些线段，并在此过程中覆盖 Segmentland。

接下来，我们还需要找出最长可能的最短线段长度。该部分也可以通过类似的二分搜索来完成，不同之处在于，我们需要找到长度相同但不相交的线段，并使用贪心算法将它们尽量向左放置。

给定这两个长度，即最短的最大线段长度和最长的最短线段长度，我们可以找到一个满足这些限制的分段方案。方法如下：

对于 $i \in 0 \dots n$，我们设定两个参数 $c_i \leq d_i$，表示对应的分界点位于 $c_i$ 和 $d_i$ 之间。我们从左向右计算这些点，从 $c_0 = d_0 = 0$ 开始，并依次计算 $c_{i+1} = \max(c_i + \text{min}, a_{i+1})$ 和 $d_{i+1} = \min(d_i + \text{max}, a_{i+2})$（我们假设 $a_{n+1} = l$）。
对于 $i \in 0 \dots n$，我们设定最终答案 $s_i = \text{ans}_{i-1}$ 和 $f_i = \text{ans}_i$，从右向左计算它们，从 $ \text{ans}_n = l $ 开始。在每一步中，我们会选择 [$c_i, d_i$] 区间中的某个点，它与 $\text{ans}_{i+1}$ 之间的距离位于 $\text{min}$ 和 $\text{max}$ 之间（很容易证明，至少会有一个这样的点）。
这样，我们就得到了一个答案：$s_i = \text{ans}_{i-1}$，$f_i = \text{ans}_i$。

问题 F. 花式堆栈 (Fancy Stack)

问题作者：Dmitry Gozman
问题开发者：Gennady Korotkevich

我们将堆栈上偶数位置的块称为“大块”（即 $b_2, b_4, \dots, b_n$），将奇数位置的块称为“小块”（即 $b_1, b_3, \dots, b_{n-1}$）。

首先，假设块的大小各不相同。我们将按照块的大小递减顺序处理它们（即 $a_1 \geq a_2 \geq \dots \geq a_n$）。我们使用动态规划来统计堆叠的方式。

令 $f_{i,j}$ 表示将前 $i$ 个最大的块放置到它们的正确位置，使得其中 $j$ 个块是大块，而 $i-j$ 个块是小块。初始状态为 $f_{0,0} = 1$。我们实现一个前向 DP，转移到第 $i+1$ 个块时，我们决定它是大块还是小块。

如果第 $i+1$ 个块是大块，它在堆栈中的位置是唯一确定的（具体来说，是第 $n-2j$ 个位置）。因此，我们转移到 $f_{i+1,j+1}$。
如果第 $i+1$ 个块是小块，那么有 $ \max(j-1, 0) + [j = \frac{n}{2}] $ 个可能的位置（即在大块之间的任何位置，并且如果所有大块都已放置完毕，则可以放置在堆栈顶部），其中 $i-j$ 个位置已经被占据。注意，这些可能的位置对于未来放置的小块是通用的。因此，我们转移到 $f_{i+1,j}$，系数为 $ \max(j-1, 0) + [j = \frac{n}{2}] - (i-j) $。

如果允许块的大小相同，我们可以按照大小递减的顺序逐块处理。在每个大小相同的组中，最多一个块可以是大块（因为所有大块的大小必须不同）。这样，我们仍然只有两种转移方式，这次两种转移都使用二项式系数。

总的时间复杂度为 $O(n^2)$。

问题 G. 全球变暖 (Global Warming)

问题作者和开发者：Nikolay Budin

我们使用从上到下的扫描平面算法。我们将维护比当前平面高的点的连通分量以及这些分量的表面积。当扫描平面遇到新点时，我们迭代其所有比平面高的邻居，并将它们的连通分量与新点合并。在存储连通分量时，可以使用并查集（DSU）。

接下来，处理表面积。考虑一个三角面，其顶点为 $a$、$b$、$c$。如果该面是水平的，则当扫描平面到达它时，我们将其面积添加到该连通分量的面积中。否则，假设 $z_a \leq z_b \leq z_c$，当前扫描平面的高度为 $s$。那么高于扫描平面的部分面积为：

\[\text{area}(s) = \int_{z=s}^{z_c} l(z) dz / \sin(\alpha) \]

其中 $\alpha$ 是该面与水平面的夹角，$l(z)$ 是该面与高度为 $z$ 的水平面相交的线段长度。函数 $l(z)$ 在区间 $[z_a, z_b]$ 和 $[z_b, z_c]$ 上是线性的。因此，函数 $\text{area}(s)$ 在这些区间上是二次函数。我们可以保持每个连通分量的这些二次函数的和，并在遇到新点时修改对应面的二次函数。

最后，当扫描平面达到某个查询的高度时，我们查看查询点所在的连通分量。

问题 H. 魔法英雄 (Heroes of Might)

问题作者：Nikolay Budin
问题开发者：Borys Minaiev

这个问题的完整解法非常复杂，所以我们仅提供一些关键思路，而不深入细节。

首先，讨论较慢的解法，它适用于回合总数不大的情况。对于每组农民，我们可以生成一个整数数组 $k_i$，表示该组在第 $i$ 次攻击中被杀死的农民数。例如，如果伤害为 15，每个农民的生命值为 10，而该组有 4 个农民，则对应的数组为 $[1, 2, 1]$。

构建每组的数组后，我们可以按保留每组初始顺序的方式将它们合并成一个大数组。这个合并后的数组对应于龙按某种顺序攻击各组农民。最优合并应该最大化生成数组的所有前缀和的总和。

如何合并数组？我们将每个数组分为若干个连续区间，并对每个区间计算 $a_i$（即该区间元素的和除以区间长度）。在所有可能的分割中，选择一个具有特殊性质的分割：

$a_1 > a_2 > \dots > a_n$
$(a_1, a_2, \dots, a_n)$ 按字典序最大

这种分割可以通过贪心算法计算。首先找到具有最大 $a_1$ 的前缀，切割它，然后递归地找到其他前缀。

这种分割也有几何解释。我们可以绘制点 $(i, \sum_{j \leq i} k_j)$，并找到它们的上凸包。上凸包的每个线段对应于最优数组分割中的一个区间。

可以证明，每个分割的线段可以在最优合并数组中保持连续。此外，要确定不同组的线段合并顺序，我们只需按 $a_i$ 排序即可。

可以证明，最优分割的段数为 $O(\log n)$。

最后一个问题是如何在较大约束下构建这些线段。我们需要找到点 $(i, \lfloor d \cdot i / h_p \rfloor)$ 的凸包。可以使用不同的方法，最简单的是使用连分数。有关该算法的详细描述，可以参考这里。

问题 I. 互动寻宝 (Interactive Treasure Hunt)

问题作者和开发者：Pavel Marvin

让我们注意到，点对 $(x_1, y_1)$、$(x_2, y_2)$ 和 $(x_1, y_2)$、$(x_2, y_1)$ 对于所有可能的 SCAN 请求结果是相同的。因此，我们可以假设 $x_1 \leq x_2$ 且 $y_1 \leq y_2$，然后用三个 DIG 请求检查这两对点。

首先，在点 $(1, 1)$ 和 $(1, m)$ 进行 SCAN：

\[A = \text{SCAN}(1, 1) = (x_1 - 1) + (x_2 - 1) + (y_1 - 1) + (y_2 - 1) \]

\[B = \text{SCAN}(1, m) = (x_1 - 1) + (x_2 - 1) + (m - y_1) + (m - y_2) \]

从这些值中，我们可以得到以下和：

\[S_x = x_1 + x_2 = \frac{A + B + 6 - 2m}{2} \]

\[S_y = y_1 + y_2 = \frac{A - B + 2 + 2m}{2} \]

接下来，在点 $\left(\left\lfloor \frac{S_x}{2} \right\rfloor, 1\right)$ 和 $(1, \left\lfloor \frac{S_y}{2} \right\rfloor)$ 进行 SCAN：

\[C = \text{SCAN}\left(\left\lfloor \frac{S_x}{2} \right\rfloor, 1\right) = (x_2 - x_1) + (y_1 - 1) + (y_2 - 1) \]

\[D = \text{SCAN}(1, \left\lfloor \frac{S_y}{2} \right\rfloor) = (x_1 - 1) + (x_2 - 1) + (y_ 2 - y_1) \]

从这些值中，我们可以得到以下差值：

\[D_x = x_2 - x_1 = C - S_y + 2 \]

\[D_y = y_2 - y_1 = D - S_x + 2 \]

最终，我们可以计算出：

\[x_1 = \frac{S_x - D_x}{2}, \quad x_2 = \frac{S_x + D_x}{2} \]

\[y_1 = \frac{S_y - D_y}{2}, \quad y_2 = \frac{S_y + D_y}{2} \]

最后，我们在单元格 $(x_1, y_1)$ 进行 DIG。如果找到宝藏，则第二个宝藏在 $(x_2, y_2)$。如果没有找到，宝藏在 $(x_1, y_2)$ 和 $(x_2, y_1)$。

问题 J. 工作查找 (Job Lookup)

问题作者：Vitaly Aksenov
问题开发者：Mikhail Dvorkin

这个问题可以通过动态规划（DP）“在子区间上”解决。

考虑一个子问题，针对一段人群 $[i, j]$。我们希望将他们安排成全局层次树中的一个子树，以最优的方式。令 $a_{ij}$ 为由该子树中的边引起的最小通信成本。换句话说，每个通信路径的成本为 $c_{uv} \cdot d_{uv}$，可以分解为每个边支付 $d_{uv}$ 次大小为 $c_{uv}$ 的费用。因此，在我们的动态规划值 $a_{ij}$ 中，只考虑由构建的子树中的边支付的通信成本。

为了计算 $a_{ij}$，我们迭代所有可能的根候选 $k \in [i, j]$。对于特定的 $k$，子树 $[i, j]$ 的通信成本由以下组成：$a_{i,k-1}$、$a_{k+1,j}$、从 $k$ 到其左子节点的边的通信成本（如果有的话），以及从 $k$ 到其右子节点的边的通信成本（如果有的话）。

从 $k$ 到其左子节点的边的通信成本是所有 $u \in [i, k-1]$ 且 $v \notin [i, k-1]$ 的对的 $c_{uv}$ 的和（这些对的所有人都需要支付这条边的费用）。这个值可以简单地通过矩阵 $c$ 中的两个子矩形的和来计算。对于右子节点的边，情况类似。

如果为矩阵 $c$ 预先计算了前缀和（或类似的数据结构），则特定 $k$ 的成本可以在 $O(1)$ 时间内计算，值 $a_{ij}$ 可以在线性时间内计算，整个问题的复杂度为 $O(n^3)$。

更多关于问题起源和相关性的说明可以参考 SplayNet 论文的第三节：SplayNet paper。

问题 K. 王国划分 (Kingdom Partition)

问题作者：Maxim Akhmedov
问题开发者：Niyaz Nigmatullin

我们从写下矩阵的系数开始，该矩阵表示在不同端点的归属下，边成本的系数：

	A	B	C
A	2	0	1
B	0	2	1
C	1	1	0

问题的结构提示它与最小割问题有关，但标准的最小割技术将顶点分为两部分，而这里要求将顶点划分为三部分 A、B 和 C。主要技巧是执行一个常见的反对称图转换。将每个顶点 $v$ 替换为两个顶点 $v_1$ 和 $v_2$，并将每条边 $uv$ 替换为两条边 $u_1 v_2$ 和 $u_2 v_1$，且两条边的成本与原边相同。

考虑新图中任意的割 $ (S, T) $。原图的每个顶点 $v$ 可以视为处于 $SS$、$ST$、$TS$ 和 $TT$ 的状态，具体取决于 $v_1$ 和 $v_2$ 是否属于 $S$ 或 $T$。写下类似的系数矩阵，该矩阵表示原图中边在割值中的系数：

	ST	TS	SS	TT
ST	2	0	1	1
TS	0	2	1	1
SS	1	1	0	2
TT	1	1	2	0

注意，目标矩阵是上述矩阵的一个子矩阵。这表明我们必须将顶点 $a$ 限制为 ST 顶点，将顶点 $b$ 限制为 TS 顶点。这可以通过将源顶点 $s$ 连接到 $a_1$ 和 $b_2$，并将 $a_2$ 和 $b_1$ 连接到汇顶点 $t$，并使用无限容量的边来实现，最终在生成的图中考虑 $s-t$ 割。

最后一个问题是如何处理 SS 和 TT 顶点的区别。可以证明，最小割总是可以选择为没有 TT 顶点；事实上，将所有 TT 顶点设为 SS 顶点不会增加边的系数。

综上所述，我们得到了一个解决方案：首先构造一个反对称图，使用适当的最大流算法（例如 Dinic 算法）找到最小割，然后将结果分割恢复为 A = ST，B = TS，C = SS ∪ TT。

问题 L. 迷宫 (Labyrinth)

问题作者：Michael Mirzayanov
问题开发者：Sergey Melnikov, Michael Mirzayanov

问题要求找到两条路径，它们从起点 $s$ 到终点 $t$ 且不相交。

设路径为：

$s = u_1, u_2, \dots, u_x, t$;
$s = v_1, v_2, \dots, v_y, t$。

我们可以证明，存在一对路径，使得顶点 $u_x$ 和 $v_y$（即两条路径的倒数第二个顶点）位于 DFS 树中根节点 $s$ 的不同子树中。这仅适用于两者不同于 $s$ 的情况。

在这种情况下，我们只需运行一次深度优先搜索（DFS），并选择一个合适的顶点作为 $t$，使得：

DFS 树中，顶点 $t$ 的父节点是顶点 $u_x$，
$t$ 有来自某个顶点 $v_y$ 的边，而 $v_y$ 在 DFS 树中相对于根节点 $s$ 位于不同的子树中（或者 $v_y = s$ 且 $u_x \neq s$）。

DFS 树中的这些路径将产生所需的两条不相交路径。

标签：dots,frac,题解,可以,ICPC,2021,text,顶点,我们
From： https://www.cnblogs.com/kimi0705/p/-/ICPC2122

ICPC 2021–2022，NERC – 北欧欧亚总决赛题解翻译

ICPC 2021–2022，NERC – 北欧欧亚总决赛题解翻译

问题 A. 可接受的地图 (Admissible Map)

引理

证明

问题 B. 预算分配 (Budget Distribution)

问题 C. 连接点 (Connect the Points)

问题 D. 可删编辑 (Deletive Editing)

问题 E. 平均划分 (Even Split)

问题 F. 花式堆栈 (Fancy Stack)

问题 G. 全球变暖 (Global Warming)

问题 H. 魔法英雄 (Heroes of Might)

问题 I. 互动寻宝 (Interactive Treasure Hunt)

问题 J. 工作查找 (Job Lookup)

问题 K. 王国划分 (Kingdom Partition)

问题 L. 迷宫 (Labyrinth)

相关文章

赞助商

阅读排行