bzoj 2118: 墨墨的等式最短路建模题意分析代码

109 阅读 0 评论 72 点赞

我是靠谱客的博主糟糕玫瑰，这篇文章主要介绍bzoj 2118: 墨墨的等式最短路建模题意分析代码，现在分享给大家，希望可以做个参考。

题意

墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

分析

我们设a1表示a数组中最小的元素，dis[i]表示我通过使用若干个数，使得结果模a1=i，假设结果为x*a1+i，最小的x是多少。
那么我们可以连边后求最短路来求出dis数组，最后统计答案即可。

这题提示我们，在做物品无限的背包问题时，可以把问题转换成对某个值取模后求最短路。

代码

复制代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N=500005;
int n,cnt,last[N],a[20];
bool vis[N];
LL L,R,dis[N];
struct edge{int to,next;LL w;}e[N*12];
queue<int> que;
void addedge(int u,int v,LL w)
{
e[++cnt].to=v;e[cnt].w=w;e[cnt].next=last[u];last[u]=cnt;
}
void spfa()
{
que.push(0);vis[0]=1;
while (!que.empty())
{
int u=que.front();que.pop();
for (int i=last[u];i;i=e[i].next)
if (dis[u]+e[i].w<dis[e[i].to])
{
dis[e[i].to]=dis[u]+e[i].w;
if (!vis[e[i].to]) vis[e[i].to]=1,que.push(e[i].to);
}
vis[u]=0;
}
}
int main()
{
scanf("%d%lld%lld",&n,&L,&R);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
dis[0]=0;for (int i=1;i<a[1];i++) dis[i]=(LL)1e12;
for (int i=2;i<=n;i++)
for (int j=0;j<a[1];j++)
addedge(j,(j+a[i]%a[1])%a[1],a[i]/a[1]+(j+a[i]%a[1]>=a[1]));
spfa();
LL ans=0;
for (int i=0;i<a[1];i++)
ans+=max((R-i-a[1]*max((LL)0,dis[i]-1))/a[1],(LL)0)-max((L-1-i-a[1]*max((LL)0,dis[i]-1))/a[1],(LL)0);
printf("%lld",ans);
return 0;
}

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N=500005;
int n,cnt,last[N],a[20];
bool vis[N];
LL L,R,dis[N];
struct edge{int to,next;LL w;}e[N*12];
queue<int> que;
void addedge(int u,int v,LL w)
{
e[++cnt].to=v;e[cnt].w=w;e[cnt].next=last[u];last[u]=cnt;
}
void spfa()
{
que.push(0);vis[0]=1;
while (!que.empty())
{
int u=que.front();que.pop();
for (int i=last[u];i;i=e[i].next)
if (dis[u]+e[i].w<dis[e[i].to])
{
dis[e[i].to]=dis[u]+e[i].w;
if (!vis[e[i].to]) vis[e[i].to]=1,que.push(e[i].to);
}
vis[u]=0;
}
}
int main()
{
scanf("%d%lld%lld",&n,&L,&R);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
dis[0]=0;for (int i=1;i<a[1];i++) dis[i]=(LL)1e12;
for (int i=2;i<=n;i++)
for (int j=0;j<a[1];j++)
addedge(j,(j+a[i]%a[1])%a[1],a[i]/a[1]+(j+a[i]%a[1]>=a[1]));
spfa();
LL ans=0;
for (int i=0;i<a[1];i++)
ans+=max((R-i-a[1]*max((LL)0,dis[i]-1))/a[1],(LL)0)-max((L-1-i-a[1]*max((LL)0,dis[i]-1))/a[1],(LL)0);
printf("%lld",ans);
return 0;
}