暑假刷题记 B

动态规划

字符串

杂题

A:Animals and Puzzle

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

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