【JZ雅礼联考】跳楼机 题解

题目

  Srwudi的家是一幢h层的摩天大楼。经过改造，srwudi的跳楼机可以采用以下四种方式移动：
  1、向上移动 $x$ 层；
  2、向上移动 $y$ 层；
  3、向上移动 $z$ 层；
  4、回到第一层。
  现在 DJL 在第一层，跳楼机也在第一层。求DJL可以乘坐跳楼机前往的楼层数。
  $h \le 10^{18},\ \ x, y, z \le 10^5$

题目大意

  给出h、x、y、z，求 [1,h] 中有多少个数，可以表示成 ax+by+cz 的形式。

【这真是一个有趣的题目】

【40%】h,x,y,z<=10^5

  设 f[i] 表示 i 能不能被跳到。f[1]=1。
  f[i]=f[i-x] | f[i-y] | f[i-z]

【100%】h<=10^18

  假设我们最后再跳 x。
  发现如果我们只用 y 和 z，能够跳到 h1 和 h2 两个位置（h1< h2），而 h1 可以用 x 来跳到 h2，那么为了避免重复，我们只保留 h1。
  设 $f[i]$ 表示仅用 y 和 z 来跳，能跳到的 %x 等于 i 的最小位置。那么显然

$$ans=\sum_{i=0}^{x-1}(\lfloor\frac{h-f[i]}{x}\rfloor+1)$$

  接下来考虑怎么求 $f$ 数组。我们发现这样两种转移

$$f[(i+y) \bmod x]=f[i]+y \\ f[(i+z) \bmod x]=f[i]+z$$

  于是这就是个最短路。跑一遍spfa求出 $f$ 数组，就可以计算答案了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxx=(1e5)+5;

LL h;
int x,y,z;

int tot,go[2*maxx],next[2*maxx],f1[maxx];
LL val[2*maxx];
void ins(int x,int y,LL z)
{
	go[++tot]=y;
	val[tot]=z;
	next[tot]=f1[x];
	f1[x]=tot;
}

LL f[maxx];
bool bz[maxx];
int d[8*maxx];
void spfa(int st)
{
	memset(f,127,sizeof(f)); f[st]=1;
	bz[st]=1;
	d[1]=st;
	for(int i=1, j=1; i<=j; i++)
	{
		for(int p=f1[d[i]]; p; p=next[p]) if (f[d[i]]+val[p]<f[go[p]])
		{
			f[go[p]]=f[d[i]]+val[p];
			if (!bz[go[p]])
			{
				bz[ d[++j]=go[p] ]=1;
				if (f[d[i+1]]>f[d[j]]) swap(d[i+1],d[j]);
			}
		}
		bz[d[i]]=0;
	}
}

int main()
{
	scanf("%lld%d%d%d",&h,&x,&y,&z);
	
	fo(i,0,x-1)
	{
		ins(i,(i+y)%x,y);
		ins(i,(i+z)%x,z);
	}
	spfa(1%x);
	
	LL ans=0;
	fo(i,0,x-1) if (f[i]<=h) ans+=(h-f[i])/x+1;
	
	printf("%lld\n",ans);
}