【VP 记录】EDU132

KSCD_ · 2024-06-04 22:32:15 · 个人记录

记录

AB 10min 顺利过了，C 卡一整场，写了个假做法，最后看 D 结果切了。

VP 后发现 C 是简单题补了，E 蓝启发式合并，F 紫没读题，不补了。

题解

A. Three Doors

简单模拟，略过不表。

B. Also Try Minecraft

预处理每一位向右和向左的代价，分别做前缀和和后缀和，每次查询只拿出一段区间的代价即可。

C. Recover an RBS

VP 时想到了要转化为前缀和数组非负，由此可以想到从左向右依次处理，维护目前前缀值 {cnt} 和未确定的位置数 {res}，容易想到 cnt 为零时问号必填左括号，否则不合法。

由此扩展，若 res+cnt=1，也即这一位之前所有未填的全部为左括号恰能填满，则这一位也必须填左括号。

最后若 res=\left|cnt\right|，也即所有未处理的位置都是同种括号，就只有一种填法，否则有多种填法。

D. Rorororobot

显然起点和终点的横纵坐标必须分别模 k 同余，否则无法每次走 k 格走到。

由于被封锁的是靠近底部的一部分，因此考虑尽可能走高处的格，发现在起点所在列尽可能向上走，再横着走到终点列，最后向下走到终点的走法受到的限制最小。

这样就需要保证起点列和终点列之间在横着走的这一行没有被封锁，也即求起点列和终点列之间的最值，用 ST 表或线段树解决即可。