同余最短路

╰半橙微兮° 2024-03-17 17:25 24阅读 0赞

**同余最短路就是把每一个同余类当成一个结点，在同余类之间建边，然后跑最短路**

**答案统计的时候对每个同余类单独计算贡献**

题意：

![9c8c8bfb42524299979c41508f6a8a77.png][]

![150baff219fd4094b59dd5a544199939.png][]

思路：

答案可以对模X的所有同余类计算贡献

设dis\[i\]为在模X意义下，+Y和+Z之后%X余数为i的能凑出来的最小数

那么答案就是枚举同余类，对于每个同余类，能到达的楼层数的贡献就是(H-dis\[i\])/X+1

前者是从这个最小数开始+X，能到达的楼层数，+1是因为要算它本身

每个同余类都看作是一个结点，同余类之间建边

起点是1，因为一开始是在第一层，%X=1

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    
    struct ty2{
        int x,dis;
        bool operator<(const ty2&oth)const{
            return oth.dis<dis;
        }
    };
    
    priority_queue<ty2> Q;
    
    int H,X,Y,Z,tot=0;
    int head[mxn];
    int dis[mxn],vis[mxn];
    
    void G_init(){
        tot=0;
        memset(head,-1,sizeof(head));
    }
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void dij(){
        memset(dis,0x3f3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[1]=1;
        Q.push({1,1});
        while(!Q.empty()){
            auto u=Q.top();
            Q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    Q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
    }
    void solve(){
        cin>>H>>X>>Y>>Z;
        if(X==1||Y==1||Z==1){
            cout<<H<<'\n';
            return;
        }
        G_init();
        for(int i=0;i<X;i++){
            add(i,(i+Y)%X,Y);
            add(i,(i+Z)%X,Z);
        }
        dij();
        int ans=0;
        for(int i=0;i<X;i++){
            if(dis[i]<=H) ans+=(H-dis[i])/X+1;
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

AGC D

![212ad6b8d17e42069c54f4c443ab45b4.png][]

![487f05d4f3cc4b139df185a13fbf144e.png][]

思路：

考虑模K意义下的所有整数

对于每个整数，都是由1经过\*10和+1这两种操作转移过来的

因此同余类之间建两条边：\*10和+1

最后的数位和就是+1操作的次数，\*10对数位和没有贡献

起点是1，终点是0

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    
    struct ty2{
        int x,dis;
        bool operator<(const ty2&oth)const{
            return oth.dis<dis;
        }
    };
    
    priority_queue<ty2> Q;
    
    int N,tot=0;
    int head[mxn];
    int dis[mxn],vis[mxn];
    
    void G_init(){
        tot=0;
        memset(head,-1,sizeof(head));
    }
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void dij(){
        memset(dis,0x3f3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[1]=1;
        Q.push({1,0});
        while(!Q.empty()){
            auto u=Q.top();
            Q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    Q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=0;i<N;i++){
            add(i,(i*10)%N,0);
            add(i,(i+1)%N,1);
        }
        dij();
        cout<<dis[0]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

题意：

![e63c2e3228644c2895ddd65b4229da8a.png][]

思路：

其实这类的板子题都一模一样，怪不得赛时这么多人过QwQ

设dis\[i\]为在模N意义下达到%N余数为i的最小代价

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
     
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
     
    struct ty2{
        int x,dis;
        bool operator<(const ty2&a)const{
            return a.dis<dis;
        }
    };
     
    priority_queue<ty2> Q;
     
    int N,y,p,x,q,tot=0,s,t;
    int c[mxn],head[mxn],dis[mxn],vis[mxn];
     
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N+1;i++){
            head[i]=-1;
        }
    }
    void dij(){
        for(int i=0;i<=N;i++) dis[i]=Inf;
        memset(vis,0,sizeof(vis));
        Q.push({s,0});
        dis[s]=0;
        while(!Q.empty()){
            auto u=Q.top();
            Q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(vis[edge[i].to]) continue;
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    Q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
    }
    void solve(){
        cin>>N>>p>>x>>q>>y;
        G_init();
        int sum=0;
        for(int i=1;i<=N;i++){
            cin>>c[i];
            sum+=c[i];
            sum%=N;
        }
        for(int i=0;i<=N-1;i++){
            add(i,(i+x)%N,p);
            add(i,((i-y)%N+N)%N,q);
        }
        s=sum%N;
        t=0;
        dij();
        if(dis[t]==Inf) cout<<-1<<'\n';
        else cout<<dis[t]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[9c8c8bfb42524299979c41508f6a8a77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6ba0c321d8a2468fa8173500e678ea5d.png
[150baff219fd4094b59dd5a544199939.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5639c6b1b66b4eff86c6b1ff961528ac.png
[212ad6b8d17e42069c54f4c443ab45b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/49978018a7014dd2a118fccd1cbc251c.png
[487f05d4f3cc4b139df185a13fbf144e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5bced33bbbbd45079b4e150e70a5cb13.png
[e63c2e3228644c2895ddd65b4229da8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f8a45b5e99204cae82c014b93821d030.png