暑假刷题记 B

2023-07-31 16:25 由 ademik 发表于 #后端开发

动态规划

字符串

杂题

B:Vanya and Treasure

根号分治。

实际上是从 $(1, 1)$ 先找一个 $1$，再找一个 $2\dots$ 最后找一个 $p$ 然后
依次按最短路走过去。

我们有两种想法，直接 BFS 递推得到当前点到所有点的距离或者直接暴力枚举两个层之间的所有点对，两种做法的时间复杂度都是 $O(n^2 m^2)$。

考虑缝合，经过一番神秘的复杂度分析，我们得到了 $O(nm \sqrt{nm})$ 的优秀算法。

D:Awesome Substrings

根号分治。

令 $s_i$ 表示 $\sum\limits_{1}^{i}a_i$，且枚举的倍数为 $d$，则有 $r - l = d \times (s_r - s_l)$。

直接暴力做是 $O(n^2)$，且不好优化。我们考虑分块计算的思想，设阈值为 $T$。

当 $d \in [1, T]$ 时，将原式变形可得 $d \times s_r - r = d \times s_l - l$，我们设 $f(i, d) = d \times s_i - i$，对于每个 d 可以求出 $ f(0...n, d)$ 的值。对于每个值 $x$，若有 $k$ 个 $i$ 满足 $f(i, d) = x$，它都会对答案产生 $\tbinom{k}{2}$ 的贡献。这一部分可以做到 $O(nT)$ 的实现。

当 $d \in (T, n]$ 时，将原式变形可以得到 $s_r - s_l = \dfrac{r - l}{d} < \dfrac{n}{d}$ ，即有贡献的 $(a, b)$ 对应的区间中 $1$ 的个数 $k < \dfrac{n}{d}$。因此我们对于每个 $l, k$ 找到 $r$ 的范围，其对答案的贡献为 $\lfloor \dfrac{r - i}{k} \rfloor - \lfloor \dfrac{l - i}{k} \rfloor$ ，再减去 $d \le T$ 的部分。这一部分可以做到 $O(n\frac{n}{T})$

总时间复杂度为 $O(nT + n\frac{n}{T})$，当 $T = \sqrt{n}$ 时最优。

E:PolandBall and Gifts

若将送别人礼物看做一条有向边，那么排列 p 所形成的是一些闭合的有向环。一个人收到礼物当且仅当一条有向边所连接的两个人都带了礼物。

先考虑最大化。假定环的大小为 k，对于一个奇环，当有 $\dfrac{k + 1}{2}$ 个人不带礼物时，这 k 个人收不到礼物；对于一个偶环，当有 $\dfrac{k}{2}$ 个人不带礼物时，这 k 个人收不到礼物。

一个不带礼物的人最多可以影响两个人，我们考虑尽量使每个不带礼物的人的影响最大。而对于任意环，只需要 $\lfloor \frac{k}{2} \rfloor$ 个不带礼物的人即可将可以影响两个人的点位占满。我们令 $ans2 = \sum\limits{\lfloor \dfrac{siz[i]}{2} \rfloor}$， $siz[i]$ 表示环的大小。当 $ans2 >= m$ 时，每个不带礼物的人都能占据一个影响两个人的点位；
否则的话，剩余的人就占据奇环上只能影响一个人的点位。

再考虑最小化。对于一个大小为 $k$ 的环，当环上有 $k$ 个不带礼物的人与有 $k - 1$ 个不带礼物的人都只会造成 $k$ 个人得不到礼物。故而，将一个环完全占满更优。原题即转化为判断是否能找到几个环使他们的大小和为 $m$，如果能，答案即为 $m$，否则的话，否则，忘带礼物的人的形式就是若干个环加上一条链，而这条链的尾部会有一个虽然带了礼物，但是收不到礼物的人。所以答案就是 $m + 1$。

F:Nastya and Time Machine

构造。

不难发现，经过节点次数的下界是所有节点的度数的最大值(类比于菊花)。如何构造出满足下界的答案？

为了方便构造，若进入节点 $x$ 的时间点为 $t_x$，则离开节点 $x$ 的时间点必须为 $t_x - 1$ (这样返回节点 x 的父节点时间点就为 $t_x$)

在遍历节点 x 的所有子节点时可能会有如下两种情况：

$t_x + deg_x < maxdeg$ 则过程中不会超过答案，只需遍历结束后将时间回到 $t_x - 1$ 即可。
$t_x + deg_x \ge maxdeg$ 过程中会有某一个节点的时间点超过答案。因为总共会占用 $deg_x + 1$ 个时间点，因此当过程中的标号达到 maxdeg 时只需回到 $maxdeg − deg_x$ 的时间点即可。

G:Andryusha and Nervous Barriers

直接正向模拟很困难，考虑从另一个角度解题。

我们可以将板子看成从高到低依次插入得到的，这样的话，我们可以不用在意板子和球的高度，只需关注他们的横坐标即可。

那么此时，一个板子的作用实际上是求出一定区间中球的个数 $x$, 并使区间两端点 $+x$, 将区间(除去端点)赋值为 $0$ 。

考虑到球在一定高度下落可能会砸碎板子这一因素，我们对于不同组的球再记录一个参数表示他们下降的高度，用优先队列来对高度进行排序。

我们考虑设计一个函数，询问一定区间内所有不足以砸碎当前板子的球的个数。由于对每个横坐标不同的点都需要查找一次优先队列，时间复杂度过高。
考虑维护一个变量记录区间最小值，当区间最小值大于坚固程度时直接返回，这样和区间取模类似，在数据随机条件下时间复杂度有保证。

H:Omkar and Landslide

结论题。

对山的调整顺序并不影响最终的结果，且停止时有 $h_{i + 1} - h_i \in \{0, 1\}$。
可以证明，停止时 $h_{i + 1} - h_i$ 最多有一个为 $0$, 其他的为 $1$。

这样的话，对于一个 n 和 h，就可以直接确定最终的答案。

J:Goodbye Souvenir

首先，由于区间中一种数只会计算一次贡献，那么我们要求的 $last_x - first_x = \sum\limits_{i \in [L, R]}^{a[i] = x} i - pre_i$，这是因为对于中间的部分而言，令 $j$ 为下一个位置满足 $a[j] = x$ 的下标，则 $pre_j = i$，那么 $i - pre_i + j - pre_j = j - pre_i$

那么此时，我们可以具化出两个不等式， $i \le R$ ， $pre_i \ge L$，在加入一个时间轴，即三维偏序。

具体的，我们有 $set$ 来维护每个值的前缀，修改一个数时需要修改以当前数为前缀数据。

K:Sources and Sinks

Q:Omkar and Time Travel

热门相关：恭喜你被逮捕了裙上之臣闺范名妓性感身体妇女会会长童贞教育