本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-22 23:13:04

Out of competition。

打得稀烂，罚时拉满。

H 题 dfs 参数传错，wa on 2 到结束也没看出来。

A

把样例抄下来就行了。

B

$O(n)$ 枚举。

C

设横向深度为 $dep_x$，纵向深度为 $dep_y$。

$score = \min(dep_x,dep_y)$

D

$dp_i$ 代表 $i$ 结尾，清理完的最小花费。

转移考虑最后 $k$ 个是否使用清理。

对于不足 $k$ 个元素的区间，如果需要清理，答案为 $1$，赛时我在这里写错，吃了一发罚时。

E

二分板子题，赛时没开 long long 寄了两发。

F

枚举每个点作为右端点，计算出左端点最远能到哪里。

然后对每个点，算左端点，可以用二分或双指针，前者 $O(n \log n)$，后者 $O(n)$。

G

显然答案最多是 $A$ 的个数。

一个点作为 $B$，前面或后面的所有 $A$ 都可以被干掉，代价是干掉前面或后面后自己失效。

设 $pre_i$ 是区间 $[1,i]$ $A$ 的数量，$suf_i$ 是区间 $[i,n]$ $B$ 的数量。

可以枚举所有 $B$ 的位置，计算 $ans = \max_{1 \le i \le n} max(pre_i,suf_i)$。

然后对于所有 $B$ 的位置 $i$ ，考虑它的下一个 $B$ 的位置 $j$，计算 $max_{1 \le i \lt j \le n} (pre_i + suf_j) $，并对 $ans$ 取 max。

H

显然只有到环上才安全。

先把环找出来。

对于环外的点，到环上显然只有一条路径。

可以计算出 Valeriu 到环上的耗时，以及第一个到达的环上点。

如果 Marcel 不能在 Valeriu 到达环上之前（可以是同时到达）堵住这个环， Valeriu 必胜。

两次 dfs 找出环，两次 dfs 算出 Marcel 堵环耗时和 Valeriu 逃生耗时就好了。

我这个是比较麻烦的做法。