每日一题倍增专题总结

本期每日一题的题目大概分成两种倍增：树上倍增和解决综合问题的倍增
倍增的大致思想是利用二进制优化，来加快我们做一个事情，或者找到一个东西的过程，我们通常可以利用二进制拆分，或者是二分的思想在一个log级别的时间内快速求出我们想要的答案！
我们分别介绍一下：
首先是树上倍增，这个比较基础也是会经常考察到的一个知识点：
[AHOI2008]MEET 紧急集合
这道题比较简单，我们手玩几类基本的情况发现情况无非就是其中关键点的lca中的一个，我们一一判断就可以了
然后我们用倍增LCA求一下距离就可以了，算是一道模板题
代码：

#include<bits/stdc++.h>
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<"-----------------------"<<endl
#define ULL unsigned long long
#define DB double
#define pii pair<int,int>
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 500020
int n,Q,tot,to[M<<1],nt[M<<1],fs[M];
int dep[M],fa[M][21];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;~i;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    for(int i=20;~i;--i) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
    return (x==y)?x:fa[x][0]; 
}
inline int getdis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
inline int Calc(int x,int y,int z,int pos){return getdis(x,pos)+getdis(y,pos)+getdis(z,pos);}
inline void dfs(int x,int last=0){
    dep[x]=dep[last]+1,fa[x][0]=last;
    for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last) dfs(to[i],x);
}

int main(){
    n=read(),Q=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
    dfs(1);
    while(Q--){
        int x=read(),y=read(),z=read(),ans,
            XY=getdis(x,y),XZ=getdis(x,z),YZ=getdis(y,z),
            xy=lca(x,y),xz=lca(x,z),yz=lca(y,z); 
        if(XY==XZ+YZ) ans=z;
        else if(XZ==XY+YZ) ans=y;
        else if(YZ==XY+XZ) ans=x;
        else ans=lca(lca(x,y),z);
        if(Calc(x,y,z,xy)<Calc(x,y,z,ans)) ans=xy;
        if(Calc(x,y,z,xz)<Calc(x,y,z,ans)) ans=xz;
        if(Calc(x,y,z,yz)<Calc(x,y,z,ans)) ans=yz;
        printf("%d %d\n",ans,Calc(x,y,z,ans));
    } 
    return 0;
}

但是这里我们注意的是需要备注一下因为这个倍增的常数过大，过不了，那么我们要用树链剖分lca才能通过本题！
附上树链剖分的代码：

#include<bits/stdc++.h>
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<"-----------------------"<<endl
#define ULL unsigned long long
#define DB double
#define pii pair<int,int>
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 500020
int n,Q,tot,to[M<<1],nt[M<<1],fs[M];
int dep[M],fa[M],sz[M],id,top[M],mxs[M],dfn[M];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline int lca(int x,int y){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return (dep[x]<dep[y])?x:y;
}
inline int getdis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
inline int Calc(int x,int y,int z,int pos){return getdis(x,pos)+getdis(y,pos)+getdis(z,pos);}
inline void dfs(int x,int last=0){
    dep[x]=dep[last]+1,fa[x]=last,sz[x]=1;
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last){
        dfs(to[i],x),sz[x]+=sz[to[i]];
        if(sz[to[i]]>sz[mxs[x]]) mxs[x]=to[i];
    }
}
inline void dfst(int x,int t=1){
    dfn[x]=++id,top[x]=t; if(mxs[x]) dfst(mxs[x],t);
    for(int i=fs[x];i;i=nt[i]) if((to[i]^fa[x])&&(to[i]^mxs[x])) dfst(to[i],to[i]);
}

int main(){
    n=read(),Q=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
    dfs(1),dfst(1);
    while(Q--){
        int x=read(),y=read(),z=read(),ans,
            XY=getdis(x,y),XZ=getdis(x,z),YZ=getdis(y,z),
            xy=lca(x,y),xz=lca(x,z),yz=lca(y,z); 
        if(XY==XZ+YZ) ans=z;
        else if(XZ==XY+YZ) ans=y;
        else if(YZ==XY+XZ) ans=x;
        else ans=lca(lca(x,y),z);
        if(Calc(x,y,z,xy)<Calc(x,y,z,ans)) ans=xy;
        if(Calc(x,y,z,xz)<Calc(x,y,z,ans)) ans=xz;
        if(Calc(x,y,z,yz)<Calc(x,y,z,ans)) ans=yz;
        printf("%d %d\n",ans,Calc(x,y,z,ans));
    } 
    return 0;
}

A and B and Lecture Rooms
这也是一道简单题，思想不是很难，关键是我们求出那个中间点，剩下的几种情况判断一下即可，主要还是考察倍增LCA
可以类比上道题，代码：

#include<bits/stdc++.h>
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<"-----------------------"<<endl
#define ULL unsigned long long
#define DB double
#define pii pair<int,int>
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 500020
int n,Q,tot,to[M<<1],nt[M<<1],fs[M];
int dep[M],fa[M],sz[M],id,top[M],mxs[M],dfn[M];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline int lca(int x,int y){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return (dep[x]<dep[y])?x:y;
}
inline int getdis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
inline int Calc(int x,int y,int z,int pos){return getdis(x,pos)+getdis(y,pos)+getdis(z,pos);}
inline void dfs(int x,int last=0){
    dep[x]=dep[last]+1,fa[x]=last,sz[x]=1;
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last){
        dfs(to[i],x),sz[x]+=sz[to[i]];
        if(sz[to[i]]>sz[mxs[x]]) mxs[x]=to[i];
    }
}
inline void dfst(int x,int t=1){
    dfn[x]=++id,top[x]=t; if(mxs[x]) dfst(mxs[x],t);
    for(int i=fs[x];i;i=nt[i]) if((to[i]^fa[x])&&(to[i]^mxs[x])) dfst(to[i],to[i]);
}

int main(){
    n=read(),Q=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
    dfs(1),dfst(1);
    while(Q--){
        int x=read(),y=read(),z=read(),ans,
            XY=getdis(x,y),XZ=getdis(x,z),YZ=getdis(y,z),
            xy=lca(x,y),xz=lca(x,z),yz=lca(y,z); 
        if(XY==XZ+YZ) ans=z;
        else if(XZ==XY+YZ) ans=y;
        else if(YZ==XY+XZ) ans=x;
        else ans=lca(lca(x,y),z);
        if(Calc(x,y,z,xy)<Calc(x,y,z,ans)) ans=xy;
        if(Calc(x,y,z,xz)<Calc(x,y,z,ans)) ans=xz;
        if(Calc(x,y,z,yz)<Calc(x,y,z,ans)) ans=yz;
        printf("%d %d\n",ans,Calc(x,y,z,ans));
    } 
    return 0;
}

疫情控制
这是一道比较综合的题目，还是不错的，有一定的思维难度和代码难度
一眼二分答案，接下来就是判定性的问题了，我觉得这个还是没什么好说的了
首先我们发现在我们力所能及的情况下，我们尽可能要让每个点都尽可能靠根，这样我们就可以尽可能做到最优放置，但是题目中比较繁琐的一个条件是我们的根节点不能放，
这样产生了其他情况，我们需要考虑一个点跨过了根节点那么覆盖那个点呢，一种比较直观的情况是我们长的覆盖长的，这个思想是可以的，只不过我们如果这个长的覆盖当前长的，如果当前这个点已经可以被自己子树里面的覆盖我们就continue掉，这样大概就对了，于是产生了很多细节，我们首先要判断掉不能跨过的情况，然后我们查看1的儿子中的子树在已知的情况是否被覆盖满，这个大概用一个类似于树形DP的思想一遍DFS就行了，剩下我们的难点是考虑每个点能到达最靠近根的点是哪个，然后我们可以用倍增的思想求出来，还是和倍增LCA的具体实现有异曲同工之妙的，大家可以看一下我的代码。
同时这道题启发我们的是，我们在很多匹配问题都可以无脑贪心，按sz或者长度权值等等匹配，然后判断一些已知的情况，这样可以省去很多分类讨论，包括我们可以这样骗分！
代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ----------------------------------- "<<endl
#define pii pair<int,int>
#define ULL unsigned long long
#define DB double
#define uint unsigned int
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
inline int read(){
    int nm=0,fh=1; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-1;
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return nm*fh;
}
#define M 50020
#define INF 1000000000000000000ll
int tot,to[M<<1],len[M<<1],nt[M<<1],fs[M];
int n,m,a[M],dep[M],fa[M][21],Hv[M];
bool F[M]; LL dis[M],mn[M]; multiset<LL>s;
#define IT multiset<LL>::iterator
inline void link(int x,int y,int z){to[++tot]=y,len[tot]=z,nt[tot]=fs[x],fs[x]=tot;}
inline int Getup(int x,LL y){
    LL dx=dis[x];
    for(int k=20;~k;--k)
        if((dep[x]>(1<<k))&&dis[fa[x][k]]>=dx-y) x=fa[x][k];
    return x;
}
inline void dfs(int x,int last=0){
    dep[x]=dep[last]+1,fa[x][0]=last;
    for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last)
        dis[to[i]]=dis[x]+(LL)len[i],dfs(to[i],x);
}
inline void dfst(int x,int last=0){
    bool flag=true;
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last)
        dfst(to[i],x),flag&=F[to[i]],Hv[x]+=Hv[to[i]],mn[x]=min(mn[x],mn[to[i]]);
    if(!F[x]&&Hv[x]) F[x]=flag;
}
inline void Ers(int x){IT it=s.lower_bound(x); s.erase(it);}
inline LL Getmx(){IT it=s.end(); --it; return *it;}
inline void Ersmx(){IT it=s.end(); --it; s.erase(it);}
pii sta[M];
inline bool cmp(pii a,pii b){return a.sc>b.sc;}
inline bool Jud(LL x){
    memset(Hv,0,sizeof(Hv)),memset(F,false,sizeof(F));
    for(int i=1;i<=n;i++) mn[i]=INF; s.clear();
    for(int i=1;i<=m;i++){
        if(dis[a[i]]<=x){s.insert(x-dis[a[i]]),Hv[a[i]]++,mn[a[i]]=x-dis[a[i]]; continue;}
        int pos=Getup(a[i],x); F[pos]=true;
    } dfst(1); int top=0;
    //for(IT it=s.begin();it!=s.end();it++) printf("%d ",*it); puts("");fgx;
    for(int i=fs[1];i;i=nt[i]) if(!F[to[i]]) sta[++top]=mpt(to[i],len[i]);
    sort(sta+1,sta+top+1,cmp);    
    //puts("Sta"); for(int i=1;i<=top;i++) printf("%d %d\n",sta[i].fr,sta[i].sc);
    for(int i=1,x;i<=top;i++){
        if(s.empty()) return false;
        x=sta[i].fr; LL now=Getmx();
        if(Hv[x]&&now>=mn[x]){Ers(mn[x]);continue;} 
        if(now<sta[i].sc) return false; Ersmx();
    } return true;
}
inline LL Getans(LL l,LL r){
    LL ans=r;
    for(LL k=60;~k;k--){
        LL tmp=ans-(1ll<<k);
        if(tmp>=l&&Jud(tmp)) ans=tmp;
    } return ans;
}

int main(){
    n=read();
    for(int i=1,x,y,z;i<n;i++) x=read(),y=read(),z=read(),link(x,y,z),link(y,x,z);
    m=read(); for(int i=1;i<=m;i++) a[i]=read();
    dfs(1),printf("%lld\n",Getans(0,1e15));
    return 0;
}

剩下我们来讲一下普通倍增的问题，这类题目通常有个共性，就是有点类似与二分，其实我们这类问题见多了自然就会有感觉了！
下面讲讲几道例题吧。
[SCOI2015]国旗计划
套路解题，破环为链，然后我们发现就可以二分了，我们只需要按照贪心的思想尽可能靠后，然后维护一个倍增数组，代表跳跃的意思，大概可以感性理解一下。
代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ----------------------------------- "<<endl
#define pii pair<int,int>
#define ULL unsigned long long
#define DB double
#define uint unsigned int
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
inline int read(){
    int nm=0,fh=1; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-1;
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return nm*fh;
}
#define M 200020
#define MAXN 1000020
int n,m,num[MAXN],tail,mx[MAXN],F[MAXN][21];
int N; pii a[M];
inline void ins(int x,int y){mx[x]=max(mx[x],y);}
inline int qry(int x,int y){
    int res=1;
    for(int k=20;~k;k--) if(F[x][k]<y) x=F[x][k],res+=(1<<k);
    return res+1;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i].fr=read(),a[i].sc=read(),num[++tail]=a[i].fr,num[++tail]=a[i].sc;
    sort(num+1,num+tail+1),tail=unique(num+1,num+tail+1)-num-1;
    for(int i=1;i<=n;i++){
        a[i].fr=lower_bound(num+1,num+tail+1,a[i].fr)-num;
        a[i].sc=lower_bound(num+1,num+tail+1,a[i].sc)-num;
        if(a[i].fr<a[i].sc) ins(a[i].fr,a[i].sc),ins(a[i].fr+tail,a[i].sc+tail);
        else ins(a[i].fr,a[i].sc+tail),ins(a[i].fr+tail,tail<<1);
    } N=tail<<1;
    for(int i=1;i<=N;i++) mx[i]=max(mx[i],mx[i-1]);
    for(int i=1;i<=N;i++) F[i][0]=mx[i];
    for(int k=1;k<=20;k++) for(int i=1;i<=N;i++)
        F[i][k]=F[F[i][k-1]][k-1];
    for(int i=1;i<=n;i++){
        if(a[i].fr<a[i].sc) printf("%d",qry(a[i].sc,a[i].fr+tail));
        else printf("%d",qry(a[i].sc+tail,a[i].fr+tail));
        putchar(i<n?' ':'\n');
    }
    return 0;
}

Smile House
我们可以反复进过每个点，然后这也就是一个套路的倍增floyd，我们一边floyd一边二分就可以了，代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=305;
const LL inf=1e18;
int n,m,ans;LL e[11][N][N],dis[N][N],cp[N][N];bool flcyc;
void chkma(LL &x,LL y){x=x>y?x:y;}
void init(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)e[0][i][j]=dis[i][j]=-inf;}
int main(){
    scanf("%d%d",&n,&m);init();
    for(int i=1,u,v,w,w2;i<=m;i++)scanf("%d%d%d%d",&u,&v,&w,&w2),e[0][u][v]=w,e[0][v][u]=w2;
    for(int t=1;t<=10;t++){
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)e[t][i][j]=e[t-1][i][j];
        for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
            chkma(e[t][i][j],e[t-1][i][k]+e[t-1][k][j]);
    }
    for(int t=10;~t;t--){
        memcpy(cp,dis,sizeof(cp));
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)chkma(cp[i][j],e[t][i][j]);
        for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
            chkma(cp[i][j],dis[i][k]+e[t][k][j]);
        bool fl=false;
        for(int i=1;i<=n;i++)if(cp[i][i]>0){fl=flcyc=true;break;}
        if(!fl)memcpy(dis,cp,sizeof(dis)),ans+=(1<<t);
    }
    if(!flcyc)puts("0");else printf("%d\n",ans+1);
    return 0;
}

[SCOI2016]萌萌哒
这道题是这里最有启发的一题，也是思路非常妙的一题
我们首先发现这是一个并查集的问题，我们维护出连通性以后就可以了，剩下的很简单这里不赘述了，但是关键是我们如何快速求出这个连通性呢，亦或是说我们怎么样快速连边呢，实际上我们这个操作是可以用倍增维护，其实这种区间问题我们也可以转化成倍增维护的，然后我们维护的时候就从大到小维护连边就可以了，其实这个也讲得不太清楚，但是代码非常简单，看一下就可以了！
启发也就是并查集问题可以用倍增搞吧，然后我们区间的问题也可以倍增，感觉倍增思想无处不在，这种区间之间的连边当初会想到线段树优化建图，但是实际上并查集问题我们是可以倍增优化建图的，或者说是上下层的影响，这个思想是非常妙的，我们线段树优化建图其实也可以用倍增做，希望这么讲能对倍增有更深的理解，能解决更多各种各样的问题，来看一下代码吧。

每日一题 倍增专题总结

全站热榜

每日一题倍增专题总结