[ABC319E] Bus Stops 题解题意简介
给定 \(n\) 个公交站。对于第 \(i\) 个公交站，在时刻 \(p_i \times k,k \in \mathbb{N}\) 有一辆公交车出发，在经过 \(t_i\) 的时间后，到达第 \(i+1\) 个公交站。
在走到第一个公交车之前需要走 \(X\) 时刻，做到最后一个公交站之后下车以后还需要走 \(Y\) 时刻。
约束：\(1 \le p_i \le 8\)
给定 \(m\) 次询问，每次询问给定出发时间 \(q_i\)，问所需要花费的最小时间。就是 \(q_i + X + \text{坐公交车花费时间} + Y\)。
题目分析
考虑到 \(1 \le p_i \le 8\)，这里有个小技巧：我们考虑（1~8）最小公倍数 840 时间范围内的时刻就够了。
如果 \(p_i\) 中出现了全部 1~8，那么经过 840 时刻之后，所有车站发车的“小周期”就可以“耦合”成大周期。如果不全部出现 1~8，那么 840 一定包含了其大周期。
我们考虑 \(f_i\) 表示在第 \(i\) 个时刻到达第 1 个车站情况下，坐到最后一个车站所需要花费的时间。我们贪心地一站一站往前坐车即可。
我们对于 840 个时刻全部预处理一遍，时间复杂度 \(O(\text{lcm}(p_i)\times n)\)。对于每个询问，我们可以除掉周期，用余数代入 \(f_i\)，\(O(1)\) 地得到答案，时间复杂度 \(O(m)\)。总时间复杂度 \(O(\text{lcm}(p_i)\times n + m)\)。
代码
#include using namespace std;typedef long long LL;const int N = 1e5 + 5;const LL P = 840;LL n,p[N],t[N],x,y;LL f[P+5];void init(){for(int i = 0;i < P;i++){f[i] = i;for(int j = 1;j > n >> x >> y;for(int i = 1;i > p[i] >> t[i];}init();LL ques = 0;cin >> ques;while(ques--){LL q;cin >> q;q += x;cout << (LL)(q/P*P + f[q%P] + y) << "\n";}return 0;}