ABC 376 ABCD 迅速题解

· · 题解

代码：https://atcoder.jp/contests/abc376/submissions/me?f.Task=&f.LanguageName=&f.Status=&f.User=da_ke

A

一个非常简单的题目。我们食用一个技巧，将初始时的 lst 值设为 -\infty，随后维护 lst,T_i 即可。

建议评：红。

B

来势汹汹，不太好做的一个 B。

我们设 L,R 为当前手的位置。

不妨设移动 L 至 H。

分两类讨论：

  1. 我们直接从 L\to H，代价为 |L-H|。可行条件为 R 不在 [\min\{L,H\},\max\{L,H\}] 之间。

  2. 从 L\to N\to H。代价均为 N-|L-H|。

评橙。

C

我他妈唐诗事后 3 min 最做出来了，请叫我事后诸葛亮。

我们发现插入一个数后单调性的变化情况，类比 CSP 2021 T2。

形式化解法。

维护 f(i),g(i) 分别表示：

- $f(i)$ 的后缀与 - $g(i)$ 的前缀与 找到第一个 $f1(i+1) \land g1(i-1)$ 的位置上的数 $a_i$。 评黄。 ## D 因为边权都为 $1$，使用 BFS 求出 $1$ 到 $1$ 的最短路，允许 $1$ 访问第二次即可。 评黄。