说实话,这道题主要还是思维。

对于 $x,y,z$ 三个操作,我们先考虑 $y,z$ 两个操作的情况。

$f[i]$ 表示通过 $y,z$ 两个操作可以到达的 $mod x=i$ 最小的楼层。

可以得知:$f[i+y]=f[i]+y,f[i+z]=f[i]+z.$

对于最短路,我们可以用一下形式建边:

   add(i,(i+y)%x,y); add(i,(i+z)%x,z);

没问题吧?%x 是必须要做的操作,上文讲了。

那如何统计答案呢?

首先,如果这个 “ 最小的楼层” 超出了 $H$ ,那么显然是不用统计的。否则,我们将这样统计:ans+=(H-f[i])/x+1;

为什么要这样写呢?想想,现在我们知道了这个最小楼层,我们可以到达这个最小楼层,对吧?如果现在以这个最小楼层为起点,我们可以选择在往上跳 $x$ 层,或者是 $2x$ 层…. 知道 $nx$ 层,$(n+1)x$就会超出 $H$,这时上面的式子就好理解多了。

Code:(可以不用 堆优 $Dijstra$,没必要,用 $Spfa$ 就行了)
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
using namespace std;
const int N=1e5+3;
ll H,x,y,z,ans,f[N];
int vis[N],head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1]; 
inline void add(int x,int y,int v)
{G[++cnt].nxt=head[x],G[cnt].to=y,G[cnt].val=v,head[x]=cnt;}
inline void spfa(){
    memset(f,127,sizeof(f));
    queue<int> q;f[1]=1,vis[1]=1,q.push(1);
    while(q.size()){
        int x=q.front();q.pop();vis[x]=0;
        for(RI i=head[x];i;i=G[i].nxt){
            if(f[G[i].to]>f[x]+G[i].val){
                f[G[i].to]=f[x]+G[i].val;
                if(!vis[G[i].to])q.push(G[i].to),vis[G[i].to]=1;    
            }
        } 
    }return;
}
int main(){
    scanf("%lld%lld%lld%lld",&H,&x,&y,&z);
    if(x==1||y==1||z==1){printf("%lld\n",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(f[i]<=H)ans+=(H-f[i])/x+1;
    printf("%lld\n",ans); 
    return 0;
}
分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

2 条评论

Remmina · 2019年1月15日 8:34 下午

同学吖,我真的建议您别用 Spfa。。。
总有一天你会后悔的

    Qiuly · 2019年1月15日 10:01 下午

    本来我也是用 Dij 的,偷了个懒

发表评论

电子邮件地址不会被公开。 必填项已用*标注