[jzoj 4722] [NOIP2016提高A组模拟8.21] 跳楼机 解题报告 （spfa+同余）

题目链接：

http://172.16.0.132/senior/#main/show/4722

题目：

DJL为了避免成为一只咸鱼，来找srwudi学习压代码的技巧。
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。
经过改造，srwudi的跳楼机可以采用以下四种方式移动：
1、向上移动x层；
2、向上移动y层；
3、向上移动z层；
4、回到第一层。
一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。DJL想知道，他可以乘坐跳楼机前往的楼层数。

题解：

一开始$h--$，把第1层给减掉方便处理

40分的做法是直接bfs统计方案数，但是这样状态数太多太大了，考虑简化方案数

定义$d_i=c$，$c$表示最小的只由操作2,3得到的且满足$c mod x = i$的数

那么答案$ans=sum_{i=0}^{x-1} (lfloor frac{h-d_i}{x} floor+1)$

为什么呢？我们考虑将合法的楼层按模x分类，显然余数是由操作2,3得到的。那么我们考虑得到了最小的楼层，比它大的所有的在这个剩余系里的楼层都可以得到，而比它小的绝对得不到

按模x分类做到了不重，取完后面所有的数做到了不漏

考虑$d_i$怎么计算，显然有

$$d_{k+y}=d_k+y$$

$$d_{k+z}=d_k+z$$

这是一个最短路模型，跑一次spfa就好了

时间复杂度怎么算呢?我也没太弄懂

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;

const int N=1e5+15;
const ll inf=1e18;
ll h,x,y,z;
int vis[N];
ll d[N];
void spfa()
{
    queue <int> q;
    for (ll i=0;i<x;i++) d[i]=inf;
    d[0]=0;q.push(0);vis[0]=1;
    while (!q.empty())
    {
        ll k=q.front();q.pop();vis[k]=0;
        if (d[(k+y)%x]>d[k]+y) 
        {
            d[(k+y)%x]=d[k]+y;
            if (!vis[(k+y)%x]) q.push((k+y)%x),vis[(k+y)%x]=1;
        }
        if (d[(k+z)%x]>d[k]+z) 
        {
            d[(k+z)%x]=d[k]+z;
            if (!vis[(k+z)%x]) q.push((k+z)%x),vis[(k+z)%x]=1;
        }
    }
}
int main()
{
    scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
    --h;
    spfa();
    ll ans=0;
    for (ll i=0;i<x;i++) if (h>d[i]) ans+=(h-d[i])/x+1;
    printf("%lld
",ans);
    return 0;
}