同余最短路

当出现形如“给定 n 个整数,求这 n 个整数能拼凑出多少的其他整数( n 个整数可以重复取)”,以及“给定 n 个整数,求这 n 个整数不能拼凑出的最小(最大)的整数”的问题时可以使用同余最短路的方法。

同余最短路利用同余来构造一些状态,可以达到优化空间复杂度的目的。

类比 差分约束 方法,利用同余构造的这些状态可以看作单源最短路中的点。同余最短路的状态转移通常是这样的 f(i+y) = f(i) + y ,类似单源最短路中 f(v) = f(u) +edge(u,v)

例题

P3403 跳楼机

题目大意:给定 x,y,z,h ,对于 k \in [1,h] ,有多少个 k 能够满足 ax+by+cz=k

不妨假设 x < y < z

d_i 为只通过 操作 2操作 3 能够达到的最低楼层 p ,并且满足 p\bmod x=i

可以得到两个状态:

  • i \xrightarrow{y} (i+y) \bmod x

  • i \xrightarrow{z} (i+z) \bmod x

注意通常选取一组 a_i 中最小的那个数对它取模,也就是此处的 x ,这样可以尽量减小空间复杂度(剩余系最小)。

那么实际上相当于执行了最短路中的建边操作:

add(i, (i+y) % x, y)

add(i, (i+z) % x, z)

接下来只需要求出 d_0, d_1, d_2, \dots, d_{x-1} ,只需要跑一次最短路就可求出相应的 d_i 。答案即为:

\sum_{i=0}^{x-1}\frac{h-d_i}{x} + 1

加一是由于当前所在楼层也算一次。

参考实现
 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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100010;
const int INF = 0x3f3f3f3f;

ll h, x, y, z;
ll head[maxn << 1], tot;
ll dis[maxn], vis[maxn];
queue<int> q;

struct edge {
  ll to, next, w;
} e[maxn << 1];

void add(ll u, ll v, ll w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void spfa() {
  dis[1] = 1;
  vis[1] = 1;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to, w = e[i].w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) {
          q.push(v);
          vis[v] = 1;
        }
      }
    }
  }
}

int main() {
  memset(dis, INF, sizeof(dis));
  scanf("%lld", &h);
  scanf("%lld %lld %lld", &x, &y, &z);
  if (x == 1 || y == 1 || z == 1) {
    printf("%d\n", h);
    return 0;
  }
  for (int i = 0; i < x; i++) {
    add(i, (i + z) % x, z);
    add(i, (i + y) % x, y);
  }
  spfa();
  ll ans = 0;
  for (int i = 0; i < x; i++) {
    if (h >= dis[i]) ans += (h - dis[i]) / x + 1;
  }
  printf("%lld\n", ans);
  return 0;
}

习题

洛谷 P3403 跳楼机

洛谷 P2662 牛场围栏

[国家集训队]墨墨的等式

「NOIP2018」货币系统


评论