Codeforces Round 898 (Div. 4)
__vector__
·
·
个人记录
Out of competition。
打得稀烂，罚时拉满。
H 题 dfs 参数传错，wa on 2 到结束也没看出来。
A
把样例抄下来就行了。
B
## C
设横向深度为 $dep_x$，纵向深度为 $dep_y$。
$score = \min(dep_x,dep_y)
D
转移考虑最后 $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 逃生耗时就好了。
我这个是比较麻烦的做法。