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