跳楼机
题目背景
DJL 为了避免成为一只咸鱼，来找 srwudi 学习压代码的技巧。
题目描述
Srwudi 的家是一幢 \(h\) 层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi 改造了一个跳楼机，使得访客可以更方便的上楼。
经过改造，srwudi 的跳楼机可以采用以下四种方式移动：
- 向上移动 \(x\) 层；
- 向上移动 \(y\) 层；
- 向上移动 \(z\) 层；
- 回到第一层。
一个月黑风高的大中午，DJL 来到了 srwudi 的家，现在他在 srwudi 家的第一层，碰巧跳楼机也在第一层。DJL 想知道，他可以乘坐跳楼机前往的楼层数。
输入格式
第一行一个整数 \(h\)，表示摩天大楼的层数。
第二行三个正整数，分别表示题目中的 \(x, y, z\)。
输出格式
一行一个整数，表示 DJL 可以到达的楼层数。
样例 #1
样例输入 #1
15
4 7 9
样例输出 #1
9
样例 #2
样例输入 #2
33333333333
99005 99002 100000
样例输出 #2
33302114671
提示
可以到达的楼层有：\(1,5,8,9,10,12,13,14,15\)。
\(1 \le h \le 2^{63}-1\)，\(1 \le x,y,z \le 10^5\)。
题解：
\(\%\%\%Mr\)_\(Leceue\)
先考虑如何统计答案,如果我们知道一个数 \(num\) 是由 \(y,z\) 构成的,即 \(num=a*y+b*z\),那么如果加上 \(x\) ,它能到达的楼层数为 \((h-num)/x+1\) 其中 \(+1\) 是因为要统计不加 \(x\) 时的答案;
那么如果我们能找到这些数,再去统计不就好了吗,但是会有重复,而且数字太过庞大,无法完全跑出,那么考虑什么时候回重复计数,即当 \(num1=num2+ax\) ,此时 \(num1\) 的贡献已经被 \(num2\) 统计过,再观察两个数字,发现 \(num1 \% x=num2 \% x\) ,那么我们只要找到余数相同中最小值即可,余数共有 xx 种;
设计转移方程: 设 \(f[i]f[i]\) 指余数为 ii 时最小楼层数,那么转移有两种方式;
\(f[(i+y)\%x]=min(f[i]+y,f[(i+y)\%x])\)
\(f[(i+z)\%x]=min(f[i]+z,f[(i+y)\%x])\)
我们可以用最短路来优化类似于点 \(i\) 与点 \((i+y)\%x\) 连边,代价为 \(y\) ;
std：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 2e5+9;
ll H,ans;
int x,y,z;
int h[N],ver[N],w[N],ne[N],idx;
void add(int u,int v,int val)
{
idx++,ver[idx]= v,ne[idx] = h[u],w[idx] = val,h[u] = idx;
}
queue<int>q;
bool inq[N];
ll dis[N];
void spfa()
{
for(int i = 0;i < x;i++)dis[i] = LLONG_MAX+1;//2^64
q.push(1),inq[1] = 1,dis[1] = 1;
while(!q.empty())
{
int u = q.front();inq[u] = 0,q.pop();
for(int i = h[u];~i;i = ne[i])
{
int v = ver[i];
if(dis[v] > dis[u] + w[i])
{
dis[v] = dis[u] + w[i];
if(!inq[v])q.push(v),inq[v] = 1;
}
}
}
}
int main()
{
scanf("%lld%d%d%d",&H,&x,&y,&z);
if(x == 1 || y == 1 || z == 1)return printf("%lld",H),0;
if(x > y)swap(x,y);
if(x > z)swap(x,z);
memset(h,-1,sizeof h);
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(H >= dis[i])ans += (H-dis[i])/x+1;
printf("%lld",ans);
return 0;
}
//putin:
//9223372036854775807
//10 10 10
//putout:
//922337203685477581