[洛谷 3403]跳楼机

题目链接

https://www.luogu.org/problem/P3403

题解

学了一个新词汇——同余最短路。

这题的常规做法是背包或者最短路。但这两种做法的时间和空间复杂度都是 \(O(h)\)，并不能解决本题。

假如 \(s\) 层可以到达的话，容易发现 \(s+kx\) 层（其中 \(k\) 为任意自然数）都可以到达。

于是我们先只考虑一次向上跳 \(y\) 层和 \(z\) 层这两种操作。

令 \(t=ay+bz+1\)（其中 \(a,b\) 均为自然数），我们设 \(f(i)\) 表示使得 \(t \equiv i \pmod x\) 成立的最小 \(t\) 的值。

初始化 \(f(1)=1\)，接下来和常规做法一样跑一遍最短路就可以了。

跑完最短路后，每个 \(f(i)+kx\)（\(k\) 为任意自然数）都是可行解。因此在给出最大高度 \(h\) 的前提下，容易知答案为：

$$ans=\sum_{i=0}^{x-1} \frac{h-f(i)}{x}+1$$

#include <cstring>
#include <iostream>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
queue<int> q;
int vis[100005];
long long dist[100005],h,x,y,z,ans;
int main()
{
 cin>>h>>x>>y>>z;
 memset(dist,INF,sizeof(dist));
 dist[1%x]=1,vis[1%x]=1;
 q.push(1%x);
 while(!q.empty())
 {
  long long u=q.front();
  q.pop();
  vis[u]=0;
  long long v=(u+y)%x;
  if(dist[v]>dist[u]+y)
  {
   dist[v]=dist[u]+y;
   if(!vis[v])vis[v]=1,q.push(v);
  }
  v=(u+z)%x;
  if(dist[v]>dist[u]+z)
  {
   dist[v]=dist[u]+z;
   if(!vis[v])vis[v]=1,q.push(v);
  }
 }
 for(int i=0;i<x;i++)
  if(dist[i]<=h)ans+=(h-dist[i])/x+1;
 cout<<ans<<endl;
 return 0;
}