神仙建模题。
Description
一栋有 $h$ 层的楼，初始位置为 $1$，有如下操作：
- 向上移动 $x$ 层；
- 向上移动 $y$ 层；
- 向上移动 $z$ 层；
- 回到 $1$ 层。
问可以到达的楼层数。
Solution
首先数据 $h\le 2^{63}-1$ 暴搜显然不行。然后就考虑楼层之间的关系。
比较容易想到的是，以楼层为点来建图。但是如果直接暴力建每个楼层之间的关系的边，同样会因为数据范围太大而爆炸。
所以我们换个思路，考虑给出的操作之间的关系。
我们可以先处理其中两种上升操作，然后将这些情况求出来，再反过来找第三种上升操作能达到的新楼层。
这里设 $\text{dis}(i)$ 表示只用操作 $2$ 和 $3$ 能到达的在 $\bmod x$ 意义下能到达 $i$ 的最小楼层。
然后可以得出：
$$\text{dis}[(i+y)\bmod x]=\min(\text{dis}(i\bmod x)+y)$$
$$\text{dis}[(i+z)\bmod x]=\min(\text{dis}(i\bmod x)+z)$$
这和我们的最短路更新方式很相似。
我们就可以考虑将 $i+y,i+z$ 作为点，用最短路求出所有的 $\text{dis}(i)$ $(i\in [0,x))$。
接下来我们考虑 $\text{dis}$ 的作用。
如果我们知道只通过操作 $2,3$ 能到达的最小高度，这说明在此基础上能达到的剩下的楼层只需要由操作 $1$ 来补全即可。
如果上面的话不理解可以手动模拟一下。而且可以保证没有漏掉的情况。
所以求出所有的 $\text{dis}$ 之后，答案就是 $\large{\sum_{i=0}^{x-1}[\frac{(h-\text{dis}(i))}{x}+1]}$ $(\text{dis}(i)\le h)$。
上面这个式子也可以手动模拟一下，应该不是很难理解。
至于为什么每次答案要加一，因为我们每次统计答案要加上 $\text{dis}(i)$ 这层本身。
Other things
但是还是存在 $h$ 太大的问题，并且考虑到真正需要的下标都在 $[0,x)$ 范围内，所以我们只在这个范围内建边就好了。
另外要注意，因为楼层高度范围是 $[1,h]$，所以 $\text{dis}(1)=1$。
最后，如果 $x,y,z$ 中有至少一个是 $1$，就说明所有的楼层都可达，此时上面的都是扯淡，答案是 $h$。
剩下的细节都在代码里（也没什么细节）。
Code
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 200100
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
bool vis[maxn];
int h,x,y,z,tot,ans;
int Dis[maxn],head[maxn];
struct edge{int fr,to,dis,nxt;}e[maxn<<2];
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void add(int fr,int to,int dis){
e[++tot]=(edge){fr,to,dis,head[fr]};head[fr]=tot;
}
void SPFA(){
memset(Dis,INF,sizeof Dis);
memset(vis,false,sizeof vis);
deque<int> q;q.push_back(1);
Dis[1]=1;vis[1]=true;
while(!q.empty()){
int u=q.front();
q.pop_front();vis[u]=false;
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;
if(Dis[to]>Dis[u]+e[i].dis){
Dis[to]=Dis[u]+e[i].dis;
if(!vis[to]){
vis[to]=1;
if(!q.empty()&&Dis[q.front()]>Dis[to])q.push_front(to);
else q.push_back(to);
}
}
}
}
}
signed main(){
h=read();
x=read();y=read();z=read();
if(x==1||y==1||z==1){cout<<h;return 0;}
for(int i=0;i<x;i++)
add(i,(i+y)%x,y),add(i,(i+z)%x,z);
SPFA();
for(int i=0;i<x;i++)
if(Dis[i]<=h) ans+=(h-Dis[i])/x+1;
printf("%lld\n",ans);
return 0;
}
