URL：https://atcoder.jp/contests/abc319

目录

E

Problem/题意

Thought/思路

Code/代码

E

Problem/题意

有 N 个公交站，给出前 N - 1 个公交站的发车时间 Pi 和到下一站需要的时间 Ti。给出 Q 次询问，每次给出从家的出发时间 Qi，问从第一站到最后一站要多少时间。

每个站的发车时间是 Pi 的倍数，从家到第 1 个站需要 X 时间，从第 N 个站到另一个家要 Y 时间。

Thought/思路

注意到 Pi 的范围是 [1, 8]，假设 现在有 P1 = 2、P2 = 3，那么当 nowTime = 6 时，这两个站就会同时发车，然后每 6 时间，就会同时发车。

显然，对于所有的站台，他们的最小公倍数，就是同时发车时间，也意味着一个新的循环开始。

而 [1, 8] 的最小公倍数是 840，所以，我们只需要设 0~839 为每一种在第一个站台开始等待的情况，对每一种情况做一次模拟，最后询问时就可以直接获得答案。

Code/代码

#include "bits/stdc++.h"#define int long longint n, x, y;signed main() {std::cin >> n >> x >> y;std::vector <std::pair <int, int>> bt(n);for (int i = 1; i <= n - 1; ++ i) {int p, t; std::cin >> p >> t;bt[i] = {p, t};}std::vector <int> dp(840); //  840 == 0for (int i = 0; i <= 839; ++ i) {int now = i; // 在时间 i 从第 1 个站台出发for (int j = 1; j <= n - 1; ++ j) {int p = bt[j].first, t = bt[j].second;int wait = (p - now % p) % p; // p - now % p == pnow += wait + t;}dp[i] = now - i;}int t; std::cin >> t;while (t --) {int q; std::cin >> q;int i = (q + x) % 840;std::cout << q + x + dp[i] + y << "\n";}return 0;
}