顾名思义，建立在同余基础上的最短路。一般来讲，用于问凑数之类的问题时用，基本思想为 若有 $ax=b$，求 $b$ 的数量，则 $ax=b+kx$ 均为可行解。
1.跳楼机
题目原址
如果你现在能到达第 $i$ 层，则 $i+kx$ 层均可到达，所以我们考虑在对 $x$ 取模的意义下建立多个点表示 $0-x$，从 $i$ 号点向 $(i+y)%x$ 与 $(i+z)%x$ 连边，边权分别为 $y,z$。然后对每个点跑一遍以 $0$ 为源点的最短路，求出每个 $dis[i]$。
那 $dis[i]$ 有什么用呢？这表示了对 $x$ 取模后为 $i$ 的最小可达楼层，我们便可以据此算出取模后为 $i$ 的楼层对答案的贡献：$(h-dis[i])/x+1$。具体细节参照代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=1e5+5;
struct node{
int v,w;
};
vector<node>a[N];
int f[N];
int dis[N];
int h,x,y,z;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>h>>x>>y>>z;
for(int i=0;i<x;i++)
a[i].push_back((node){(i+y)%x,y}),a[i].push_back((node){(i+z)%x,z});
memset(dis,0x3f,sizeof(dis));
dis[1%x]=1;
queue<int>q;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
f[u]=0;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i].v,w=a[u][i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!f[v])q.push(v),f[v]=1;
}
}
}
int ans=0;
for(int i=0;i<x;i++)
if(dis[i]<=h)ans+=(h-dis[i])/x+1;
cout<<ans;
return 0;
}
|
2.墨墨的等式
题目原址
先将题目所求的 $l-r$ 转换为 $r$ 与 $l-1$ 的答案相减，相对上一题而言，这一题将 $x,y,z$ 的数量增多了，所以我们任选一个非零的 $a_i$，以它作为 $x$ 进行上一题的步骤。答案的统计同上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
struct node{
int v,w;
};
vector<node>e[N];
int a[N];
int f[N];
int dis[N];
int h,x,y,z;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,l,r;
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(!a[i])n--,i--;
}
if(!n)return cout<<"0",0;
sort(a+1,a+n+1);
int x=a[1];
memset(dis,0x3f,sizeof(dis));
for(int i=2;i<=n;i++)
if(a[i]!=a[i-1])
for(int j=0;j<x;j++)
e[j].push_back((node){(j+a[i])%x,a[i]});
dis[0]=0;
queue<int>q;
q.push(0);
while(!q.empty())
{
int u=q.front();
q.pop();
f[u]=0;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i].v,w=e[u][i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!f[v])q.push(v),f[v]=1;
}
}
}
int ans=0;
l--;
for(int i=0;i<x;i++)
{
if(dis[i]<=r)ans+=(r-dis[i])/x+1;
if(dis[i]<=l)ans-=(l-dis[i])/x+1;
}
cout<<ans;
return 0;
}
|
由于作者菜菜的，有问题不吝赐教。
