题目
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 的形式。
【这真是一个有趣的题目】
![](/images/huaji.png)
【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 的最小位置。那么显然
接下来考虑怎么求 $f$ 数组。我们发现这样两种转移
于是这就是个最短路。跑一遍spfa求出 $f$ 数组,就可以计算答案了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| #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); }
|