觉得之前写的跟shi一样，看了我博客的都更懵逼了，重写一部分
同余系最短路
Q:同余系是什么
A:所谓同余系最短路并不是拿同余方程跑最短路,而是跑最短路用同余方程优化
暴力的话就是暴力建边然后跑最短路,然而这样你肯定不行
Q:为什么要最短路
A:假设现在有$a,b,c,Z,e,f$
$a$是$a,b,c$中最小的
现在$e=a*x_1+Z$,$f=a*x_2+Z$
现在有$e<f$,那么有$e+a*y=f$
那么e+a可以凑出来的一些数,f是根本凑不出来的
e可以表示更多数
最短路中dis[o]中o对应的是e,o对应的是Z,我们把Z抽象成一个个位置,这样跑最短路找到用b,c可以凑出%a意义下为u的最小值
实际比如现在有一个数w,先%a得出i,那么dis[i]<=w表示可以凑出来(i可以通过加若干个a得到w),dis[i]若>w表示怎么样也凑不出来(越加越大),
所以要最短路
Q:为什么是对的
A:%a得到(0-a-1)可以证明+若干a达到1-正无穷每个数
解决了上述问题开始看几道题
simple
题解
这里给出一种傻逼做法,同余系最短路,
考虑简单容斥,拿$q-可以达到的解$
在得出一个可以达到的解我们可以任意拓展+任意多别的数达到其他值,我们可以利用这一优良性质
例如现在有$x=1,y=3$,$y$可以达到$3$那么我们可以$3+1*x,3+2*x,3+3*x$得到其他所有解,剩余还能有解的个数就是$(q-dis[i])/x+1$
于是构造在同余于$x$下的同余系,$dis[i]$表示不用$x$在$\%x后=i$需要的最少步数(例如现在有$x$,$y$,$z$,构造同余系$dis[i]$表示单纯用$y,z$到达$i$的最小步数)
为什么要$dis[i]$尽量小,$dis[i]$达到高度小,我们就可以用更多$x$来填充剩下路径
考虑暴力$dp$ $dis[(i+y)\%x]=min(dis[i]+y)$,形式相当于最短路形式,建从$i->(i+y)\%x$边跑$spfa$即可
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 555555 ll head[A],nxt[A],ver[A],edg[A],dis[A],vis[A]; ll t,tot,n,m,q; void add(ll x,ll y,ll z){ nxt[++tot]=head[x],head[x]=tot,ver[tot]=y,edg[tot]=z; } void spfa(ll o){ memset(dis,63,sizeof(dis)); memset(vis,0,sizeof(vis)); deque<ll> q; dis[0]=0; vis[0]=1; q.push_back(0); while(!q.empty()){ ll x=q.front(); q.pop_front(); for(ll i=head[x];i;i=nxt[i]){ ll y=ver[i]; if(dis[y]>dis[x]+edg[i]){ dis[y]=dis[x]+edg[i]; if(!vis[y]){ vis[y]=1; q.push_back(y); } } } vis[x]=0; } } int main(){ scanf("%lld",&t); while(t--){ scanf("%lld%lld%lld",&n,&m,&q); if(n>m) swap(n,m);//n较小值 memset(head,0,sizeof(head)); memset(nxt,0,sizeof(nxt)); tot=0; for(ll i=0;i<n;i++){ add(i,(i+m)%n,m); } spfa(0); ll ans=0; for(ll i=0;i<n;i++){ if(dis[i]<=q) ans+=(q-dis[i])/n+1; } ans--; printf("%lld ",q-ans); } }
跳楼机
题面
求$k_1*x+k_2*y+k_3*z=[1,q]$解个数
题解
同样构造同余系最短路,$dis[i]$和上面定义类似,只用$y,z$走到的点$\%x=i$需要最短距离,
连边$add(i,(i+y)\%x,y)$,$add(i,(i+z)\%x,z)$求解,从当前点走还能走多少步$sumlimits_{i=0}^{i<x} (q-dis[i])/x+1$
代码和上面基本一样不放了
完全背包问题
题解
可以同余系最短路做，套路和上面一样
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define fhAK 666666 ll bag[fhAK],val[fhAK],flag[fhAK],tim[fhAK]; ll n,m,pos,L,C; int main(){ ll mod=0x7fffffffff; scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++){ scanf("%lld",&val[i]); mod=min(mod,val[i]); } sort(val+1,val+n+1); memset(bag,0x3f,sizeof(bag)); memset(tim,0x3f,sizeof(tim)); scanf("%lld%lld",&L,&C); pos=n; for(ll i=1;i<=n;i++){ if(val[i]>=L){ pos=i-1; break; } } deque<ll> q; bag[0]=0,tim[0]=0; q.push_back(0); while(!q.empty()){ ll x=q.front(); q.pop_front(); flag[x]=0; for(ll i=1;i<=n;i++){ ll tmp=(x+val[i])%mod; if(i>pos&&tim[x]==C) break ; if(bag[tmp]>bag[x]+val[i]){ bag[tmp]=bag[x]+val[i]; if(i>pos) tim[tmp]=tim[x]+1; else tim[tmp]=tim[x]; if(!flag[tmp]){ q.push_back(tmp); flag[tmp]=1; } } else if(bag[tmp]==bag[x]+val[i]){ if(i<=pos){ if(tim[tmp]>tim[x]){ tim[tmp]=tim[x]; if(!flag[tmp]){ q.push_back(tmp); flag[tmp]=1; } } } else{ if(tim[tmp]>tim[x]+1){ tim[tmp]=tim[x]+1; if(!flag[tmp]){ q.push_back(tmp); flag[tmp]=1; } } } } } } for(ll i=1;i<=m;i++){ ll w,x; scanf("%lld",&x); w=x%mod; if(bag[w]<=x) printf("Yes "); else printf("No "); } }