simple,跳楼机,[同余系最短路]
归档于 2019-10-09 09:25
觉得之前写的跟shi一样，看了我博客的都更懵逼了，重写一部分
同余系最短路
Q:同余系是什么
A:所谓同余系最短路并不是拿同余方程跑最短路,而是跑最短路用同余方程优化
暴力的话就是暴力建边然后跑最短路,然而这样你肯定不行
Q:为什么要最短路
A:假设现在有$a,b,c,Z,e,f$
$a$是$a,b,c$中最小的
现在$e=ax_1+Z$,$f=ax_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+1x,3+2x,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\n",q-ans);
}
}
View Code
跳楼机
题面
求$k_1x+k_2y+k_3*z=[1,q]$解个数
题解
同样构造同余系最短路,$dis[i]$和上面定义类似,只用$y,z$走到的点$%x=i$需要最短距离,
连边$add(i,(i+y)%x,y)$,$add(i,(i+z)%x,z)$求解,从当前点走还能走多少步$\sum\limits_{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\n");
else printf("No\n");
}
}
View Code