P3403 跳楼机
One_JuRuo
·
·
个人记录
题目大意
有四个操作，上升 x，y，z 层楼，和回到第一层楼，问从第一层楼开始最多可到达多少层楼。
思路
因为交换操作顺序不会改变结果，所以我们可以考虑只进行操作 2,3，我们可以分别算出楼层模 x 为 i 能达到的最小楼层，那么把这些楼层加上若干个 x 都是可达到的楼层，这样就可以确定所有可能的楼层了。
那么怎么求得最小楼层呢？
设 dis_i 代表楼层模 x 为 i 中能达到的最小楼层。
那么可以轻易得到 dis_{i+y\%x}=dis_i+y，dis_{i+z\%x}=dis_i+z。
显然可以用这样的形式建图，然后跑最小路。这就是同余最小路的思想。把所有余数相同的情况整合在一起，算出最小的情况，然后这些答案加上模数就又是合理的情况。我们就可以快速地算出每个余数的总情况数。
对于这道题的每一个 dis_i，显然所有的 dis_i+x\times j,j\in\mathbb{N} 都是正确答案，所以答案就是 \lfloor\frac{h-dis_i}{x}\rfloor+1。
# AC 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long h,x,y,z,dis[100005],ans;
bool vis[100005];
queue<int>q;
inline void spfa(int s)
{
memset(dis,0x3f,sizeof(dis)),dis[s]=1,q.push(s),vis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
int j=(u+y)%x;
if(dis[j]>dis[u]+y)//同余最短路大多数情况不需要建图，可以直接根据定义跳转至下一个点
{
dis[j]=dis[u]+y;
if(!vis[j]) q.push(j),vis[j]=1;
}
j=(u+z)%x;
if(dis[j]>dis[u]+z)
{
dis[j]=dis[u]+z;
if(!vis[j]) q.push(j),vis[j]=1;
}
vis[u]=0;
}
}
int main()
{
scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
if(x==1||y==1||z==1) printf("%lld",h),exit(0);//特殊情况
spfa(1);
for(int i=0;i<x;++i) if(dis[i]<=h) ans+=(h-dis[i])/x+1;//计算答案
printf("%lld",ans);
return 0;
}
```