[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} \rfloor+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+;

const ll inf=1e18;

ll h,x,y,z;

int vis[N];

ll d[N];

void spfa()

{

    queue <int> q;

    for (ll i=;i<x;i++) d[i]=inf;

    d[]=;q.push();vis[]=;

    while (!q.empty())

    {

        ll k=q.front();q.pop();vis[k]=;

        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]=;

        }

        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]=;

        }

    }

}

int main()

{

    scanf("%lld%lld%lld%lld",&h,&x,&y,&z);

    --h;

    spfa();

    ll ans=;

    for (ll i=;i<x;i++) if (h>d[i]) ans+=(h-d[i])/x+;

    printf("%lld\n",ans);

    return ;

}