BZOJ2118: 墨墨的等式 思维建图

2019-04-14 19:51发布

站内文章 / 模拟电子
17120 0 984
问a1x1+a2x2+a3x3+……+anxn∈[Bmin,Bmax]中的非负整数解有多少组 由于是非负所以不能简单求gcd，可以考虑任取其中某一项ax， 以它的模域0-ax-1建图，单向通过a数组转移，这样跑出从模0到模任意数的最短路 最短是为了保证在BminBmax里能塞进最多的ax 显然ax取最小可以让复杂度最好，实测取max是min耗时2倍 正确性就是如果m可以取到，那么k*ax+m都可以取到，只要数区间内有多少ax倍数就行，这个用一下前缀和思想就行
至于为什么能任取ax，因为当ax变大，模域也变大，转移路径也会变多，不会因为区间内ax倍数变少而影响正确性 //#include //#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include using namespace std; const double pi=acos(-1.0); #define ll long long #define pb push_back #define sqr(a) ((a)*(a)) #define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)) const double eps=1e-10; const int maxn=6e6+56; const int inf=0x3f3f3f3f; const ll mod=6; ll d[maxn]; int arr[maxn]; bool vis[maxn]; struct NODE{ int d,u; bool operator < (const NODE &rhs)const{ return d>rhs.d; } }; struct EDGE{ int u,v,w,nxt; }G[maxn];int tot,head[maxn]; void addedge(int u,int v,int w){ G[++tot]=(EDGE){u,v,w,head[u]}; head[u]=tot; } void dij(int n){ priority_queueQ; Q.push((NODE){0,0}); for(int i=1;i<=n;i++)d[i]=9e18; while(!Q.empty()){ NODE x=Q.top();Q.pop(); if(vis[x.u])continue;vis[x.u]=1; for(int i=head[x.u];~i;i=G[i].nxt){ if(d[G[i].v]>d[x.u]+G[i].w){ d[G[i].v]=d[x.u]+G[i].w; Q.push((NODE){d[G[i].v],G[i].v}); } } } } int main(){ memset(head,-1,sizeof head); int n;scanf("%d",&n);ll l,r; scanf("%lld%lld",&l,&r);l--; int mn=inf; for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); mn=min(mn,arr[i]); } for(int i=0;i学过平衡树算是明白最短路那个vis的意义了，虽说实测这题数据加了vis反而慢了。。

热门文章