P1967 货车运输
*Kruskal重构树模板题。
#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<cctype> #include<algorithm> #include<cstring> #include<iomanip> #include<queue> #include<map> #include<set> #include<bitset> #include<vector> #include<stack> #include<cmath> #include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; const int M=200010; int n,m,cnt,q,fa[M],tot,head[M],val[M],size[M],top[M],son[M],dep[M],f[M]; bool vis[M]; struct node{ int u,v,dis; bool operator < (const node&x) const{ return dis<x.dis; } }e[M]; inline bool cmp(node x,node y){return x.dis>y.dis;} struct Node{ int nxt,to; }ee[M]; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } inline int getfa(int x){ if(x==fa[x]) return x; return fa[x]=getfa(fa[x]); } inline void add(int u,int v){ ee[++tot].nxt=head[u]; head[u]=tot; ee[tot].to=v; } inline void dfs1(int u,int pa){ size[u]=1;vis[u]=1; for(ri i=head[u];i;i=ee[i].nxt){ int v=ee[i].to; if(v==pa)continue; dep[v]=dep[u]+1;f[v]=u; dfs1(v,u); size[u]+=size[v]; if(size[v]>size[son[u]]) son[u]=v; } } inline void dfs2(int u,int tp){ top[u]=tp; if(son[u]) dfs2(son[u],tp); for(ri i=head[u];i;i=ee[i].nxt){ int v=ee[i].to; if(v==son[u]||v==f[u]) continue; dfs2(v,v); } } inline int lca(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]>dep[top[v]]) u=f[top[u]]; else v=f[top[v]]; } return dep[u]<dep[v]?u:v; } inline void kruskal(){ For(i,1,n) fa[i]=i; sort(e+1,e+m+1,cmp); For(i,1,m){ int fu=getfa(e[i].u),fv=getfa(e[i].v); if(fu!=fv){ val[++cnt]=e[i].dis; fa[cnt]=fa[fu]=fa[fv]=cnt; add(fu,cnt),add(cnt,fu); add(fv,cnt),add(cnt,fv); } } For(i,1,cnt){ if(!vis[i]){ int ff=getfa(i); dfs1(ff,0),dfs2(ff,ff); } } } int main(){ n=read(),m=read(),cnt=n; For(i,1,m){ e[i].u=read(),e[i].v=read(),e[i].dis=read(); } kruskal(); q=read(); while(q--){ int u=read(),v=read(); if(getfa(u)!=getfa(v)) printf("-1 "); else printf("%d ",val[lca(u,v)]); } return 0; }
*倍增
P1081 开车旅行
*俩神经病换着还要凭喜好开车的故事...怎么跟小学的憨憨放水进水的奥数题一样...
*70'的暴力我卡在了初始化上，我是想预处理出各个城市的距离再sort，题解是
枚举其实从1到n-1和n-1到1都没有区别。提前处理出四个需要用到的量，其他都不用管这个idea很好。看下我被卡的代码实现，主要是没想到只处理出4个量，按我原来的sort实现不了。
For(i,1,n-1){ ll minn1=i+1,minn2=0; dis1[i]=abs(h[i]-h[i+1]); For(j,i+2,n){ if(dis1[i]>abs(h[i]-h[j])||dis1[i]==abs(h[i]-h[j])&&h[j]<h[minn1]){ dis2[i]=dis1[i],dis1[i]=abs(h[i]-h[j]); minn2=minn1,minn1=j; } else if(!dis2[i]||dis2[i]>abs(h[i]-h[j])||dis2[i]==abs(h[i]-h[j])&&h[j]<h[minn2]){ dis2[i]=abs(h[i]-h[j]); minn2=j; } } c1[i]=minn1,c2[i]=minn2; }
换车那里记录一个turn=1/0，表示a/b开车，统计一下判断是否符合条件即可。
*70'代码：
#include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; const int M=100010; ll n,m,xo,ans,c1[M],c2[M],dis1[M],dis2[M],h[M]; double minv=1e9; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int main(){ n=read(); For(i,1,n) h[i]=read(); For(i,1,n-1){ ll minn1=i+1,minn2=0; dis1[i]=abs(h[i]-h[i+1]); For(j,i+2,n){ if(dis1[i]>abs(h[i]-h[j])||dis1[i]==abs(h[i]-h[j])&&h[j]<h[minn1]){ dis2[i]=dis1[i],dis1[i]=abs(h[i]-h[j]); minn2=minn1,minn1=j; } else if(!dis2[i]||dis2[i]>abs(h[i]-h[j])||dis2[i]==abs(h[i]-h[j])&&h[j]<h[minn2]){ dis2[i]=abs(h[i]-h[j]); minn2=j; } } c1[i]=minn1,c2[i]=minn2; } xo=read(),ans=0; For(i,1,n){ ll a=0,b=0,loc=i,turn=0; while(1){ if(turn){ if(a+b+dis1[loc]>xo||!c1[loc]) break; b+=dis1[loc]; loc=c1[loc]; } else{ if(a+b+dis2[loc]>xo||!c1[loc]) break; a+=dis2[loc]; loc=c2[loc]; } turn^=1; } if(!ans||1.0*a/b-minv<-0.00000001||fabs((1.0*a/b-minv))<=0.00000001&&h[ans]<h[i]){ minv=1.0*a/b; ans=i; } } write(ans);printf(" "); m=read(); while(m--){ ll s=read(),x=read(),a=0,b=0,turn=0; while(1){ if(turn){ if(a+b+dis1[s]>x||!c1[s]) break; b+=dis1[s]; s=c1[s]; } else{ if(a+b+dis2[s]>x||!c1[s]) break; a+=dis2[s]; s=c2[s]; } turn^=1; } write(a);printf(" ");write(b);printf(" "); } return 0; }
*AC代码就是用双向链表初始化+倍增优化，就是多两个优化啦。不多赘述，不会实现的话看->https://www.luogu.org/blog/Zechariah/solution-p1081。
*AC代码：
#include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; const int M=100010; ll c1[M],c2[M],c3[M][21],n,m,pos[M],dis1[M],dis2[M],dis3[M][21],dis4[M][21],dis5[M][21]; double minv=1e9; struct node { ll h; int bh,last,next; }q[M]; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } inline bool cmp(node s,node t){return s.h<t.h;} inline void updata(int i,int loc,int x){ if(x>=1&&x<=n){ if(!dis1[i]||dis1[i]>abs(q[loc].h-q[x].h)||(dis1[i]==abs(q[loc].h-q[x].h)&&q[x].h<q[pos[c1[i]]].h)){ dis2[i]=dis1[i]; dis1[i]=abs(q[loc].h-q[x].h); c2[i]=c1[i]; c1[i]=q[x].bh; } else if(!dis2[i]||dis2[i]>abs(q[loc].h-q[x].h)||(dis2[i]==abs(q[loc].h-q[x].h)&&q[x].h<q[pos[c2[i]]].h)){ dis2[i]=abs(q[loc].h-q[x].h); c2[i]=q[x].bh; } } } int main(){ n=read(); For(i,1,n) q[i].h=read(),q[i].bh=i; sort(q+1,q+n+1,cmp); For(i,1,n){ pos[q[i].bh]=i; if(i!=1)q[i].last=i-1; if (i!=n)q[i].next=i+1; } For(i,1,n){ int loc = pos[i]; updata(i,loc,q[q[loc].last].last); updata(i,loc,q[loc].last); updata(i,loc,q[loc].next); updata(i,loc,q[q[loc].next].next); if(q[loc].last)q[q[loc].last].next=q[loc].next; if(q[loc].next)q[q[loc].next].last=q[loc].last; q[loc].last=q[loc].next=0; } For(i,1,n){ dis4[i][0]=dis2[i]; dis5[i][0]=dis1[c2[i]]; dis3[i][0]=dis2[i]+dis1[c2[i]]; c3[i][0]=c1[c2[i]]; } For(j,1,20) For(i,1,n){ c3[i][j]=c3[c3[i][j-1]][j - 1]; if(c3[i][j]){ dis3[i][j]=dis3[i][j-1]+dis3[c3[i][j-1]][j-1]; dis4[i][j]=dis4[i][j-1]+dis4[c3[i][j-1]][j-1]; dis5[i][j]=dis5[i][j-1]+dis5[c3[i][j-1]][j-1]; } } ll xx=read(),ans=0; For(i,1,n){ ll a=0,b=0,loc=i,x0=xx; Dfor(j,20,0){ if(dis3[loc][j]&&x0>=dis3[loc][j]){ x0-=dis3[loc][j]; a+=dis4[loc][j]; b+=dis5[loc][j]; loc=c3[loc][j]; } } if(dis2[loc]<=x0)a+=dis2[loc]; if(a<=0)continue; if(!ans||1.0*a/b-minv<-0.00000001||(fabs(1.0*a/b-minv)<=0.00000001&&q[pos[ans]].h<q[pos[i]].h)){ minv=1.0*a/b; ans=i; } } write(ans);printf(" "); m=read(); while(m--){ ll s=read(),x=read(),a=0,b=0; Dfor(j,20,0){ if(dis3[s][j]&&x>=dis3[s][j]) { x-=dis3[s][j]; a+=dis4[s][j]; b+=dis5[s][j]; s=c3[s][j]; } } if(dis2[s]<=x)a+=dis2[s]; write(a);printf(" ");write(b);printf(" "); } return 0; }
P1613 跑路
*题面简直就是清清楚楚得把倍增拍你脸上了...2^k都出来了（然而接近10点搞了一天的我却瞎了眼
*直接放代码吧
#include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; int dis[60][60],n,m; bool g[60][60][65]; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } int main(){ n=read();m=read(); memset(dis,10,sizeof(dis)); For(i,1,m){ int u=read(),v=read(); dis[u][v]=1; g[u][v][0]=1; } For(k,1,64){ For(i,1,n){ For(t,1,n){ For(j,1,n){ if(g[i][t][k-1]&&g[t][j][k-1]) dis[i][j]=1,g[i][j][k]=1; } } } } For(k,1,n){ For(i,1,n){ For(j,1,n){ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } } printf("%d ",dis[1][n]); return 0; }