2021.1 月赛题解

Once edited 3 年,11 月前

本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。首先,感谢以下同学为本次月赛命题做出的贡献:

命题人blunt_axe

验题团队zbwwssshwyRainAirKilo_5723Xiejiadongjhdonghj112xryjr233Oncebingoier

感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划,使得 EOJ 月赛能够圆满完成。此外,感谢 EOJ 运维团队为月赛提供了重要的技术支持。

最后,祝各位 ACMer 和 OIer 们元旦快乐,学业有成。

扫描二维码关注我们的微信公众号,获得更多信息。本次月赛的获奖名单和后续竞赛通知将通过公众号发布。

预计难度顺序:A < E < C < B < D < F。

A 逆十字

发现每个 “逆十字” 唯一对应一个只有五个格子的小十字,所以只要数出小十字的个数即可。

B 洪水

考虑终点 $(c, d)$ 未被淹没的最晚时刻 $T$。我们可以证明,以 $(a, b)$ 为起点的最晚出发时刻是 $T - |a - c| - |b - d|$。换句话说, Cuber 出现后可以沿着最短路径不停地走,并且到达终点后的下一时刻终点被淹没。

为什么一定可行呢?考虑 $t$ 时刻 Cuber 站在 $(x, y)$ 的情况。因为此时 $(x, y)$ 未被淹没,所以在 $t - 1$ 时刻 $(x, y)$ 的相邻格子也未被淹没(如果某相邻格子在 $t - 1$ 时刻被淹没,那么 $(x, y)$ 必会在 $t$ 时刻被淹没,故矛盾)。所以,如果 “时光倒流”,Cuber 就能自由移动,我们就能轻易推得上述结论了。

时间复杂度 $O(nq)$,可优化到 $O((n + q) \log n)$。

C 魔树

发现一个 D 操作恰好抵消前面的一个 A 操作。维护一个 “操作栈”,碰到操作后:

在(删去几层叶子后的)原树基础上,再依次执行栈中的 A 操作,就能得到最终的树。因为转化后只有 A 操作,所以结点数比较好算。

有个问题就是如何删除叶子。可以选择从下到上、类似拓扑排序的方法。也可以对于每个点算出:它到子树中最远叶子的距离。这个值加上 $1$ 直接代表了它属于第几层叶子,所以删叶子时不用真的删,记录一下总共删叶子的层数即可。

D 区间替换

记 $\texttt{F}$ 为 $[1, 2, \cdots, m]$,$\texttt{P}$ 为 $\texttt{F}$ 的一个真前缀,$\texttt{S}$ 为 $\texttt{F}$ 的一个真后缀,$\texttt{R}$ 为 $[2, 3, \cdots, m - 1]$ 的一个子段。

发现:合法的数组一定能由这四个基本的东西拼成,例如:
$$
\mathtt{PP\cdots P \ F \ SS\cdots S \ R \ PP\cdots P \ F \ SS\cdots S}
$$
进一步地,有如下规律:

所以,记 $f(n, c \in \lbrace \texttt{F}, \texttt{P}, \texttt{S}, \texttt{R}\rbrace )$ 表示以 $c$ 结尾的、长度为 $n$ 的数组个数。前缀和优化就能做到 $O(n)$。

E 菜品制作

在 $k = 1$ 时答案为 $\sum_{i = 1}^{n} a_i$。之后 $k$ 每增加 $1$,答案都会增加 $\max_{i = 1}^{n} a_i$。所以答案为 $\sum_{i = 1}^{n} a_i + (k - 1) \max_{i = 1}^{n} a_i$。

F 动态规划

对于序列 $[l_1, r_1], [l_2, r_2], \cdots, [l_k, r_k]$,考虑使用调整法得到答案。

考虑两个相邻的区间 $[a, b], [c, d]$:

如果对序列不断做上述操作,答案不变,并且最终只会得到两种序列:

只要用这个算法套上线段树就可以直接解决问题。线段树的结点存储对应序列调整后的序列,如果是第一种就存一个区间,如果是第二种就只存 $x_1, x_k$ 以及中间的答案。合并两个结点时,先把两个序列拼起来,然后在中间进行调整即可。

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

Comments

MAOoo

尝试学了一下D题的第二个通过代码,感觉比题解简单很多。如果用$\, f_n(i) \,$表示所有长度为$\, n \,$,最后一个数字为$\, i \,$,且后面再加上$\, i + 1, i + 2, \cdots, m \,$后是一个合法串的方案数。那么转移矩阵$\, f_{n+1} = A f_n \,$满足$\, A_{ij} = [i = 1] \mid [j = 1] \mid [i = j + 1] \,$。如果暴力维护$\, f_n \to f_{n+1} \,$的过程,复杂度是$\, O(m) \,$每次。但是注意到$\, f_{n+1}(m) - f_n(m - 1) = \cdots = f_{n+1}(2) - f_n(1) = f_n(m) \,$,所以只需要用滑窗单独维护$\, f_{n+1}(1) \,$,剩余部分shift一下,再维护一下差值就行。

MAOoo

写错了,$ A_{ij} \,$应该是$\, [i = 1] \mid [j = m] \mid [i = j + 1] \,$。

blunt_axe

这个做法非常简洁,我出题时也没想到。感谢您的分享以及这份代码的提交者!

Stump2001

妙啊

ShmilyTY

能提供一下标程吗,F不是很会写,看别人的也看不懂/kk

Once

代码已经全部公开

AdaptiveRoute

能请教一下B题具体是怎么优化的吗/kel 感觉像是线段树维护 $t_i$ 与曼哈顿距离之和的最小值或者什么之类的东西,但是想了一下觉得非常不可写/kel

MAOoo

有$\, (\pm 1, \pm 1) \,$四个方向。用扫描线分别沿正$\, x \,$和负$\, x \,$维护$\, \leq y \,$和$\, \geq y\,$的点在这四个方向上点积的最小值。离散化后可以用树状数组代替平衡树。

好像还有一个黑科技可以直接在$\, O(n \log n) \,$内建出V图,就不需要离线了。

AdaptiveRoute

大概懂了 谢谢神仙stO /kel

本来还以为需要类似 cdq分治 的玩意(