

同余最短路

当出现形如“给定个整数，求这个整数能拼凑出多少的其他整数（个整数可以重复取）”，以及“给定个整数，求这个整数不能拼凑出的最小（最大）的整数”，或者“至少要拼几次才能拼出模余的数”的问题时可以使用同余最短路的方法。

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

类比差分约束方法，利用同余构造的这些状态可以看作单源最短路中的点。同余最短路的状态转移通常是这样的，类似单源最短路中。

例题

例题一

P3403 跳楼机

题目大意：给定 $，，，$ ，对于，有多少个能够满足。（，，）

不妨假设。

令为只通过 操作 2 和 操作 3，需满足能够达到的最低楼层，即 操作 2 和 操作 3 操作后能得到的模下与同余的最小数，用来计算该同余类满足条件的数个数。

可以得到两个状态：

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

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

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

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

接下来只需要求出，只需要跑一次最短路就可求出相应的。

与差分约束问题相同，当存在一组解时，同样为一组解，因此在该题让作为源点，此时源点处的在已知范围内最小，因此得到的也是一组最小的解。

答案即为：

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

参考实现

  #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() {  // 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("%lld\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;
  }

例题二

ARC084B Small Multiple

题目大意：给定，求的倍数中，数位和最小的那一个的数位和。（）

本题可以使用循环卷积优化完全背包在的时间内解决，但我们希望得到线性的算法。

观察到任意一个正整数都可以从开始，按照某种顺序执行乘、加的操作，最终得到，而其中加操作的次数就是这个数的数位和。这提示我们使用最短路。

对于所有，从向连边权为的边；从向连边权为的边。（点的编号均在模意义下）

每个的倍数在这个图中都对应了号点到号点的一条路径，求出到的最短路即可。某些路径不合法（如连续走了条边权为的边），但这些路径产生的答案一定不优，不影响答案。

时间复杂度。

习题

AGC057D - Sum Avoidance

本页面最近更新：2022/8/3 19:56:51，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：ChungZH, Enter-tainer, F1shAndCat, Jijidawang, kenlig, R-G-Mocoratioen, ShaoChenHeng, shuzhouliu, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

同余最短路

例题

例题一

例题二

习题

评论