Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P3403 【跳楼机】

posted on 2019-04-29 12:10:09 | under 题解 |

原文地址

这题是在干嘛啊?怕不是又是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;
}