BZOJ 2118 墨墨的等式 (同余最短路)

题目大意:已知B的范围,求a1x1+a2x2+...+anxn==B存在非负正整数解的B的数量,N<=12,ai<=1e5,B<=1e12

同余最短路裸题

思想大概是这样的,我们选定一个最小的$ai$,让其他的数用最小的代价去拼凑取余a1之后的数,这其实可以看成求最短路的过程

想象图中有amin个点(0~amin-1),$k$和$k+ai$之间连了一条长度为ai的边,通过跑最短路的方式,尽可能得去拼凑出取余amin以后的余数的最小花费

绝对不写spfa

 1 #include <queue>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #define ll long long
 6 #define N 400010
 7 #define uint unsigned int
 8 #define inf 0x3f3f3f3f3f3f3fll
 9 using namespace std;
10  
11 int n,use[N];
12 ll a[N],amin;
13 ll dis[N],bmin,bmax;
14 struct node{
15     int id;ll d;
16     friend bool operator<(const node &s1,const node &s2){
17         return s1.d>s2.d;}
18     node(int id,ll d):id(id),d(d){}
19     node(){}
20 };
21 ll dijkstra()
22 {
23     priority_queue<node>q;
24     memset(dis,0x3f,sizeof(dis));
25     dis[0]=0;
26     q.push(node(0,0));
27     while(!q.empty()){
28         node k=q.top();q.pop();int x=k.id;
29         if(use[x]) continue;use[x]=1;
30         for(int i=2;i<=n;i++){
31             ll v=(x+a[i])%amin;
32             if(dis[v]>dis[x]+a[i]){
33                 dis[v]=dis[x]+a[i];
34                 q.push(node(v,dis[v]));
35             }
36         }
37     }
38 }
39  
40 int main()
41 {
42     scanf("%d%lld%lld",&n,&bmin,&bmax);
43     for(int i=1;i<=n;i++)
44         scanf("%lld",&a[i]);
45     sort(a+1,a+n+1);
46     amin=a[1];
47     dijkstra();
48     ll ans=0;
49     for(int i=0;i<amin;i++){
50         if(dis[i]<inf&&bmax>=dis[i])
51             ans+=(bmax-dis[i])/amin+1-((bmin-1-dis[i]>0)?((bmin-1-dis[i])/amin+1):0); //floor
52     }
53     printf("%lld
",ans);
54     return 0;
55 }
原文地址:https://www.cnblogs.com/guapisolo/p/9810928.html