洛谷 P3403 分析（别看）

科技起源

2026-07-17 15:03:03

发布于：河北

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：可达数量

1.2 题目背景、允许、禁止与限制

背景：有一栋 $h$ 层的摩天大楼
允许：初始在 $1$ 层，有四种操作供选择：

向上 $x$ 层
向上 $y$ 层
向上 $z$ 层
回到 $1$ 层

求可到达的楼层数量
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le x,y,z \le 10^5 \longrightarrow O((x,y,z)~log~(x,y,z))$

1.4 一句话概括题意

有一栋 $h$ 层的摩天大楼，有四种操作，求可到达的楼层数量

2 题目破题推导

2.1 题意梳理

初始位置为第 $1$ 层，允许四种操作：

当前楼层 $u$ 向上走 $x$ 层至 $u+x$ ；
当前楼层 $u$ 向上走 $y$ 层至 $u+y$ ；
当前楼层 $u$ 向上走 $z$ 层至 $u+z$ ；
任意楼层直接返回第 $1$ 层。

所有楼层 $v$ 必须满足 $1\le v \le h$ ，求可到达楼层的总数量。

2.2 数学表达式化简

任意合法路径均为为：从1出发，累加若干次 $x,y,z$ 。
因此所有可达楼层满足：

$pos = 1 + a\cdot x + b\cdot y + c\cdot z \quad (a,b,c\in \mathbb{N})$

使 $A = ax+by+cz$ ， $H=h-1$ ，原问题等价于：统计满足 $0\le A \le H$ 的非负整数 $A$ 的个数。

2.3 同余分类优化思路

选取 $x$ 作为模数，任意非负整数 $A$ 可唯一表示为： $A = k\cdot x + r,\quad r\in\{0,1,2,\dots,x-1\}$ ，其中 $r$ 为 $A~mod~x$
对固定余数 $r$ ：
设 $dis[r]$ 为满足 $A\equiv r \pmod{x}$ 的最小合法 $A$ 。
若 $dis[r] \le H$ ，则该余数下合法数字为： $dis[r],dis[r]+x,dis[r]+2x,\dots \le H$ ，总数为 $\dfrac{H-dis[r]}{x}+1$ ；若 $dis[r]>H$ ，该余数无合法数字。
问题转化为：求解每个余数 $r$ 对应的最小 $dis[r]$ 。

2.4 数学模型向图论模型的转化

2.4.1 顶点定义

构造有向图 $G=(V,E)$ ，顶点集合 $V=\{0,1,2,\dots,x-1\}$ 。
顶点 $r$ 的含义：代表所有模 $x$ 余 $r$ 的整数 $A$ 。

2.4.2 边的定义

对任意余数 $i$ ，若给当前总和 $A$ 加上 $y$ ，新总和为 $A+y$ ，新余数为 $(i+y)\bmod x$ ，边权为 $y$ ；
同理加上 $z$ 后余数为 $(i+z)\bmod x$ ，边权为 $z$ 。
因此对每个顶点 $i$ ，添加两条带权有向边：

$\begin{align*} i &\xrightarrow{w=y} (i+y) \bmod x \\ i &\xrightarrow{w=z} (i+z) \bmod x \end{align*}$

边权代表累加的数值大小

2.4.3 模型等价性证明

起点：顶点 $0$ ，对应 $A=0$ （即原始楼层 $1$ ）；
单源最短路 $dis[r]$ 的意义：从顶点 $0$ 走到顶点 $r$ 的最短路径总权值，恰好是满足 $A\equiv r \pmod{x}$ 的最小 $A$ ；
原计数问题等价于：跑完单源最短路后，遍历所有余数，累加每类余数的合法数字数量。

2.5 两种图模型对比

暴力楼层图（不可行）
- 顶点：每层楼层 $1\sim h$ ， $h\le 2^{63}-1$ ，顶点规模极大，无法存储遍历；
- 边： $u\to u+x,u\to u+y,u\to u+z,u\to1$ ；
- 缺陷：无法适配题目超大范围的 $h$ 。
余数剩余类图（本题采用）
- 顶点：仅 $x$ 个（ $x\le 10^5$ ），内存可承受；
- 边：总边数 $2x$ ，图规模极小；
- 优势：将无穷多数字按余数压缩为有限顶点，完美匹配数据范围。

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：最短路，无负边， $h\le 10^5$ $\longrightarrow$ $\huge{堆优化dijkstra}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int h, x, y, z;
const int N = 1e5 + 10;
struct node{
    int to;
    int w;
};
vector<node> g[N];
const int INF = 0x3f3f3f3f3f3f3f3f;
int dis[N];
void dijk(int s){
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    while(!q.empty()){
        int d = q.top().first;
        int u = q.top().second;
        q.pop();
        for (int i = 0;i < g[u].size();i++){
            node now = g[u][i];
            int v = now.to;
            int w = now.w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}

signed main(){

    cin >> h >> x >> y >> z;
    if (x == 1 || y == 1 || z == 1){
        cout << h;
        return 0;
    }
    h--;
    for (int i = 0;i < x;i++){
        g[i].push_back({(i + y) % x, y});
        g[i].push_back({(i + z) % x, z});
    }
    dijk(0);
    int ans = 0;
    for (int i = 0;i < x;i++){
        if (dis[i] > h){
            continue;
        }
        ans += (h - dis[i]) / x + 1;
    }
    cout << ans;
    
    return 0;
}