直接放学长的讲解还有代码算了.....
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<algorithm> #define rg register #define ll long long #define LDB long double #define ull unsigned long long #define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt) #define go(i,x,a) for(rg int i=a;i<x;i++) #define inf 0x3f3f3f3f #define INF 0x7fffffff using namespace std; const int maxn=5e5+5; int n,hd[maxn],k,a[maxn],vis[maxn]; ll L,R,dis[maxn]; struct edd{ int nt,v,w; }e[maxn*20]; inline ll rd(){ ll ret=0,af=1; char gc=getchar(); while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); } while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar(); return ret*af; } inline void add(int a,int b,int c){ e[k].v=b; e[k].w=c; e[k].nt=hd[a]; hd[a]=k++; } void spfa(){ memset(dis,-1,sizeof(dis)); deque<int>q; /*go(i,n+1,1){ int x=a[i]%a[1]; if(dis[x] == -1) dis[x]=a[i],q.push_back(x),vis[x]=1; else dis[x]=min(dis[x],(ll)a[i]); }*/ q.push_back(0); vis[0]=1; dis[0]=0; while(!q.empty()){ int x=q.front(); q.pop_front(); vis[x]=0; for(rg int i=hd[x];i!=-1;i=e[i].nt){ int v=e[i].v,w=e[i].w; if(dis[v] == -1 || dis[v] > dis[x]+w){ dis[v]=dis[x]+w; if(!vis[v]){ if(q.empty()) q.push_back(v); else if(dis[v] < dis[q.front()]) q.push_front(v); else q.push_back(v); vis[v]=1; } } } } } inline ll cal(ll m){ ll ans=0; go(i,a[1],0){ if(dis[i] > m || dis[i] == -1) continue; ans=ans+(m-dis[i])/a[1]+1; } return ans; } int main(){ #ifndef ONLINE_JUDGE freopen("3.in","r",stdin); //freopen(".out","w",stdout); #endif memset(hd,-1,sizeof(hd)); k=0; n=rd(); L=rd(); R=rd(); go(i,n+1,1) a[i]=rd(); sort(a+1,a+n+1); go(i,a[1],0) go(j,n+1,2) add(i,(i+a[j])%a[1],a[j]); spfa(); printf("%lld",cal(R)-cal(L-1)); return 0; }//Faze
upd2019.9.16
#include<bits/stdc++.h> using namespace std; #define Max(x,y) ((x)>(y)?(x):(y)) #define Min(x,y) ((x)<(y)?(x):(y)) #define ll long long const int N=12+10,M=500000+10,inf=0x3f3f3f3f; int n,a[N]; ll b1,b2,ans=0; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[M],tot=0; struct edge{int v,w,nxt;}e[M*20]; void add(int u,int v,int w){ e[++tot]=(edge){v,w,head[u]},head[u]=tot; } queue<int>q;bool vis[M]; ll dis[M]; void spfa(){ memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); q.push(0),vis[0]=1,dis[0]=0; while(!q.empty()){ int u=q.front();q.pop(),vis[u]=0; for(int i=head[u],v,w;i;i=e[i].nxt) if(dis[v=e[i].v]>dis[u]+(w=e[i].w)){ dis[v]=dis[u]+w; if(!vis[v]) q.push(v),vis[v]=1; } } } int main(){ freopen("in.txt","r",stdin); rd(n),rd(b1),rd(b2); for(int i=1;i<=n;++i) rd(a[i]); sort(a+1,a+n+1); for(int i=0;i<a[1];++i) for(int j=2;j<=n;++j) add(i,(i+a[j])%a[1],a[j]); spfa(); for(int i=0;i<a[1];++i){ if(dis[i]<=b1-1) ans-=(b1-1-dis[i])/a[1]+1; if(dis[i]<=b2) ans+=(b2-dis[i])/a[1]+1; } printf("%lld",ans); return 0; }