跳楼机

题意

从 1 楼反复增加 x/y/z，统计不超过 h 的可达楼层数。

思路

取最小步长 base。对每个模 base 的余数，Dijkstra 求能到达的最小楼层 dist[r]；此后反复加 base，同余且更高的楼层全部可达，贡献为 (h-dist[r])//base+1。

Python 知识

余数图只有 min(x,y,z) 个节点。
Python 整数直接支持 2^63 范围楼层。
生成器求和只统计 dist<=h 的余数。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import sys
from heapq import heappop, heappush


data = list(map(int, sys.stdin.buffer.read().split()))
height = data[0]
steps = data[1:]
base = min(steps)
infinity = height + max(steps) + 1
distance = [infinity] * base
distance[1 % base] = 1
heap = [(1, 1 % base)]
while heap:
    current, residue = heappop(heap)
    if current != distance[residue]:
        continue
    for step in steps:
        next_residue = (residue + step) % base
        candidate = current + step
        if candidate < distance[next_residue]:
            distance[next_residue] = candidate
            heappush(heap, (candidate, next_residue))
print(sum((height - value) // base + 1 for value in distance if value <= height))

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

设 b=min(x,y,z)，时间 O(b log b)，空间 O(b)。

总结

巨大数值范围加少量固定步长，常压缩成“每个余数的最小代表”。

目录

题意

思路

Python 知识

代码

复杂度

总结