题解 P3403 【跳楼机】

· · 题解

主要的思想是要将题目转为最短路。我们假设dis[i]是y和z可达到的楼层mod x=i的最低楼层。将i从0到x-1枚举一遍，最终得到的便是所有在h范围内余数从0到x-1可达到的位置全部相加，即 (h-dis[i])/x+1 （i从0到i-1）。

而其中比较关键的一个点就是要将所有的dis[i]求出来，这就需要最短路。而最短路需要的图要由f(i+y)=f(i)+y和f(i+z)=f(i)+z 因为到达mod x=i+y的层数就是相当于先跑到mod x=i的层数在往上跑y层，所以我们可以通过这种方式自己构建图，在进行spfa。

这题有一个坑，就是第一组数据，x,y,z存在1且是乱序。必须要从大到小排序，否则结果会是0，当然也可以进行特判

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 500010;
long long ans, h, x, y, z, vis[N], dis[N], head[N], Next[N], ver[N], edge[N], tot;
queue <int> q;
void add(int x,int y,int z)//边表 
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
void spfa()//最短路 
{
    memset(dis,0x3f3f3f,sizeof(dis));
    q.push(1);
    dis[1]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        vis[x]=1;
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            if(dis[y]>dis[x]+edge[i])
            {
                dis[y]=dis[x]+edge[i];
                if(!vis[y]) q.push(y);
                vis[y]=1;
            }
        }
        vis[x]=0;
    }
}
int main()
{
    scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
    if(y<z) swap(y,z);
    if(x<y) swap(x,y);//将x，y，z按从大到小排序，x余数范围尽量大,过第一点
    for(int i=0;i<x;i++)//建图 
    {
        add(i,(i+y)%x,y);//f(i+y)=f(i)+y   到达mod x=i+y的层数就是相当于先跑到mod x=i的层数在往上跑y层 
        add(i,(i+z)%x,z);//f(i+z)=f(i)+z   同上 
    } 
    spfa();//跑一遍最短路 
    for(int i=0;i<x;i++)
    {
        if(h>=dis[i]) ans+=(h-dis[i])/x+1;//如果可以mod x=i时y和z可以达到的最低楼比总高度小，那就加上它的倍数（在h范围内），还要包括它自己 
    }
    printf("%lld",ans);
    return 0;
}