题解 P3403 【跳楼机】

## [原文地址](https://www.cnblogs.com/bcoier/p/10789672.html) ~~这题是在干嘛啊？怕不是又是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; } ```