同余最短路(总结)

同余最短路其实是一种优化最短路建图的方法。

通常是解决给定m个整数，求这m个整数能拼凑出多少的其他整数(这m个整数可以重复取)或给定m个整数，求这m个整数不能拼凑出的最小（最大）的整数。

时间复杂度：$O(mlogn)$

P3403 跳楼机

给定$x,y,z,h$

$ax+by+cz=k$，$a,b,c\ge 0$，求满足条件$k\le h$的$k$有多少个。

考虑令$d_i$表示只通过$y,z$可以得到的最小值，且$d_i(\mathrm{m}\mathrm{o}\mathrm{d}x)=i$。

从第$d_i$层开始，我们可以通过$x$来增加贡献。

即：$d_i+x,d_i+2x,d_i+3x\dots \dots$

因此这部分的贡献是：$\frac{h-d_i}{x}$

而且加上$d_i$ 这层的贡献，就是$\frac{h-d_i}{x}+1$。

因此最后的答案就是：$\sum _{i=0}^{x-1}（\frac{h-d_i}{x}+1）$

注意需要满足$h\ge d_i$ 才会产生贡献。

可能有人会有疑惑，那$(1,x)$之间的数会不会漏掉呢？答案是不会的。

如果通过$y,z$可以得到$(1,x)$之间的数，则这个贡献会被算到$1$里去。

如果通过$y,z$不能得到$(1,x)$之间的数，那么显然$x,y,z$组合更得到不到，因为$x>(1,x)$。

注意$x,y,z$有等于1时，需要特判。

// Problem: P3403 跳楼机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3403
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-07-08 18:22:37
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%dn",a[n]); 
}
ll H;
int x,y,z;
ll d[N];
struct edge{
	int to,nt,w;
}e[N<<1];
int h[N],cnt;
void add(int u,int v,int w){
	e[++cnt]={v,h[u],w};h[u]=cnt;
}
int vis[N];
void spfa(){
	queue<int>q;
	mst(d,0x3f);
	vis[1]=d[1]=1;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=h[u];i;i=e[i].nt){
			int v=e[i].to,w=e[i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
}
int main(){
	scanf("%lld%d%d%d",&H,&x,&y,&z);
	if(x==1||y==1||z==1) {
		printf("%lldn",H);return 0;
	}
	for(int i=0;i<x;i++)  add(i,(i+y)%x,y),add(i,(i+z)%x,z);
	spfa();
	ll s=0;
	for(int i=0;i<x;i++)
		if(d[i]<=H){
			s+=(H-d[i])/x+1;
		}
	printf("%lldn",s);
	return 0;
}

P2371 [国家集训队]墨墨的等式

一样的题，只不过三种方式变成了$n$种方式，而且做了个前缀和处理。

先排序，然后用最小的值作为余数，跑最短路。

注意当有$a_i=1$直接输出，$r-l+1$。

有$0$直接跳过，避免重复加边。

跑$0$开始的最短路。

// Problem: P3403 跳楼机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3403
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-07-08 18:22:37
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=6e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%dn",a[n]); 
}
ll d[N];
struct edge{
	int to,nt,w;
}e[N<<1];
int h[N],cnt;
void add(int u,int v,int w){
	e[++cnt]={v,h[u],w};h[u]=cnt;
}
int vis[N];
void spfa(){
	queue<int>q;
	mst(d,0x3f);
	vis[0]=d[0]=0;
	q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=h[u];i;i=e[i].nt){
			int v=e[i].to,w=e[i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
}
int a[15];
ll que(ll mx){
	ll s=0;
	for(int i=0;i<a[1];i++){
		if(d[i]<=mx) s+=(mx-d[i])/a[1]+1;
	}
	return s;
}
int main(){
	int n;ll l,r;
	scanf("%d%lld%lld",&n,&l,&r);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]==1) return printf("%lldn",r-l+1),0;
		if(!a[i]) i--,n--;
	}
	sort(a+1,a+n+1);
	int p=unique(a+1,a+n+1)-a-1;
	n=p;
	if(n==1) return printf("%lldn",r/a[1]-(l-1)/a[1]),0;
	for(int i=0;i<a[1];i++)
		for(int j=2;j<=n;j++){
			add(i,(i+a[j])%a[1],a[j]);
		}
	spfa();
	printf("%lldn",que(r)-que(l-1));
	return 0;
}

GYM100753 M-Sums

判断是否有解等于$x$

不用真的建图的同余最短路方法。

即跑完同余最短路之后得到的$d[]$数组，判断$x\ge d[x(\mathrm{m}\mathrm{o}\mathrm{d}{a}_1)]$

因为如果满足的话，再通过加若干个$a_1$，即可得到$a_1$即可得到$x$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=5e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%dn",a[n]); 
}
ll d[N];
bitset<N>vis;
int a[N],n;
void spfa(){
	queue<int>q;
	mst(d,0x3f);d[0]=0;
	vis[0]=1;q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=2;i<=n;i++){
			int v=(u+a[i])%a[1];
			if(d[v]>d[u]+a[i]){
				d[v]=d[u]+a[i];
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
}
int main(){
	scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	spfa();
	int q;scanf("%d",&q);
	while(q--){
		int x;scanf("%d",&x);
		puts((x>=d[x%a[1]])?"TAK":"NIE");
	}
	return 0;
}

Little Elephant and Colored Coins(不会)

https://vjudge.net/problem/CodeChef-LECOINS

只会subtask1，判断是否有解。

最后

以上就是刻苦石头为你收集整理的同余最短路(总结)同余最短路(总结)P3403 跳楼机P2371 [国家集训队]墨墨的等式GYM100753 M-Sums的全部内容，希望文章能够帮你解决同余最短路(总结)同余最短路(总结)P3403 跳楼机P2371 [国家集训队]墨墨的等式GYM100753 M-Sums所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。