题意
n<=30000,m<=30000
题解
暴力的话就是直接建边跑spfa最短路
然而直接建边看上去复杂度正确,实际最多会建$n^2$条边,
看上去复杂度正确如何不试一试,
$dis[x][y]$表示位置$x$有一只跳跃长度为y的狗
炸空间十分严重30000*30000开不下
,考虑分块,这样就不炸空间了
$dis[0][x][y]$表示位置$x$有一只跳跃长度为y的狗
$dis[1][x][y]$表示$id$为$x$的狗目前跳到了能跳的第$y$个位置
以200为分界线dis[2][30000][200]就行了
由于数据比较水,你分块完就AC了,只是一种优化的暴力就可以水过这个题
但这实在不失为优化空间的一种好方法
水过的代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 31000 #define maxn 215 ll dis[2][A][maxn],vis[A][maxn],rec[A],b[A],p[A],st[A]; ll flag[2][A][maxn]; ll n,m,ans; vector <ll> v[A]; vector <ll> dog[A]; struct node{ ll opt,pla,x; node(){} node(const ll &a,const ll &b,const ll &c){opt=a,pla=b,x=c;} }; queue<node> q; void update(ll x,ll d){ // printf("x=%lld d=%lld ",x,d); if(!rec[x]){ for(ll i=0;i<dog[x].size();i++){ ll h=dog[x][i]; if(dis[1][h][st[h]]>d){ dis[1][h][st[h]]=d; q.push(node(1,h,st[h])); } } for(ll i=1;i<200;i++){ if(vis[x][i]){ if(dis[0][x][i]>d){ dis[0][x][i]=d; // printf("**********i=%lld ",i); q.push(node(0,x,i)); } } } rec[x]=1; } } void spfa(){ memset(dis,0x3f,sizeof(dis)); if(p[0]>=200){ q.push(node(1,0,st[p[0]])); dis[1][0][st[p[0]]]=0; } else { q.push(node(0,b[0],p[0])); dis[0][b[0]][p[0]]=0; } update(b[0],0); while(!q.empty()){ node u=q.front(); q.pop(); flag[u.opt][u.pla][u.x]=0; ll d=dis[u.opt][u.pla][u.x]; // printf("dis=%lld opt=%lld pla=%lld x=%lld ",dis[u.opt][u.pla][u.x],u.opt,); if(u.opt==0){ if(u.pla+u.x<=n) if(dis[0][u.pla+u.x][u.x]>d+1){ dis[0][u.pla+u.x][u.x]=d+1; if(!flag[0][u.pla+u.x][u.x]){ flag[0][u.pla+u.x][u.x]=1; q.push(node(0,u.pla+u.x,u.x)); } update(u.pla+u.x,d+1); } if(u.pla-u.x>=0) if(dis[0][u.pla-u.x][u.x]>d+1){ dis[0][u.pla-u.x][u.x]=d+1; if(!flag[0][u.pla-u.x][u.x]){ flag[0][u.pla-u.x][u.x]=1; q.push(node(0,u.pla-u.x,u.x)); } update(u.pla-u.x,d+1); } } else{ if(u.x>=1) if(dis[1][u.pla][u.x-1]>d+1){ dis[1][u.pla][u.x-1]=d+1; if(!flag[1][u.pla][u.x-1]){ flag[1][u.pla][u.x-1]=1; q.push(node(1,u.pla,u.x-1)); } update(v[u.pla][u.x-1],d+1); } if(u.x+1<v[u.pla].size()) if(dis[1][u.pla][u.x+1]>d+1){ dis[1][u.pla][u.x+1]=d+1; if(!flag[1][u.pla][u.x+1]){ flag[1][u.pla][u.x+1]=1; q.push(node(1,u.pla,u.x+1)); } update(v[u.pla][u.x+1],d+1); } } } } int main(){ scanf("%lld%lld",&n,&m); for(ll i=0;i<m;i++){ scanf("%lld%lld",&b[i],&p[i]); if(p[i]>=200){ dog[b[i]].push_back(i); ll k=b[i]; while(k>=p[i]) k-=p[i]; while(k<=n){ v[i].push_back(k); if(k==b[i]){ st[i]=v[i].size()-1; } k+=p[i]; } } else vis[b[i]][p[i]]=1; } spfa(); ans=0x3f3f3f3f; if(p[1]>=200){ ans=min(ans,dis[1][1][st[1]]); } else { ans=min(ans,dis[0][b[1]][p[1]]); } if(ans>=1000000) printf("-1 "); else printf("%lld ",ans); }
然而当p很小还是会建很多条边,如果p全是1你会挂仍然会被卡成sb
作为一个有脸的人是需要打正解的
正解是分块+建虚点
建边最多会达到$n^2$,通常遇到建边很多的题都可以建虚点解决
这个题也可以建虚点
每只狗能跳长度是确定的,一直狗起始点$b[i]$,它能跳的就是$b[i]+p[i]*1$,$b[i]+p[i]*2$,$b[i]+p[i]*3$
类似于同余系最短路,我们可以在p[i]->p[i]*2,p[i]*2之->p[i]间建代价为1的边
在b[i]->底层建代价为0的边,每个虚点向外界连代价0的边
考虑每个>200的点最多建$sqrt{n}$个边,<200建完虚点也只会最多$sqrt{n}$个边
总建边数量$n*sqrt{n}$可过
建边代码
for (ll i=1;i<=t;i++) for (ll j=0;j<i;j++) for (ll k=j;k<n;k+=i){ pos[i][k]=++cnt; add(cnt,k,0); if (k>=i){ add(cnt,cnt-1,1); add(cnt-1,cnt,1); } } for(ll i=0;i<m;i++){ if(p[i]<=t){ add(b[i],pos[p[i]][b[i]],0); } else { for(ll j=1;j;j++){ if(b[i]+p[i]*j>=n) break; add(b[i],p[i]*j+b[i],j); } for(ll j=1;j;j++){ if(b[i]-p[i]*j<0) break; add(b[i],b[i]-p[i]*j,j); } } }
总代码
#include<bits/stdc++.h> using namespace std; #define ll int #define A 16100000 #define maxn 215 ll dis[A],flag[A],b[30100],p[30100],pos[maxn][30100],head[A],nxt[A],edg[A],ver[A]; ll n,m,ans,cnt,t,tot; void add(ll x,ll y,ll z){ // printf("tot=%d ",tot); // if(tot>10000000) printf("tot=%d ",tot); nxt[++tot]=head[x],head[x]=tot,edg[tot]=z,ver[tot]=y; } void spfa(ll w){ for(ll i=0;i<=cnt;i++) dis[i]=1e9; queue<ll> q; q.push(w); dis[w]=0; while(!q.empty()){ ll x=q.front(); q.pop(); flag[x]=0; 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(!flag[y]){ flag[y]=1; q.push(y); } } } } } int main(){ // freopen("zj.in","r",stdin); scanf("%d%d",&n,&m); for(ll i=0;i<m;i++){ scanf("%d%d",&b[i],&p[i]); } t=min((ll)sqrt(n),100); cnt=n-1; for (ll i=1;i<=t;i++) for (ll j=0;j<i;j++) for (ll k=j;k<n;k+=i){ pos[i][k]=++cnt; add(cnt,k,0); if (k>=i){ add(cnt,cnt-1,1); add(cnt-1,cnt,1); } } for(ll i=0;i<m;i++){ if(p[i]<=t){ add(b[i],pos[p[i]][b[i]],0); } else { for(ll j=1;j;j++){ if(b[i]+p[i]*j>=n) break; add(b[i],p[i]*j+b[i],j); } for(ll j=1;j;j++){ if(b[i]-p[i]*j<0) break; add(b[i],b[i]-p[i]*j,j); } } } spfa(b[0]); ans=dis[b[1]]; if(ans>1000000) printf("-1 "); else printf("%d ",ans); }
ps:极限数据还是会建15000000条边,需要对空间做很好把控