跳楼机

· · 题解

从来没见过同余最短路，确实有点意思的。此类题关键在于，其中某个元素的范围很小，我们需要以此为切入点解决。方便起见，我们从 0 开始出发，存在的最后一个楼层为 h-1。

对于任何一个能到达的数，可以继续乘坐跳楼机上升 x 层若干次。因此可以发现，设有 a\equiv b \pmod x，其中 a\le b，若可以到达 a，则一定可以到达 b。

假设我们已经求出了仅使用 y 和 z 能到达的数集 S。从 S 中任取一数 v，则任意 v+kx(k\ge0,v+kx<h) 都可以达到，这样的 k 有 \left \lfloor \dfrac{h-1-v}{x} \right \rfloor +1 个。

但是，一个数可能会被重复统计。这是由于 S 中可能有多个数关于 x 同余。其中一个解决方案，即多个同余的数仅保留最小的，这是因为从最小的这个数 v 开始一直加 x 若干次后，一定可以到达其他与 v 模 x 同余的点。

现在，对于每个 0\le i<n，我们想要知道集合中满足 v\bmod x=i 的最小的点 v（形式化地，我们要求 \min_{v\in S,v\bmod x=i}v）。这里的一个相当聪明的步骤是转化为图论问题。

我们建立一个 x 个点的图，编号为 0 到 x-1。对某一个点 i，我们建立边 i\stackrel{y}{\longrightarrow}((i+y)\bmod x) 和 i\stackrel{z}{\longrightarrow}((i+z)\bmod x)。在这个图中，每条种移动方案都可以用一条路径描述：上升 y 层相当于沿着边权为 y 的移动一轮，上升 z 层相当于沿着边权为 z 的移动一轮，移动的距离即到达的高度。

从 0 出发跑最短路，设从 0 出发到点 i 的最短路为 dis_i。而 dis_i 同时还是我们上面要求的 \min_{v\in S,v\bmod x=i}v！

确实很聪明的转化。

#include <bits/extc++.h>
using namespace std;
namespace pbds = __gnu_pbds;
istream& fin = cin;
ostream& fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
vector<uli> dijkstra(size_t s, vector<vector<pair<size_t, uli>>> const& mp) {
  vector<uli> dis(mp.size(), numeric_limits<uli>::max() / 2);
  vector<bool> vis(mp.size());
  priority_queue<pair<uli, size_t>, vector<pair<uli, size_t>>,
                 greater<pair<uli, size_t>>>
      q;
  dis[s] = 0;
  q.emplace(0, s);
  while (!q.empty()) {
    size_t p = q.top().second;
    q.pop();
    if (vis[p]) continue;
    vis[p] = true;
    for (auto i : mp[p])
      if (dis[p] + i.second < dis[i.first])
        q.emplace(dis[i.first] = dis[p] + i.second, i.first);
  }
  return dis;
}
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  uli h;
  ui x, y, z;
  fin >> h >> x >> y >> z;
  --h;
  vector<vector<pair<size_t, uli>>> mp(x);
  for (size_t i = 0; i < x; ++i)
    mp[i].emplace_back((i + y) % x, y), mp[i].emplace_back((i + z) % x, z);
  auto dis = dijkstra(0, mp);
  uli ans = 0;
  for (size_t i = 0; i < x; ++i)
    if (dis[i] <= h) ans += (h - dis[i]) / x + 1;
  fout << ans;
  return 0;
}