2022/03/29 做题记录

模拟赛

A

可以发现，如果我们可以找到每一次出发会在哪个红绿灯第一次等待，那么等待完接下来的路程就相当于从那个红绿灯 0 时刻开始走，而每个红绿灯 0 时刻开始走需要的时间也可以通过相似的方法求出，找到从这开始会在哪个红绿灯第一次等待，然后从后往前递推即可。

而对于每一个红绿灯我们可以求出从家开始走会在这个红绿灯被拦住（不要求是第一个）的时间区间（ $\mathrm {mod} (g+r)$ ），而从中间一个红绿灯（假设走到起点的时间为 $d$) ，时间为 0 开始走就相当于从起点，时间为 $-d$ 开始走。

于是我们可以从后往前扫，对于每一个红绿灯我们区间取 min + 单点查询即可，需要一个动态开点线段树。

B

赛时写了个暴力在 trie 树上匹配的过了，总时间 ~200 ms ，果然出题人是卡不掉 n = 30000 的 $\mathrm{O}(n^2)$ 的。。。

正解是个 $\frac{}{w}$ 的东西，

因为总串长很小，所以我们可以在它们前面加上一个分隔符拼起来，然后我们枚举根节点，对每一个子树维护一个 bitset 表示在这个节点从下往上都有可能匹配到哪位（在上边拼起来的串中），初始状态就是只有所有分割符为 1 ，而转移就是对每一个可能匹配的位置看下一个和它到它父亲的那条边上的字符一不一样，如果一样就右移一位，否则就删掉，这样我们可以对每一个字符维护一个它所有出现位置的 mask ，也就是只有这些位置才可能右移过来，然后大概就是 dp[fa]|=((dp[x]<<1)&mask[c]),因为有分割符不用担心越界，而最后我们把 dp 状态全或起来看结束位置有没有 1 即可。