Bzoj2118 墨墨的等式

Time Limit: 10 Sec Memory Limit: 259 MB
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

Sample Output

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通过

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define LL long long

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct edge{

     int v,nxt;

     LL dis;

 }e[mxn*];

 int hd[mxn],mct=;

 void add_edge(int u,int v,LL dis){

     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].dis=dis;hd[u]=mct;return;

 }

 int n;

 LL B1,B2;

 LL dis[mxn];

 int a[];

 bool inq[mxn];

 queue<int>q;

 void SPFA(){

     memset(dis,0x3f,sizeof dis);

     q.push();inq[]=;dis[]=;

     while(!q.empty()){

         int u=q.front();q.pop();inq[u]=;

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

             if(dis[v]>dis[u]+e[i].dis){

                 dis[v]=dis[u]+e[i].dis;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

     }

     return;

 }

 LL query(LL x){

     LL res=;

     for(int i=;i<a[];i++){

         if(dis[i]<=x)res+=(x-dis[i])/(LL)a[]+;

     }

     return res;

 }

 int main()

 {

     scanf("%d%lld%lld\n",&n,&B1,&B2);

     int i,j;

     for(i=;i<=n;i++){

         a[i]=read();

         if(!a[i]){i--;n--;}

     }

     sort(a+,a+n+);

     for(i=;i<=n;i++)

         for(j=;j<a[];j++){

             add_edge(j,(j+a[i])%a[],a[i]);

         }

     SPFA();

 //    for(i=0;i<a[1];i++)printf("%d ",dis[i]);

     LL ans=query(B2)-query(B1-);

     printf("%lld\n",ans);

     return ;

 }

邻接表

二：改成了不具体建边的写法，只需要1000+ms

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define LL long long

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 LL B1,B2;

 LL dis[mxn];

 int a[];

 bool inq[mxn];

 queue<int>q;

 void SPFA(){

     memset(dis,0x3f,sizeof dis);

     q.push();inq[]=;dis[]=;

     while(!q.empty()){

         int u=q.front();q.pop();inq[u]=;

         for(int i=;i<=n;i++){

             int v=(u+a[i])%a[];

             if(dis[v]>dis[u]+a[i]){

                 dis[v]=dis[u]+a[i];

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

     }

     return;

 }

 LL query(LL x){

     LL res=;

     for(int i=;i<a[];i++){

         if(dis[i]<=x)res+=(x-dis[i])/(LL)a[]+;

     }

     return res;

 }

 int main()

 {

     scanf("%d%lld%lld\n",&n,&B1,&B2);

     int i,j;

     for(i=;i<=n;i++){

         a[i]=read();

         if(!a[i]){i--;n--;}

     }

     sort(a+,a+n+);

     SPFA();

     LL ans=query(B2)-query(B1-);

     printf("%lld\n",ans);

     return ;

 }

秒客网