题目链接

大体思路

把 11 作为起始点，将 i(0⩽i⩽x−1)i(0\leqslant i\leqslant x-1) 与 (i+y)mod  x(i+y)\mod x 连权值为 yy 的边以及与 (i+z)mod  x(i+z)\mod x 连权值为 zz 的边，跑一遍最短路，就会发现到 ii 的最短路（记作 disidis_i）会表示 %x==i 的楼中可以走到的最低的楼的层数。

坑点

  • 全部要开long long

  • x=1x=1 时，11 是 mod  x=0\mod x=0 的最低楼层，所以要把 11 向 00 建边（其他时候都不用）。

代码

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>//75760209
#include<ctime>
#include<climits>
#include<random>
#include<algorithm>
#include<unordered_set>
#define fru(i,j,k) for(register int i=j;i<=k;i++)//for_register_up
#define frd(i,j,k) for(register int i=j;i>=k;i--)//for_register_down
#define pc(charx) putchar(charx)
#define finfout(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using ll = long long;
namespace usegetin{
    char c=' ';
    inline ll in()
    {
        ll x=0;bool w=false;
        while(!isdigit(c))
        {
            w|=c=='-';
            c=getchar();
        }
        while(isdigit(c))
        {
            x=(x<<1)+(x<<3)+(c^48);
            c=getchar();
        }
        return w?-x:x;
    }
    template<typename ty>
    void out(ty x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)out(x/10);
        putchar(x%10+48);
    }
}
using usegetin::in;using usegetin::out;
using namespace std;
const int maxn=100012,maxm=100012;
ll h,x,y,z,ans;
struct edg
{
    int next,to,w;
}edge[maxm<<4];
int head[maxn],cnt=1;
inline void getin(int a,int b,int w)
{
    edge[cnt]=(edg){head[a],b,w};
    head[a]=cnt++;
}
struct node
{
    int no;ll num;
    bool operator<(node y)const
    {
        return num>y.num;
    }
};
ll dis[maxn];
bool bl[maxn];
void dijkstra(int s)
{
    if(s>=x)
    {
        getin(s,(s+y)%x,0);
        getin(s,(s+z)%x,0);
    }
    memset(dis,0x3f,sizeof dis);
    memset(bl,0,sizeof bl);
    priority_queue<node>que;
    dis[s]=1;
    que.emplace((node){s,1});
    while(!que.empty())
    {
        int dc=que.top().no;
        que.pop();
        //cout<<dc<<endl;
        if(bl[dc])continue;
        bl[dc]=true;
        for(register int j=head[dc];j;j=edge[j].next)
        if(dis[edge[j].to]>edge[j].w+dis[dc])
        {
            dis[edge[j].to]=edge[j].w+dis[dc];
            if(!bl[edge[j].to])que.emplace((node){edge[j].to,dis[edge[j].to]});
        }
    }
}
int main()
{
    h=in();x=in();y=in();z=in();
    fru(i,0,x-1)
    {
        getin(i,(i+y)%x,y);
        getin(i,(i+z)%x,z);
    }
    dijkstra(1);
    fru(i,0,x-1)
    {
        if(h>=dis[i])ans+=(h-dis[i])/x+1;
    }
    out(ans);
    return 0;
}