同余最短路学习笔记

同余最短路是什么？

就是没个点i的意义是在模mn的意义下能被构造出来的最小值

这有什么用呢？

这可以用最短路的方法求的余数是的最小能构造出来的数

这就可一求1-k中有多少数能被构造出来，即若干个a1到an的和

dis[(u+a[i])%mn]=min(dis[(u+a[i])%mn],dis[u]+a[i])

题目：跳楼机

Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。

经过改造，srwudi的跳楼机可以采用以下四种方式移动：

1. 向上移动x层；
2. 向上移动y层；
3. 向上移动z层；
4. 回到第一层。

一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。DJL想知道，他可以乘坐跳楼机前往的楼层数。

题解：

为了好做，先h--，求0-h每层能否到达。

题目可以转换成：求1-k中有多少数能被构造出来，即若干个a1到an的和

代码：

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=100005;
int h,a,b,c,mi,dis[N],vis[N];
struct node{
    int id,val;
};
bool operator < (node a,node b)
{
    return a.val>b.val;
}
priority_queue<node>q;
void dj()
{
    for(int i=0;i<N;i++)dis[i]=1e19;
    dis[0]=0;
    q.push((node){0,0});
    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        if(dis[(u+a)%mi]>dis[u]+a)
        {
            dis[(u+a)%mi]=dis[u]+a;
            q.push((node){(u+a)%mi,dis[(u+a)%mi]});
        }
        if(dis[(u+b)%mi]>dis[u]+b)
        {
            dis[(u+b)%mi]=dis[u]+b;
            q.push((node){(u+b)%mi,dis[(u+b)%mi]});
        }
        if(dis[(u+c)%mi]>dis[u]+c)
        {
            dis[(u+c)%mi]=dis[u]+c;
            q.push((node){(u+c)%mi,dis[(u+c)%mi]});
        }
    }
}
signed main()
{
    scanf("%llu",&h);
    h--;
    scanf("%llu%llu%llu",&a,&b,&c);
    mi=max(a,max(b,c));
    dj();
    int ans=0;
    for(int i=0;i<mi;i++)
    {
        if(dis[i]>h)continue; 
        ans+=(h-dis[i])/mi+1;
    }
    cout<<ans;
    return 0;
}

题目：[国家集训队]墨墨的等式

墨墨突然对等式很感兴趣，他正在研究存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

题解:

这不就是裸题吗？

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005;
int n,m,l,r,x,t,ans,a[N],dis[N];
bool vis[N];
struct node{
    int val,id;
}dui[N];
void upp(int x)
{
    if(x==1ll)return;
    int k=x/2ll;
    if(dui[x].val<dui[k].val)
    {
        node p=dui[x];dui[x]=dui[k];dui[k]=p;
        upp(k);
    }
}
void downn(int x)
{
    int k=x*2ll;
    if(k>t)return;
    if(k<t)
        if(dui[k].val>dui[k+1].val)k++;
    if(dui[k].val<dui[x].val)
    {
        node p=dui[x];dui[x]=dui[k];dui[k]=p;
        downn(k);
    }
}
int popp()
{
    int k=dui[1].id;
    dui[1]=dui[t--];
    downn(1);
    return k;
}
void dj()
{
    for(int i=1;i<=a[1];i++)dis[i]=1e16;
    dui[t=1]=(node){0,0};
    while(t>0ll)
    {
        int u=popp();
        while(t>0ll&&vis[u])u=popp();
        vis[u]=true;
        for(int i=2;i<=n;i++)
        {
            int x=(u+a[i])%a[1];
            if(dis[x]>dis[u]+a[i])
            {
                dis[x]=dis[u]+a[i];
                dui[++t]=(node){dis[x],x};
                upp(t);
            }
        }
    }
}
signed main()
{
    scanf("%lld%lld%lld",&n,&l,&r);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    dj();
    for(int i=0;i<a[1];i++)
        if(dis[i]<=r)
        {
            if(dis[i]>=l)ans+=((r-dis[i])/a[1]+1);
            else{
                ans+=(r-dis[i])/a[1]+1;
                ans-=(l-dis[i]+a[1]-1)/a[1];
            }
        }
    cout<<ans;
    return 0;
}