首页 > 代码库 > 数论+spfa算法 bzoj 2118 墨墨的等式
数论+spfa算法 bzoj 2118 墨墨的等式
2118: 墨墨的等式
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1283 Solved: 496
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。
/*一开始就没想到是个最短路。题目可以这样变化一下:n个物品,可以用0-,正无穷,问[l,r]区间内有多少价值可以凑出来。联系到最短路上面:任选一个ai>0,如果一个价值k∗ai+x(0≤x<ai,k≥0)可以被凑出来,那么显然(k+1)∗ai+x,(k+2)∗ai+x,...都可以被凑出来(这样x的范围就是小于ai了)显然如果我们对于每个x都找到最小的k满足k∗ai+x可以被凑出来,这个问题就解决了,如果满足凑出x的最小花费是大于b的,那么就不能在[l,r]区间内凑出mn*k+x,这个数了,否则的话,就计算[l,r]内有多少个可以凑出来。 最短路,spfa时间复杂度O(n∗ai∗log2ai)因为复杂度与ai有关,所以我们就选择最小的ai了,举个例子:当最小的ai等于1时,那么自然区间内的所有数都可以凑出来了。*/
1 /*网上的AC代码,我加了注解,注意把I64d改为lld*/ 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 8 #define md 9 #define ll long long10 #define inf 1000000000000000LL11 #define eps 1e-812 #define N 50001013 using namespace std;14 int q[N];15 ll dis[N];16 bool vis[N];17 int mn,n;18 int a[20];19 void spfa()20 {21 int h=0,w=1,x,y; q[1]=0; vis[0]=1;/*第一个能凑出的数就是0*/ 22 while (h!=w)23 {24 h++; if (h>mn+5) h=1; x=q[h];/*循环队列,取出队头的数*/25 for (int i=1;i<=n;i++)26 {27 y=(x+a[i])%mn;/*利用这个价值和其他价值组合所能达到的y,计算y的最小花费(因为只有计算最小花费),才能用mn凑出更多的满足区间条件的数*/28 if (dis[y]>dis[x]+a[i])29 {30 dis[y]=dis[x]+a[i];31 if (!vis[y])32 {33 vis[y]=1;34 w++; if (w>mn+5) w=1; q[w]=y;35 }36 }37 }38 vis[x]=0;39 }40 }41 42 ll query(ll x)43 {44 ll ans=0;45 for (int i=0;i<mn;i++)46 if (dis[i]<=x) ans+=(x-dis[i])/mn+1; /*计算有多少个k满足k*mn+i<=x,因为k>=0,所以还要加1*/47 return ans;48 }49 50 /*windows 用I64d linux 用lld*/ 51 int main()52 {53 mn=(1e9);54 ll L,R;55 scanf("%d%I64d%I64d",&n,&L,&R);56 for (int i=1;i<=n;i++) { scanf("%d",&a[i]); if (a[i]==0) { i--; n--; continue;} mn=min(mn,a[i]);}/*取出最小的an,但是不能为0,很好理解吧*/57 for (int i=1;i<mn;i++) dis[i]=inf;/*设达到每个k*mn+i(i<mn)的最小花费,所以数组dis中只有小于mn的i即可(*/58 spfa();59 printf("%I64d\n",query(R)-query(L-1));60 return 0;61 }
1 /* 2 首先,答案=ans(Bmax)-ans(Bmin-1)//利用差分 3 找出a1到an中的最小值p,则如果可以构造出答案x,就可以构造出答案x+p 4 所以我们只需要对于每个q(0<=q<p),计算出最小的k,使k*p+q能够能够被构造出来,那么对于k’(k’>k) k’*p+q也能构造出来 5 所以对于每个q建一个点,对于每个ai,从q向(q+ai)%p连一条长度为ai的边,先跑一遍最短路,计算出得到每个q的最小花费,如果最小花费大于了Bmax,那么没有办法凑出了。否则就计算可以凑出多少个。 6 7 */ 8 #define N 15 9 #define S 500010 //注意题目时5*1e510 #include<iostream>11 using namespace std;12 #include<cstdio>13 #include<queue>14 typedef long long ll;15 ll L,R;16 bool vis[S]={0};17 int n,mn=(1<<31)-1,a[N];18 ll dis[S];19 void input()20 {21 cin>>n>>L>>R;22 for(int i=1;i<=n;++i)23 {24 scanf("%d",&a[i]);25 if(a[i]==0)26 {27 i--;n--;28 continue;29 } 30 mn=min(mn,a[i]);31 }32 }33 void spfa()34 {35 queue<int>Q;36 Q.push(0);37 vis[0]=true;38 dis[0]=0;/*注意得到0的花费是0*/39 int x,y;40 while(!Q.empty())41 {42 x=Q.front();Q.pop();43 vis[x]=false;44 for(int i=1;i<=n;++i)45 {46 y=(x+a[i])%mn;47 if(dis[y]>dis[x]+a[i])48 {49 dis[y]=dis[x]+a[i];50 if(!vis[y])51 {52 vis[y]=true;53 Q.push(y);54 }55 }56 }57 }58 }59 ll query(ll x)60 {61 ll ans=0;62 for(int i=0;i<mn;++i)/*别忘了从0开始循环,因为凑出的是0,可以全部用mn来凑*/63 if(dis[i]<=x) ans+=(x-dis[i])/mn+1;64 return ans;65 }66 int main()67 {68 input();69 for(int i=0;i<mn;++i)70 dis[i]=100000000000000000LL;//当赋值longlong的数时,要加后缀ll(大小写都可以)才可以,否则会出错的。 71 spfa();72 cout<<query(R)-query(L-1);73 return 0;74 }
数论+spfa算法 bzoj 2118 墨墨的等式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。