「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$ 层能否到达,那么转移方程就是

但是 $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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}

本文标题:「Luogu P3403」跳楼机

文章作者:Heartlessly

发布时间:2019年04月29日 - 08:51:08

最后更新:2019年04月29日 - 20:19:13

原始链接:https://heartlessly.github.io/problems/luogu-p3403/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%