题解 P3403 【跳楼机】

· · 题解

一个比较简单的 trick。似乎网上现在只有两道题（跳楼机 和 墨墨的等式）。干脆就来写一下吧。

同余最短路

通过同余构造一些状态，状态 x \to y 相当于图上点 x 连上一条有向带权的边至 y。

因此可通过此方法建图跑最短路，以此达到解决问题的效果。

【例题】跳楼机

有四种操作，分别为：

给定最高楼层 h，问可以到达多少不同的楼层。

先假设 x < y < z。

定义 d_i 为只通过操作 2,3 能够达到的最低楼层 p，并且满足 p \ \bmod x =i。

不难得到两个状态：

只要我们求出 d_0,d_1,\dots,d_{x-1}，答案就显而易见了。在此基础下我们只需要跳到不能再跳，对于答案累加就行了。显然能够证明跳的楼层不会重复。答案即为：

\sum_{i=0}^{x-1} \lfloor \frac{(h-d_i)}{x} \rfloor +1

注：这里需要加一的原因是现在所处的楼层也要算一次。

现在的最主要问题是 d_i 如何求出。

联想到最短路，最短路的转移是：

i \stackrel{val}{\longrightarrow}j

这个转移实际上和题目要求的状态是相像的，我们只需要令 i,[(i+y) \ \bmod x] 与 [(i+z) \ \bmod x] 为点，y,z 为权值就能够转移了。

定义到这里，显然的，d_i 就是 1 \to i 的最短路。直接使用最短路算法即可。这里使用的 Dijkstra 算法。但是这种题推荐使用 SPFA，这样建图是不会被卡的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Edge{
    LL v,val;
    Edge(){}
    Edge(LL V,LL VAL){v=V,val=VAL;}
};
struct Point{
    LL val;
    int s;
    Point(){}
    Point(LL VAL,int S){val=VAL,s=S;}
    bool operator < (Point another) const {return val<another.val;}
};
vector<Edge> G[100005];
LL h,d[100005];
int x,y,z;
void Dijkstra(LL s)
{
    memset(d,63,sizeof d);
    d[1]=1;
    priority_queue<Point> Q;
    Q.push(Point(1,s));
    while(!Q.empty())
    {
        Point now=Q.top();
        Q.pop();
        int p=now.s;
        LL val=now.val;
        if(val<d[p])    continue;
        for(unsigned int i=0;i<G[p].size();++i)
        {
            if(G[p][i].val+d[p]<d[G[p][i].v])
            {
                d[G[p][i].v]=G[p][i].val+d[p];
                Q.push(Point(d[G[p][i].v],G[p][i].v));
            }
        }
    }
}
int main(){
    scanf("%lld %d %d %d",&h,&x,&y,&z);
    if(x==1 || y==1 || z==1)    return printf("%lld",h)&0;
    int a[5];
    a[1]=x,a[2]=y,a[3]=z;
    sort(a+1,a+4);
    x=a[1],y=a[2],z=a[3];
    for(int i=0;i<x;++i)    G[i].emplace_back(Edge((i+y)%x,y)),G[i].emplace_back(Edge((i+z)%x,z));
    Dijkstra(1);
    LL ans=0;
    for(int i=0;i<x;++i)    if(d[i]<=h) ans+=(h-d[i])/x+1;
    printf("%lld",ans);
    return 0;
}

【拓展】墨墨的等式

题意：

给定 a_1,a_2,\dots,a_n,l,r,n，求有多少个 b \in [l,r]，使得等式存在非负整数解。

与上题相差不大，唯一的变化是求有多少个 b \in [l,r] 满足条件，实际上等同于分别求有多少个 b \in [1,r] 满足条件和有多少个 b \in [1,l-1] 满足条件。然后 Dijkstra 写丑的被卡了。

区别在于上题有 3 个上楼的操作，这个题有 n 个。照常建图就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
LL read()
{
    LL x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')  f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
    return x*f;
}
void write(LL x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct Edge{
    int v,val;
    Edge(){v=val=0;}
    Edge(int V,int VAL){v=V,val=VAL;}
};
struct Point{
    int val,s;
    Point(){val=s=0;};
    Point(int VAL,int S){val=VAL,s=S;}
    bool operator < (Point another) const {return val<another.val;}
};
vector<Edge> G[500005];
LL l,r,d[500005];
bool vis[500005];
int n,a[15];
void Spfa(int s)
{
    memset(d,63,sizeof d);
    queue<int> Q;
    d[s]=0;
    Q.push(s);
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        vis[now]=false;
        for(unsigned int i=0;i<G[now].size();++i)
        {
            int to=G[now][i].v,val=G[now][i].val;
            if(d[to]>d[now]+val)
            {
                d[to]=d[now]+val;
                if(!vis[to])    Q.push(to),vis[to]=true;
            }
        }
    }
}
LL query(LL upper)
{
    LL ans=0;
    for(LL i=0;i<a[1];++i)  if(d[i]<=upper) ans+=(upper-d[i])/a[1]+1;
    return ans;
}
int main(){
    n=read(),l=read(),r=read();
    for(LL i=1;i<=n;++i)
    {
        a[i]=read();
        if(a[i]==1) return write(r-l+1),0;
        if(!a[i])   --n,--i;
    }
    sort(a+1,a+1+n);
    LL p=unique(a+1,a+1+n)-a-1;
    n=p;
    if(n==1)    return write(r/a[1]-(l-1)/a[1]),0;
    for(LL i=0;i<a[1];++i)  for(LL j=2;j<=n;++j)    G[i].emplace_back(Edge((i+a[j])%a[1],a[j]));
    /*
    0 2
    1 0
    2 1
    */
    Spfa(0);
    write(query(r)-query(l-1));
    return 0;
}

完。