首页 > 代码库 > Bzoj2118 墨墨的等式
Bzoj2118 墨墨的等式
Submit: 1488 Solved: 578
Description
墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Input
输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。
Output
输出一个整数，表示有多少b可以使等式存在非负整数解。
Sample Input
2 5 10
3 5
3 5
Sample Output
5
HINT
对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。
Source
同余类最短路
在所有读入的a[i]中，找到最小的一个a为基准，在模a的意义下计算问题
假设通过一些数可以凑出x，使得x%a==j，那么通过累加a就可以凑出所有%a==j的大数。
设dis[i]表示能凑到的模a余i的最小数，SPFA算出dis数组，再利用dis计算Bmin~Bmax内可以凑出的数的个数。
一：刚开始写了建边的版本，但是因为要连的边太多了，常数爆炸，4000+ms通过
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #define LL long long 7 using namespace std; 8 const int mxn=500100; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 struct edge{16 int v,nxt;17 LL dis;18 }e[mxn*10];19 int hd[mxn],mct=0;20 void add_edge(int u,int v,LL dis){21 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].dis=dis;hd[u]=mct;return;22 }23 int n;24 LL B1,B2;25 LL dis[mxn];26 int a[20];27 bool inq[mxn];28 queue<int>q;29 void SPFA(){30 memset(dis,0x3f,sizeof dis);31 q.push(0);inq[0]=1;dis[0]=0;32 while(!q.empty()){33 int u=q.front();q.pop();inq[u]=0;34 for(int i=hd[u];i;i=e[i].nxt){35 int v=e[i].v;36 if(dis[v]>dis[u]+e[i].dis){37 dis[v]=dis[u]+e[i].dis;38 if(!inq[v]){39 inq[v]=1;40 q.push(v);41 }42 }43 }44 }45 return;46 }47 LL query(LL x){48 LL res=0;49 for(int i=0;i<a[1];i++){50 if(dis[i]<=x)res+=(x-dis[i])/(LL)a[1]+1;51 }52 return res;53 }54 int main()55 {56 scanf("%d%lld%lld\n",&n,&B1,&B2);57 int i,j;58 for(i=1;i<=n;i++){59 a[i]=read();60 if(!a[i]){i--;n--;}61 }62 sort(a+1,a+n+1);63 64 for(i=1;i<=n;i++)65 for(j=0;j<a[1];j++){66 add_edge(j,(j+a[i])%a[1],a[i]);67 }68 SPFA();69 // for(i=0;i<a[1];i++)printf("%d ",dis[i]);70 LL ans=query(B2)-query(B1-1);71 printf("%lld\n",ans);72 return 0;73 }
二：改成了不具体建边的写法，只需要1000+ms
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #define LL long long 7 using namespace std; 8 const int mxn=500010; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int n;16 LL B1,B2;17 LL dis[mxn];18 int a[20];19 bool inq[mxn];20 queue<int>q;21 void SPFA(){22 memset(dis,0x3f,sizeof dis);23 q.push(0);inq[0]=1;dis[0]=0;24 while(!q.empty()){25 int u=q.front();q.pop();inq[u]=0;26 for(int i=2;i<=n;i++){27 int v=(u+a[i])%a[1];28 if(dis[v]>dis[u]+a[i]){29 dis[v]=dis[u]+a[i];30 if(!inq[v]){31 inq[v]=1;32 q.push(v);33 } 34 }35 }36 }37 return;38 }39 LL query(LL x){40 LL res=0;41 for(int i=0;i<a[1];i++){42 if(dis[i]<=x)res+=(x-dis[i])/(LL)a[1]+1;43 }44 return res;45 }46 int main()47 {48 scanf("%d%lld%lld\n",&n,&B1,&B2);49 int i,j;50 for(i=1;i<=n;i++){51 a[i]=read();52 if(!a[i]){i--;n--;}53 }54 sort(a+1,a+n+1);55 SPFA();56 LL ans=query(B2)-query(B1-1);57 printf("%lld\n",ans);58 return 0;59 }
Bzoj2118 墨墨的等式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。