别问我Hard Ver,我不会(((
题目翻译:你在一个长度为 O(稳定化子暴力)O(稳定化子暴力)O(稳定化子暴力) 左右走向的路上,有 nnn 个红绿灯,第 iii 个红绿灯位于 AiA_iAi ,从第 BiB_iBi 秒开始变红灯,每 kkk 秒变红 111 秒,其它时候全为绿灯。
你的一开始朝向是向右,111 秒移动一格,如果遇到红灯就转向。
问你在 O(染色暴力)O(染色暴力)O(染色暴力) 秒内能不能走出这条路(即位置超过了 [0,O(稳定化子暴力)][0,O(稳定化子暴力)][0,O(稳定化子暴力)] 的区间)。
显然 O(稳定化子暴力)O(稳定化子暴力)O(稳定化子暴力) 是 O(n5)O(n^5)O(n5),O(染色暴力)O(染色暴力)O(染色暴力) 是 O(2n)O(2^n)O(2n),不在一个数量级,所以不能走出这条路的情况只能是在某几个红绿灯之间卡住了。
太晚了,直接说做法。
我们找到第一个红绿灯,记录到达它的时间,然后只记录到达红绿灯之间的时间和方向,如果发现重复了就说明卡住了。
时间复杂度 O(qn2)O(qn^2)O(qn2),空间复杂度 O(n2)O(n^2)O(n2)。