Posts by hostmaster

最小割 给定一个连通图 $G = \left(V, E\right)$。如果一个边子集 $C \subseteq E$ 是一个 割 当且仅当将 $C$ 中所有的边全部删除后，图不再连通。 所谓 最小割，就是让 $C$ 中的边权和最小。 Karger 算法 定义 收缩 操作 $\mathsf{Contract}\left(e\right)$…

题目 题解 这里给出一个不依赖子树标号连续的做法。 我们可以认为，如果一条路径上还有一条边的边权没有固定，那么这条路径的权是容易计算的。 我们可以认为，一开始所有点都是独立的，每次添加一条边。当一条路径的两个点连通时，这条路径上的边权就全部固定了。 我们需要做的是合并两个连通块，启发式合并即可。 代码 /* C++20 is requir…

ABC368D Minimum Steiner Tree 考虑到我们可以从叶子开始删，我们这里对叶子的定义是度数为 $1$ 的点。维护集合 $L$，如果一个叶子需要保留，那么从 $L$ 中删除这个点，不再考虑在这个叶子上操作。否则我们可以删除这个叶子 $x$，看看删掉 $x$ 之后，$x$ 的父亲是否变成了叶子，如果是，则要加入进 $L$…

题意 给定长度为 $n$ 的排列 $a$，删除 $a_i$ 的代价是 $b_i$。 现在希望删除一些 $a_i$，使得删完后 $a$ 的最长上升子序列长度不超过 $k$，最小化被删除元素的代价和。 对 $k \in \left[1, n\right]$ 分别求出答案。 题解 根据 Dilworth 定理，LIS 长度为 $k$，代表可以用…

题意 对于每个 $k \in \left[1, n\right]$，输出最小的 $m$，满足存在一种将给定的 $n$ 个数划分成 $m$ 段的方案，每段中不同数字的个数不超过 $k$ 个。 题解 做法 1 我一开始想到的就是这个。首先观察到我们一段区间里至少会有 $k$ 个数，因此可以暴力枚举 $k$，然后快速跳。这样是一个调和数。 我们…

二次方程 如今我们都知道的形式是 $ax^2 + bx + c = 0$，我们有通解 $x = -b \pm \frac{\sqrt{b^2 - 4ac}}{2a}$。 我们希望找一个有启发性的解法，帮助我们推导三次方程的解。 首先我们先给我们的形式简化一下，显然可以变成 $x^2 + \frac bax + \frac ca = 0$，…

题意 在一条直线上有 $n$ 个圆，分别以 $c_i$ 为圆心，$r_i$ 为半径。 如果两个圆相离、相切、包含时，这两个圆可以放在一起，求最多能有多少个圆同时放在一起，求方案。 $1 \leq n \leq 2000$ 题解 首先可以把一个圆看作一条线段 $\left[c_i - r_i, c_i + r_i\right]$。离散化。…

题意 给定 $n, m, k$ 和一个长度为 $n$ 的数组 $a$，满足 $1 \leq a_i \leq m$。 处理 $q$ 个询问，每次询问在 $\left[l, r\right]$ 中，至少删除几个数，能使得删完后的数组里，任意两个相邻的数的绝对值之差都不超过 $k$。 $1 \leq n \leq 10^5, 1 \leq q \leq 500$…

题目 题解 对于每个询问，我们让修改次数较小的人来计算。 按顺序处理每次操作，维护当前每个人是否在线，以及到目前为止的总在线时间，差分计算答案。 需要记忆化。我们分析时间复杂度： $$\sum\limits_{1 \leq i \leq \sqrt n}O\left(i \operatorname{op}_i\right) \leq \sum\limits_{1 \leq i \leq \sqrt n}O\left(n\right) = O\left(n \sqrt n\right)$$…

题目 题解 倍增做法 假设起点在左边，终点在右边。 首先最优的走法一定是能往右走就往右走，不能往右走了，我们就称“撞墙”了。 考虑一次撞墙事件，撞墙后，你一定会跑到新区间的上端点或者下端点，然后继续走。 那么撞墙一次之后，我们就可以倍增了。设 $f_{i, j}$ 表示从 $i$ 点出发，撞墙 $2^j$ 后到达的点，$g_{i, j}$…