「Luogu」P3403 跳楼机 - 同余最短路

题面

题目背景

DJL为了避免成为一只咸鱼,来找srwudi学习压代码的技巧。

题目描述

Srwudi的家是一幢 h 层的摩天大楼。由于前来学习的蒟蒻越来越多,srwudi改造了一个跳楼机,使得访客可以更方便的上楼。

经过改造,srwudi的跳楼机可以采用以下四种方式移动:

  1. 向上移动x层;
  2. 向上移动y层;
  3. 向上移动z层;
  4. 回到第一层。

一个月黑风高的大中午,DJL来到了srwudi的家,现在他在srwudi家的第一层,碰巧跳楼机也在第一层。DJL想知道,他可以乘坐跳楼机前往的楼层数。

输入格式

第一行一个整数 h ,表示摩天大楼的层数。

第二行三个正整数,分别表示题目中的 x , y , z

输出格式

一行一个整数,表示DJL可以到达的楼层数。

输入输出样例

输入 #1

1
2
15
4 7 9

输出 #1

1
9

输入 #2

1
2
33333333333
99005 99002 100000

输出 #2

1
33302114671

说明/提示

可以到达的楼层有

1
1,5,8,9,10,12,13,14,15

想不出来不要死磕这一题,先看看第三题。。。。

1\leq h\leq 2^{63}-1

1\leq x, y, z\leq 10^5

题解

同余最短路板子题

对于题目中给的第四个条件其实是并没有用处的, 我们只需要考虑剩下三个条件就好了, 于是问题就转化为了用 x, y, z 能够凑出多少个 h 以内的数字

考虑 \mod x 的剩余系, 令 f_i 表示对于剩余系中的 i , 能被凑出来的最小高度, 那么说 f_i+tx, t\in \mathbb N 都能被凑出来, 此时对答案贡献了 \lceil{h-f_i\over x}\rceil

若能快速求出 f 数组, 那么这个题目就解决了

对于 f , 可以通过 同余最短路 来求出, 也就是对于 i (i+y)\mod x (i+z)\mod x 分别连一条长度为 y z 的边, 跑一边最短路即可

代码:

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
78
#include <bits/stdc++.h>

#define int long long

const int N = 100000 + 10;

struct Node;
struct Edge;

class Node {
public:
int dist;
bool used;

Edge *firstEdge;
} node[N];

class Edge {
public:
Node *s,*t;
int w;
Edge *next;
Edge (Node *s, Node *t, int w) : s(s), t(t), w(w), next(s->firstEdge) {}
};

int n, h;
int x, y, z;

inline void add (const int &s, const int &t, const int &w) {
node[s].firstEdge = new Edge(&node[s], &node[t], w);
}

inline void init () {
for (int i = 0; i < x; i++) {
node[i].dist = LLONG_MAX >> 1; // 由于 h 比较大, 这里要开的大一点
node[i].used = false;
}
}

void dij(const int &s){
init ();

std::priority_queue<std::pair<int, Node*>, std::vector<std::pair<int, Node*> >, std::greater<std::pair<int, Node*> > > q;
q.push(std::make_pair(node[s].dist = 1, &node[s]));

while(!q.empty()) {
Node *v = q.top().second;
q.pop();
if(v->used) continue;
v->used = true;
for(Edge *is = v->firstEdge; is; is = is->next){
if(is->t->dist > v->dist + is->w){
is->t->dist = v->dist + is->w;
q.push(std::make_pair(is->t->dist, is->t));
}
}
}
}

signed main () {
scanf("%lld", &h);
scanf("%lld%lld%lld", &x, &y, &z);

for (int i = 0; i < x; i++) {
add (i, (i + y) % x, y); // 加边
add (i, (i + z) % x, z);
}

dij(1 % x);

int ans = 0;
for (int i = 0; i < x; i++) { // 统计答案
// printf("[DEBUG] #%d's dist is %d\n", i, node[i].dist);
if (node[i].dist <= h) ans += (h - node[i].dist) / x + 1;
}
printf("%lld", ans);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!