【BZOJ 2118】 2118: 墨墨的等式 （最短路）

时间：2024-10-23 18:36:32

2118: 墨墨的等式

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

5

HINT

对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

Source

【分析】

　　看了好久题解，感觉好机智啊。。

　　题目可以理解成经典的背包问题。只是他问你的是[L,R]区间中有多少个容积是恰好可以装满的。

　　然后这个范围很大啊，传统的暴力当然是行不通的了。

　　考虑一个可以被拼出来的x，他里面可以包含ai也可以不包含ai。设x%ai=b(0<=b<ai)

　　那么其实x+ai都可以被拼出来，显然。

　　所以我们只要对于一个b，求出最小的可以拼出来的x，那么一直加ai也是可以的。

　　直接把不同的b算出来的答案加起来就好了。

　　要证明的话只要说明两个东西：

　　1、不重复性，对于不同的可以拼出的x1,x2,如果他们%ai不同，那就不会算重复。

　　　　如果他们%ai相同，也不会算重复【233我在搞笑？】

　　2、不遗漏性，对于可以拼出来的x1，有一个模对应的b，那么肯定会算到嘛= =【233

　　所以就这样搞笑的证明了？？

　　【想出来的人思路真的很妙【我根本看不出是最短路啊ORZ。。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<vector>

 using namespace std;

 #define LL long long

 #define Maxm 7000100

 #define Maxn 500010

 #define INF 1000000000000LL

 int a[];

 struct node

 {

     int x,y,next;

     LL c;

 }t[Maxm];int len=;

 // vector<int > e[Maxn],c[Maxn];

 int first[Maxn];

 void ins(int x,int y,LL c)

 {

     t[++len].x=x;t[len].y=y;t[len].c=c;

     t[len].next=first[x];first[x]=len;

 }

 LL dis[Maxn];

 bool inq[Maxn];

 queue<int > q;

 void spfa()

 {

     int st=;

     while(!q.empty()) q.pop();

     memset(inq,,sizeof(inq));

     // memset(dis,63,sizeof(dis));

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

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

     while(!q.empty())

     {

         int x=q.front();

         for(int i=first[x];i;i=t[i].next)

         {

             int y=t[i].y;

         // for(int i=0;i<e[x].size();i++)

         // {

             // int y=e[x][i];

             if(dis[y]>dis[x]+t[i].c)

             {

                 dis[y]=dis[x]+t[i].c;

                 // dis[y]=dis[x]+c[x][i];

                 while(!inq[y])

                 {

                     inq[y]=;

                     q.push(y);

                 }

             }

         }

         inq[x]=;

         q.pop();

     }

 }

 LL get_ans(LL x,LL y)

 {

     if(x<y) return ;

     return (x-y)/a[]+;

 }

 int main()

 {

     int n;

     LL L,R;

     scanf("%d%lld%lld",&n,&L,&R);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     sort(a+,a++n);

     memset(first,,sizeof(first));

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

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

      {

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

      }

     spfa();

     LL ans=;

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

         ans+=get_ans(R,dis[i])-get_ans(L-,dis[i]);

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

     return ;

 }

WA了很久竟然是spfa打错了。。。

2017-01-13 19:05:54

相关文章