菜王的 blog

题单

题意

link

有一个 $n$ 个节点的有向图 $G$，对于所有的 $1 \le i, j \le n$ 且 $i \not= j$，都有一条权值为 $(a_i + b_j) \bmod m$ 的边连接 $i, j$。

现在请你求出 $G$ 从 $1$ 到 $n$ 的最短路。

题解

最短路建模神仙题！

我们考虑这样一张有 $n + m$ 个节点的图 $G'$，节点分别为 $1, 2, 3, ..., n, \overline 0, \overline 1, \overline 2, \overline{m - 1}$。（有上划线的点可以理解为新增的虚点）

1. 对于所有的 $0 \le i < m$，有一条边连接 $\overline{i}$ 和 $\overline{i + 1}$，权值为 $1$。（$\overline m$ 相当于 $\overline 0$）

2. 对于所有的 $1 \le i \le n$，有一条边连接 $i$ 和 $\overline{m - a_i}$，有一条边连接 $\overline{b_i}$ 和 $i$，边权为 $0$。

这是对应的一组 $G$ 和 $G'$。

我们可以发现，$G$ 的任意两点之间的最短路和 $G'$ 的任意两个实点的最短路长度是一致的。

$G'$ 的点数和边数都是 $n + m$ 级别的，我们考虑去除无用的点。

考虑把 $G''$ 其中每一个没有与实点建立连接的虚点都缩到一起，就像这样：

与实点建立连接的虚点个数只有 $O(n)$ 的级别，边数也是 $O(n)$ 的级别，所以直接求最短路即可。

题意

link

有一个 $n$ 个点 $m$ 条边的无向图 $G$，你最初不知道 $G$ 的任何信息。

每次你可以询问 $G$ 的一个只包含部分边的子图 $G'$ 的最大生成森林的边权和，请你在 $2m$ 次询问内求出 $G$ 的最小生成森林的边权和。

题解

有趣的交互题。

首先可以做 $m$ 次询问求出 $G$ 的每条边的边权。

然后知道了边权，怎么求出最小生成森林呢？

容易想到使用 Kruskal。

将边按照边权从小到大排序后，不知道每条边的端点，怎么判断这条边的两个端点是否已经联通呢？

别着急，还有 $m$ 次询问还没用呢。

假设我们正在添加第 $i$ 条边（排序后），且权值为 $w$，$x_i$ 为只用前 $i$ 条边的子图的最大生成森林的边权和。

我们发现，第 $i$ 条边的两个端点还没有联通，当且仅当 $x_i - x_{i - 1} = w$。

为什么呢？首先，因为边权是从小到大排序的，所以在只用前 $i$ 条边的子图中，$w$ 是最大的那条边之一。这就意味着，如果两个端点已经联通，那么加上这条边一定会替换掉一些边。否则，不会替换边。

那么，这道题就做完了。

题意

link

给出一棵 $n$ 个点的树，有 $q$ 次询问，每次给出 $a, b, c, d$，询问树上路径 $(a, b)$ 与路径 $(c, d)$ 之间有没有公共点。

题解

有一个神奇的规律：

如果两条路径相交，那么一定有一条路径两个端点的 LCA 在另一条路径上。

证明

我们分两类讨论相交，一类是 $\operatorname{lca}(a, b)$ 在 $(c, d)$ 上，另一类是 $\operatorname{lca}(a, b)$ 不在 $(c, d)$ 上。

第一类相交显然满足条件。

第二类相交肯定满足，$(c, d)$ 整条链都在 $\operatorname{lca}(a, b)$ 的子树里，或者 $(c, d)$ 整条链都在 $\operatorname{lca}(a, b)$ 的子树外，只有第一种情况有可能产生相交。

如果第一种情况产生了相交，那么 $\operatorname{lca}(a, b)$ 显然在 $(c, d)$ 上。

于是，用倍增求 LCA 即可。

题意

link

有一个 $n \times m$ 的网格，边有边权，还有一些关键格，保证 $(1, 1)$ 一定是关键格。

现在需要选出一个围栏（可以自重叠），包围所有的关键格，花费为围栏上的边权和（重复覆盖的边要多算），求出最小花费。

题解

最短路建模神仙题！

令 $(1, 1)$ 格的左上角格点为源点。

首先有一个性质：选出的围栏一定包围源点到每一个关键格点左上角的最短路。

证明

考虑反证法。首先放张图片：

如果围栏（紫色部分）不完全包围某一条最短路，那么这条最短路有一些部分是在环外面的（红色部分）。

然后我们可以将围栏拓展到最短路处，因为最短路最短的性质，花费一定不会变多，能包含的部分也会变多（黄色部分），所以更优。

考虑围栏的本质。

我们发现，最优的围栏本质上就是一个从源点出发，绕过所有源点到关键格左上角点的最短路与关键格，又回到源点的最短路径。

怎么使围栏绕过最短路呢？首先，我们把所有源点到关键格左上角点的最短路都求出来，将最短路经过的边都标记。然后，我们考虑拆点。

首先，把每个格点拆成四个点，分别为 $0, 1, 2, 3$ 号点，对应格点的左上、右上、左下、右下四个部分。

对于每个点：

• 如果这个点所处的格子是关键点，将这个点删除。（因为路径需要绕过关键格）

• 否则：

  • 向与它处于同一个格点的顺时针方向下一个点连一条有向边

    • 如果这条边没有与任意一条最短路交叉，则边权为 $0$。
    • 否则，边权为 $\inf$（相当于不连）。

  • 向与它处于同一个格子的逆时针方向下一个点连一条有向边，边权为 $w$（原本这两个格点之间的边权）

具体连边看这张图：

然后，我们以源点拆成的 $0$ 号点作起点跑一遍最短路，终点为源点拆出的 $3$ 号点，路径长度即为答案。

题意

link

给一个 $n$ 个节点 $m$ 条边的无向图，$q$ 次询问，每次给定一个整数 $x$，你需要选出一棵生成树，设这棵生成树第 $i$ 条边的边权为 $w_i$，最小化 $\sum |w_i - x|$ 的值。

题解

最小生成树好题。

首先观察数据范围，$q$ 高达 $10^7$ 级别，而单次 Kruskal 需要 $O(m \log m)$，这让我们萌生了预处理然后快速查询的想法。

然后发现这个绝对值函数很麻烦，它会影响 $w_i$ 的值。我们考虑 Kruskal 的本质，其实我们不需要得知边权具体为多少，只需要知道边权的相对顺序，就可以知道具体使用哪些边。

继续挖掘绝对值的性质。可以得出，两条边 $w_i, w_j$（假设 $w_i < w_j$）当 $x \ge \lceil\frac{w_i + w_j}2\rceil$ 时，$|w_i - x| \ge |w_j - x|$。我们预处理出所有这样的临界值，对 $x$ 为每一个临界值的情况都跑一遍 Kruskal，就可以知道当 $x$ 在某个区间内，哪些边应该选。查询时直接二分 + 前缀和即可。

时间复杂度为 $O(m^3 \log m + q \log m)$，四秒时限可过。

题意

link

有一个 DAG，保证这个 DAG 只有一个点没有出边，每个点写有一个数，第 $i$ 个点上的数为 $a_i$。

每一秒，对于每一个这一秒之前 $a_u > 0$ 的节点 $u$，$a_u \larr a_u - 1$，对于所有 $u$ 直接通向的节点 $v$，$a_v \larr a_v + 1$。

请求出每一个节点的数都变为 $0$ 的最早秒数 $\bmod 998244353$。

题解

拓扑排序好题。

首先考虑 $a$ 均不为 $0$ 的情况。然后我们发现，在这种情况下一个点 $u$ 满足 $a_u = 0$ 时，当且仅当连向 $u$ 的每一个点 $f$ 都满足 $a_f = 0$，因为每一秒 $a_u$ 只会减少 $1$，而只要有一个连向 $u$ 的点 $f$ 满足 $a_f > 0$，$a_u$ 就又会增加 $1$，这样就证明了在来源消失前 $a_u$ 不降，我们直接拓扑排序 DP 即可。

回到 $a$ 可能为 $0$ 的情况。我们直接模拟前 $n$ 秒的情况，这样每个点都被贡献到了，按照前面的方法即可。

时间复杂度为 $O(n(n + m))$。