题解 P3403 【跳楼机】

· · 题解

原文地址

这题是在干嘛啊？怕不是又是a*b-a-b

然而万万没想到，这是到图论题

设dis[i]为在%x意义下，能到达的楼层为i的最小值

也就是说只用y, z能到达的楼层在%x意义下的最小值

不难推出方程

dis[(i + y) \% x] = min(dis[(i + y) \% x], dis[i] + y) dis[(i + z) \% x] = min(dis[(i + z) \% x], dis[i] + z)

看到这两个柿子，不难想到图论中的最短路，所以我们可以用最短路来求出0~x的dis值

求除了dis以后有什么用呢？

跟据dis定义，我们可以通过y, z到达的最小楼层，以该楼层为起点（设该点为s），我们可以跳到s + x, s + 2 * x……

总共我们可以跳到(H - dis[i]) / x + 1层

不难证明，每个楼层是不会被重复统计的

于是我们就可以以优秀的复杂度完成此题了

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define mem(k, p) memset(k, p, sizeof(k))
#define maxn 100005
int n, m, x, y, z, dis[maxn], vis[maxn], ans;
queue<int>q;
il void SPFA() {
    mem(dis, 63), q.push(1 % x), dis[1 % x] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop(), vis[u] = 0;
        int v = (u + y) % x;
        if(dis[v] > dis[u] + y) {
            dis[v] = dis[u] + y;
            if(!vis[v]) vis[v] = 1, q.push(v);
        }
        v = (u + z) % x;
        if(dis[v] > dis[u] + z) {
            dis[v] = dis[u] + z;
            if(!vis[v]) vis[v] = 1, q.push(v);
        }
    }
}
signed main() {
    n = read(), x = read(), y = read(), z = read();
    SPFA();
    rep(i, 0, x - 1) if(dis[i] <= n) ans += (n - dis[i]) / x + 1;
    printf("%lld", ans);
    return 0;
}