目录
显示
题目链接
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; }