「Luogu P3403」跳楼机

Description

现在有一座 $h\ (1 \leq h \leq 2^{63} - 1)$ 层的大楼，你站在第 $1$ 层，每次可以选择向上移动 $x,y,z\ (1 \leq x,y,z \leq 10^5)$ 层，求能到达的楼层数。

Source

[Luogu]P3403

Solution

其实问题就是求 $ax + by + cz\ (a, b, c \in\rm N)$ 有多少个小于等于 $h$ 的值。

很容易想到 $O(h)$ 的做法，就是用 $f_i$ 表示第 $i$ 层能否到达，那么转移方程就是

$$\large { f_i = f_{i - x} \mid f_{i - y} \mid f_{i - z} }$$

但是 $h$ 很大，所以换一种思路。

显然如果某一层楼 $i$ 能到达，那么 $i + kx$ 也一定能到达，因此只需要考虑模 $x$ 等于 $i$ 的最小层数。我们可以连有向边 $i \to (i + y) \bmod x$ 以及 $i \to (i +z) \bmod x$，其中 $0 \leq i < x$，边权分别为 $y$ 和 $z$，表示从第 $i$ 层到第 $i + y$ 层需要走 $y$ 层，$z$ 同理。建图后，从 $1$ 到 $i$ 的最短路即是模 $x$ 等于 $i$ 的最小层数。如果最早在第 $j\ (1 \leq j \leq h)$ 层满足 $j \bmod x = i$，则 $j + kx$ 层都能够到达，但又必须满足 $j + kx \leq h$，所以一共有 $\left \lfloor \frac{h - j}{x} \right \rfloor + 1$ 层能到达。枚举 $i = 0 \sim x - 1$，然后累加答案即可。时间复杂度为 $O(kx)$ 。这种算法叫做 同余最短路 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5, MAXM = 2e5;
ULL h, ans, dis[MAXN + 5];
int x, y, z, tot, head[MAXN + 5];
bool vis[MAXN + 5];
struct Edge {
    int next, to, dis;
} e[MAXM + 5];

inline void addEdge(int u, int v, int w) {
    e[++tot] = (Edge) { head[u], v, w };
    head[u] = tot;
}

inline void spfa(int s) {//求 1 到其它点的最短路 
    for (int i = 0; i < x; ++i) dis[i] = h + 1;//初始化
    queue<int> q;
    dis[s] = 1;//模 x 等于 1 的最小层数是 1
    q.push(s);
    for (; !q.empty(); ) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next)
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
    }
}

int main() {
    read(h), read(x), read(y), read(z);
    if (x == 1 || y == 1 || z == 1) {
        write(h);
        putchar('\n');
        return 0;
    }//特判，防止出现 x mod 1 = 0 的情况
    for (int i = 0; i < x; ++i)
        addEdge(i, (i + y) % x, y), addEdge(i, (i + z) % x, z);//连有向边 
    spfa(1);//起点为 1
    for (int i = 0; i < x; ++i)
        if (dis[i] <= h)//第 i mod x 层必须在 h 层之前
            ans += (h - dis[i]) / x + 1;//累加答案 
    write(ans);
    putchar('\n');
    return 0;
}