List 1

发布于

ABC368D Minimum Steiner Tree

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

换句话说,如果一棵树的所有叶子都需要保留,那么此时无法进行操作,已经最优,否则我们一定可以找一个不需要被保留的叶子删除。

显然每个节点最多进出 $L$ 一次,用 set 维护,总复杂度 $O\left(n \log n\right)$。

ABC368G Add and Multiply Queries

题目保证了答案不超过 $10^{18}$,于是区间中 $B_i \neq 1$ 的个数不会超过 $\log_2 10^{18}$ 个,于是我们开 set 动态维护 $B_i \neq 1$ 的位置。对于 $B_i = 1$ 的区间,我们只能选择每次都加 $A_i$,开树状数组动态维护区间和即可。

总复杂度 $O\left(Q \log V \log N\right)$。

CF743E Vladik and cards

我们可以枚举选的最少的数选了几个。枚举 $8!$ 种排列,依次二分最前面的达标的位置判断。最终 $2^8 \times 8!$ 求最优答案。

总复杂度 $O\left(8! \cdot \log n + 8! \cdot 2^8\right)$。

ABC262F Erase and Rotate

我们只能碰到后 $k$ 个数,因此,我们绝对会选择后 $k$ 个里面最小的那个挪到前面。

考虑如果还剩下操作次数该怎么办。如果出现 $a_i > a_{i + 1}$,那么我们选择最小的 $i$,将 $a_i$ 删除即可。

如果还剩下操作次数,那么现在单调递增,删掉任何一个都会导致答案变大。于是我们选择删除最后一个。

还有一种情况,就是从前往后删到能碰到的最小数。这个是简单的。

CF2003D2 Turtle and a MEX Problem (Hard Version)

记 $mex_i$ 为序列 $i$ 的 $\operatorname{mex}$,$mexx_i$ 为序列 $i$ 添加上 $mex_i$ 后的序列的 $\operatorname{mex}$。我们让 $mex_i$ 向 $mexx_i$ 连有向边,那么假设现在我们在点 $x$,我们可以

  1. 将 $x$ 沿任意出边移动。
  2. 移动到另一个点 $y$,并将 $y$ 的任意一条出边删除(注意到如果我们如果选择了一个序列 $i$,但是添加的数不是 $mex_i$,那么当前数会变成 $mex_i$)。

对第一种情况 DP,$f_x$ 记为答案。

如果有一个点 $i$ 的出边数量大于等于 $2$,那么对于任意 $x$ 点,我们都可以放心跳到 $i$ 上,因此我们的答案至少是 $f_i$。

最终,点 $x$ 的答案是 $\max\limits_{i, \#out_i \geq 2} f_i$ 和 $\max\limits_i mex_i$ 和 $f_x$ 中的最大值,这已经包含了所有可能的选择,正确性得到保证。

复杂度 $\tilde O\left(\sum l_i\right)$。

CF924F Minimal Subset Difference

考虑 DP,我们得要一个优秀的状态。

我们考虑填入加减号,最终得到的绝对值最小值怎么算。注意到这只跟我们每个数选了几个有关,状态不多,容易预处理。

设 $f_{i, j, k}$ 表示还要填 $i$ 位,最终绝对值不超过 $j$,状态机上位置在 $k$ 的方案数。建立状态机的时候计算。

通过计算发现,这个状态机的大小在 $2 \times 10^4$ 左右。

对于每个数求答案时在这个状态机上数位 DP 即可。

AGC007E Shik and Travel

考虑如何让每条边只经过两次,我们需要按一个顺序去 dfs 这棵树。

现在先考虑一个 DP,我们只考虑以 $x$ 根的子树的答案。

现在我们的问题是如何合并两个子树,那我们需要枚举最后一个到达的点,和第一个枚举的点,求一个路径长度,取一下 $\max$,这样就得到一个 $O\left(n^3\right)$ 的做法。

我们完全可以不关心第一个枚举的点是谁,只关心到当前根的距离即可,我们把这个分别记为 $indis$ 和 $outdis$,这样得到一个 $indis$ 到 $outdis$ 的映射。容易发现,随着 $indis$ 的增加,$outdis$ 单调递减。

现在的问题变成了,合并两个分段函数。由于具有单调性,双指针合并是最优的。

一个大小为 $n$ 的分段函数和一个大小为 $m$ 的分段函数合并后的分段函数大小为 $2 \min\left(n, m\right)$,因此总复杂的经过 yyc 的势能分析为 $O\left(n \log n\right)$。

CF1025D Recovering BST

本来想的是令 $f_{l, r, t}$ 表示以 $t$ 为根,能否让 $a_l$ 到 $a_r$ 构成 BST。这样我们需要在左边枚举一个根,右边枚举一个根,判断是否合法,这样是 $O\left(n^4\right)$,后面猜测只能选第一个或最后一个,然后就过了。。。具体原因以后再分析吧。

CF429D Tricky Function

求 $\left(i - j\right)^2 + \left(s_i - s_j\right)^2$,看成最近点对即可。

CF366E Dima and Magic Guitar

考虑在位置 $\left(i, j\right)$ 找距离最远的颜色 $c$。我们发现,可能的情况只有左上,右上,左下,右下四种,于是分别记录最靠左上的,右上的,左下的,右下的四种点即可。

复杂度 $O\left(kn^2\right)$。

CF575G Run for beer

需要想的第一个问题是,这题的答案可能有多大。显然是有 $10^{10^5}$,非常难搞。但是我们发现他是个 10 进制,因此只需要算出路径即可。

这时候你就会发现,如果数长了那一定不优,因此我们需要保证我们的路径最短。

我们发现有一个很困难的问题是,在最后我们可以走一段权值为 $0$ 的边,这样我们的答案并不会增加。我们等下再考虑这个问题。

那么,如果只是单纯的在保证路径长度最短的前提下,让字典序最小,这个好做吗?

我们需要跑一个 BFS,但是我们需要找到一个合理的“层”的定义。为了维护复杂度,我们需要让 层之间的转移 与 总层数 的乘积较小。

如果我们单纯地让一个点的层就看作该点的深度,那么层内的点不等价。

Hack

$1$ 跟 $2$ 都是在一层的。但是如果先转移 $2$,那么点 $3$ 会出错,但实际上我们应该先更新更小的 $2$。

如果你构造一个明确的方式去获取每个点所在的层,是比较困难的。但其实我们的问题没这么棘手,我们只需要保证转移的顺序是对的即可。动态维护更新队列即可。

现在我们需要考虑一下前导零。我们发现如果两个节点都只有前导零,那么他们在地位上是等价的。把他们当做初始节点即可。

CF1110D Jongmah

三个一样的顺子可以看成三个刻子,于是只需要记录 $f_{i, j, k}$ 表示考虑点数小于等于 $i$ 的牌,有 $j$ 个 $\left\{i - 1, i, i + 1\right\}$ 的顺子和 $k$ 个 $\left\{i, i + 1, i + 2\right\}$ 的顺子的答案。

答案即为 $f_{m, 0, 0}$。

时间复杂度 $O\left(m\right)$。

CF1070A Find a Number

设 $f_{i, j}$ 表示模 $d$ 余 $i$,各位数字和为 $j$ 的最小数。位数可能有 $s$ 位,没法存。

使用 BFS,每次从小到大选择数字来更新队列。顺便记录上一次的位置,顺藤摸瓜找答案。

CF894D Ralph And His Tour in Binary Country

我们把贡献分为子树中的和需要经过父亲的。

由于树深度是 $\log_2 n$ 的,我们可以暴力跳父亲求经过父亲的贡献。

子树中的贡献也是好算的。使用一个 vector 维护子树中所有儿子到自身的距离,每次排序后二分即可。

时间复杂度 $O\left(m\log^2 n\right)$。

CF707D Persistent Bookcase

把操作依赖关系建树,dfs 时 bitset 实时维护即可。

CF643G Choosing Ads

线段树维护一个 $5$ 个数的摩尔投票,需要支持区间推平。

ARC099C Independence

考虑原图的补图,一个团在补图中的形态为一堆独立点。

因此原图的补图应为若干个二分图。背包合并即可。

CF687D

首先考虑一个 $\tilde O\left(qm\right)$ 的暴力,对于每个询问,取出指定的边,按照边权从大到小排序。一条边不成为答案,当且仅当这条边的两个端点在不同的集合里。用并查集维护对立关系。

如果一条边合并了两个并查集,那么这条边就是有用的。有用的边最多 $n - 1$ 条,于是可以在 $\tilde O\left(n\right)$ 的时间内合并两个区间的答案。用线段树维护。

总复杂度 $\tilde O\left(m + qn\right)$。

CF1552F

设 $f_i$ 表示,假设所有传送门目前都是开启的,那么从 $x_i$ 出发,走过传送门到 $y_i$,回到 $i$ 所需的时间是多少。

显然 $\left[y_i, x_i - 1\right]$ 的所有传送门都会被经过,且因为都是开着的,所以所有传送门全部会踩一边。因此

$$f_i = x_i - y_i + \sum\limits_{j, y_i \leq x_j < x_i}f_j$$

而显然,回到 $i$ 后,所有传送门照样是开启的。

二分之后,前缀和一下,后边的求和可以在 $O\left(\log n\right)$ 的时间内计算。

时间复杂度 $O\left(n\log n\right)$。

CF845F

$n, m$ 中的较小者不会超过 $15$,因此考虑状压。设 $m$ 为较小数。

要决定当前位置,我们只需要知道,上面是否有光线照射,左边是否有光线照射,和之前有没有一个没覆盖的位置即可。

上面的光线记录需要一个 $2^m$ 的状态,而左边的只需要一个 bool 即可。然后枚举当前这个位置填不填,更新一下状态去记忆化搜索就好了。

总状态数只有 $4nm \cdot 2^m$,转移规则 $O\left(1\right)$ 个。

Gym 103469F

注意到操作 $\left(a + b\right)$ 并不会改变 $a + b \bmod p$ 的值,而 $a$ 不断乘二会遍历整个模 $p$ 的剩余系,因此可以判断无解的情况。

接下来,我们发现把 $a, b, c, d$ 同时乘上某个数,并不改变 答案,因此我们可以把他们都乘上 $\left(a + b\right)^{-1}$,因此 $\left(a, b\right) \to \left(x, 1 - x\right)$。

观察 $\left(x, 1 - x\right)$ 的变换:

  • $\left(x, 1 - x\right) \to \left(2x, 1 - 2x\right)$
  • $\left(x, 1 - x\right) \to \left(2x - 1, 2 - 2x\right)$

其实,因为我们知道 $a, b$ 的其中之一,就能知道另一个数,因此我们可以只记录两者之一,比如就记录 $x$。

那我们的变换就很简单了,每次让 $x$ 变成 $2x$ 或者 $2x - 1$。如果我们进行 $k$ 次操作,$x$ 能变到 $\left[2^kx - k + 1, 2^kx\right]$ 中的任意一值。

枚举 $k$ 即可,总计算量为 $q \log p$。

Gym 103260A

注意到,我们不可能在一种职业里,去选择排名大于 $m$ 的人,这样一定不如选排名前 $m$ 的人优。现在我们的矩阵大小变为了 $m \times m$。考虑搜索。

我们肯定是要去搜每个职位选什么人,有两种实现方式。第一种是直接搜第 $i$ 次,在职位 $j$ 中选了哪个人。这种方式比较慢,较好的实现也需要超过一秒的时间。可以通过 long long 压位的方式减小常数,记忆化后可以做到 30 ms 以内,代码 https://home.rbtr.ee/code/Gym103260A.1.txt

第二种实现方式是去判断每个位置是否可能被去到,搜索时只需维护哪些人需要被选,一个个确定填的位置即可。这种方式常数非常小,无需优化即可做到 30 ms,代码 https://home.rbtr.ee/code/Gym103260A.2.txt

两种方式对分别应着,位置去选人 和 人去选位置。

Gym 102979J

显然把 $A$ 从大到小排序之后,第一条限制自然满足了。

现在我们要选一个长度为 $7$ 的子序列 $P_1, \ldots, P_7$,满足

$$P_1 < P_2 + P_3 < P_4 + P_5 + P_6 + P_7$$

容易发现,$P_3$ 到 $P_7$ 一定在序列中位置是连续的,因为固定 $P_3$ 之后,我们想尽可能让 $P_4 + P_5 + P_6 + P_7 > P_2 + P_3$,同时也希望和尽可能大,于是 $P_4, P_5, P_6, P_7$ 一定是紧跟在 $P_3$ 后面。

那么我们有两种思路

  • 枚举 $P_3$
    此时我们已经知道了 $P_3$,我们想找一个最大的 $P_2$,使得 $P_2 + P_3 < P_4 + P_5 + P_6 + P_7$,更大的 $P_2$ 可以让 $P_2 + P_3$ 更大,从而也能让 $P_1$ 选得更大。但其实有个小问题,就是如果 $P_2$ 选在太前面,可能导致 $P_1 \geq P2 + P3$,这是不合法的,仔细分析,我们发现 $P_2$ 所在的位置 $i$,如果 $A_{i - 1} \geq A_i + P_3$,那么这个 $P_2$ 就不合法了。我们移个项,就是 $A_{i - 1} - A_i \geq P_3$,这个 $P_3$ 我们是知道的,因此只需要求出第一个满足 $A_{i - 1} - A_i < P_3$ 的位置作为 $P_2$ 即可,线段树上二分或者 ST 都可以做到单 $\log$。确定了 $P_2 + P_3$ 之后,可以二分求出最好的 $P_1$。
  • 枚举 $P_2$
    此时我们知道了 $P_2$,设 $q = P_4 + P_5 + P_6 + P_7 - P_3$,我们想要一个最大的 $P_3$,满足 $P_2 < q$。如果有一个 $P_3$ 和一个 ${P_3}'$,满足 $P_3 \leq {P_3}'$,且 $q < q'$,则 $P_3$ 一定不优于 ${P_3}'$,使用单调栈维护,可以做到线性。

因为 $P_2$ 和 $P_3$ 在式子里是加起来的,枚举哪个,另外一个都会具有单调性。

Gym 105446E

首先是一个显然的 $O\left(n^2\right)$ DP,设 $f_i$ 表示以 $i$ 结尾的最小代价,转移显然就是

$$ \begin{aligned} f_i &= \min\limits_{0 \leq j < i, h_j \leq h_i} \left(f_j + \left(i - j - 1\right)^2\right) \\ &= \left(i - 1\right)^2 + \min\limits_{0 \leq j < i, h_j \leq h_i} \left(f_j - 2\left(i - 1\right)j + j^2\right) \end{aligned} $$

我们可以把后者看作一条斜率为 $-2j$,截距为 $f_j + j^2$ 的直线,计算 $f_i$ 时只需查询所有 $h_j \leq h_i$ 的直线在 $x = i - 1$ 处的最小值即可,值域线段树套动态开点李超树可以做到 $O\left(n \log^2 n\right)$,640 ms 通过。

https://home.rbtr.ee/code/Gym105446E.1.txt

想一想有没有更加优秀的做法,我们可以换一个角度,一个 $h_i$ 较大的点,不可能会由一个在 $i$ 后面的 $h_i$ 更小的点转移而来。

dp 方案可以看作是走一条路径,从 $i$ 走到 $j$ 的长度即为 $\left(j - i - 1\right)^2$,$f_i$ 就表示从 $1$ 走到 $i$ 的最短路径长度。

我们现在从 $i$ 转移到 $j$ 有两个限制:$i < j$ 和 $h_i \leq h_j$

如果我们按照 $h_i$ 从小到大的顺序来计算 $f_i$,那我们就需要确保当前的 $f_i$ 不会由 $j > i$ 的点转移而来。

我们通过归纳来证明不会出现这样的情况。如图所示,$i$ 是我们当前正在计算的位置。$j$ 是一个可能的决策点,我们要说明 $i$ 不可能从 $j$ 转移而来。绿色的路径表示 $j$ 的最短路。我们可以找到满足 $k < i$ 的最靠右的点 $k$。$k$ 的后继记为 $l$。首先 $f_j \geq f_l$,且 $\left(l - i - 1\right)^2 < \left(j - i - 1\right)^2$,所以从 $j$ 转移到 $i$,一定不如从 $l$ 转移到 $i$。同样的,从 $l$ 转移到 $i$ 一定也不如从 $k$ 转移到 $i$ 优:从 $k$ 转移到 $i$ 的代价为 $\left(i - k - 1\right)^2$,而从 $k$ 转移到 $j$ 再转移到 $i$ 的代价至少有 $\left(j - k - 1\right)^2$,仅这一项就已经超过 $\left(i - k - 1\right)^2$ 了。

这意味着我们按照 $h_i$ 从小到大加入点,也不会往左走,这样即满足了 $h_i \leq g_j$,又满足了 $i < j$。因此不再需要二维偏序,直接使用李超树维护即可。

于是我们直接按照 $h_i$ 从小到大的顺序加入点即可。复杂度变为 $O\left(n \log n\right)$,78 ms 通过。

https://home.rbtr.ee/code/Gym105446E.2.txt

Gym 102956G

显然当 $n$ 是奇数时无解。

考虑确定匹配后,练成树的方案数。我们先把匹配好的那些点对连起来,看作一个大点。现在我们有 $n/2$ 个大点,我们要将他们练成树。根据 Cayley 公式,方案数为 $\left(n/2\right)^{n / 2 - 2}$ 个。另外,任意两个大点相连都有 $4$ 种方案,因此答案要乘上 $4^{n / 2 - 1}$。现在考虑不同匹配的方案数。我们可以先全排列一下,相邻两个凑一对,然后除去 对与对 内的顺序,再除去对内的顺序,就是 $\frac{n!}{\left(n / 2\right)!2^{n / 2}}$。所以答案为

$$\frac{n!}{\left(n / 2\right)!2^{n / 2}} \cdot \left(n/2\right)^{n / 2 - 2} \cdot 4^{n / 2 - 1}$$

由于要算阶乘,复杂度为 $O\left(n\right)$。


  • 分类: 杂事
  • 最后更新于:2025-02-04 16:14:27UTC+8
  • 标签: 无标签