这题赛场上看了觉得完全不可做，这我连跑一遍都不能在 \(O(n)\) 时间内解决，却给我十万个询问，十万个点和边。
没想到短短不到 \(40\) 行代码就解决了。算法竞赛的魅力啊！
\(n\) 个城市，\(m\) 辆车，对于第 \(i\) 辆车在 \(s_i + 0.5\) 时刻从 \(u_i\) 出发，于 \(t_i+0.5\) 抵达 \(v_i\)。
T 某在一个点时会选择还没出发且离当前出发时刻最近的车坐上，直到没有车。给出 \(q\) 个询问，问 T 某最后会到哪里。
我以为是什么神奇的最短路的改进和优化，结果居然是倍增！倍增！倍增！
让 \(f_{i, j}\) 表示在第 \(i\) 辆车后又换乘 \(2^j\) 次内最后乘坐的车。\(f_{i, 0}\) 可以用 std::set 或 std::vector 里 lower_bound 来求得。
然后进行转移 \(f_{i, j} = f_{f_{i, j-1}, j-1}\)。
对于每个询问只要不断地跳直到跳不了，判断在车上还是在城市里就行了。
这么短就说完了，听上去也很简单，代码也很短，可就是想不到哇！/fn
不仅我没有想到，friends 表里的一堆大佬也没有想到，这题真是好极了。
不到 40 行的代码
#include <iostream>
#include <set>
#include <utility>
#include <algorithm>
#define se second
#define fi first
#define mapa std::make_pair
const int M = 100005, N = M;
int n, m, q, u[M], v[M], s[M], t[M], x, y, f[M][20], z;
typedef std::set<std::pair<int, int> > twt;
twt g[N];
int main() {
std::cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
std::cin >> u[i] >> v[i] >> s[i] >> t[i];
g[u[i]].insert(mapa(s[i], i));
}
for (int i = 1; i <= m; i++) {
twt::iterator it = g[v[i]].lower_bound(mapa(t[i], 0));
if (it != g[v[i]].end()) f[i][0] = it -> se;
}
for (int j = 1; j <= 17; j++)
for (int i = 1; i <= m; i++)
f[i][j] = f[f[i][j-1]][j-1];
while (q--) {
std::cin >> x >> y >> z;
twt::iterator it = g[y].lower_bound(mapa(x, 0));
if (it == g[y].end() || s[it->se] >= z) std::cout << y << ‘\n‘;
else {
int now = it -> se;
for (int j = 17; j >= 0; j--)
if (f[now][j] && s[f[now][j]] < z) now = f[now][j];
if (t[now] >= z) std::cout << u[now] << ‘ ‘ << v[now] << ‘\n‘;
else std::cout << v[now] << ‘\n‘;
}
}
}
那么现在来反思一下为什么想不到吧，或者说，怎么样才能想到倍增呢。
可以运用倍增的问题的性质
- 两步规模相同的问题的答案可以被快速合并。
- 状态有限、不大且易表示。
- 合并运算满足结合律。
第一条性质是显然的，不然你连倍增数组都求不出来。
第二条在这个问题中的体现就是，虽然在每个点要走的都是和时间相关的，但对于下每辆车之后的走发是唯一的，所以可以把车作为状态，以满足这个条件。也正是因为这个状态的巧妙定义，才能使第一条性质成立，能够不受其它因素影响地快速合并。
对于第三条，这也是一个重要的条件，因为在最后获取答案的时候直接用到了后面处理出来的答案，其实就是先算了后面，若运算不能满足结合律，这一步就不能保证了。在这个问题中，先走走后面和先走走前面肯定是没有问题的，但这同样依赖状态的确定。
所以这道题的难点在于确定这样一个倍增的状态，发现以车为状态后面的操作是唯一的。
得勤于观察思考，平时多做题积累经验啊！