本期每日一题的题目大概分成两种倍增:树上倍增和解决综合问题的倍增
倍增的大致思想是利用二进制优化,来加快我们做一个事情,或者找到一个东西的过程,我们通常可以利用二进制拆分,或者是二分的思想在一个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]萌萌哒
这道题是这里最有启发的一题,也是思路非常妙的一题
我们首先发现这是一个并查集的问题,我们维护出连通性以后就可以了,剩下的很简单这里不赘述了,但是关键是我们如何快速求出这个连通性呢,亦或是说我们怎么样快速连边呢,实际上我们这个操作是可以用倍增维护,其实这种区间问题我们也可以转化成倍增维护的,然后我们维护的时候就从大到小维护连边就可以了,其实这个也讲得不太清楚,但是代码非常简单,看一下就可以了!
启发也就是并查集问题可以用倍增搞吧,然后我们区间的问题也可以倍增,感觉倍增思想无处不在,这种区间之间的连边当初会想到线段树优化建图,但是实际上并查集问题我们是可以倍增优化建图的,或者说是上下层的影响,这个思想是非常妙的,我们线段树优化建图其实也可以用倍增做,希望这么讲能对倍增有更深的理解,能解决更多各种各样的问题,来看一下代码吧。
#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 100020 #define mod 1000000007 int n,Q,Fd[M][21],tot; inline int find(int x,int k){return (Fd[x][k]==x)?x:(Fd[x][k]=find(Fd[x][k],k));} inline void merge(int x,int y,int k){ int fx=find(x,k),fy=find(y,k); if(fx^fy) Fd[fx][k]=fy; } int main(){ n=read(),Q=read(); for(int k=0;k<=20;k++) for(int i=1;i+(1<<k)-1<=n;i++) Fd[i][k]=i; while(Q--){ int x=read(),y=read(),x2=read(),y2=read(),len=y-x+1; for(int i=20;~i;--i) if(len&(1<<i)) merge(x,x2,i),x+=(1<<i),x2+=(1<<i); } for(int k=20;k;--k) for(int i=1,x;i+(1<<k)-1<=n;i++) x=find(i,k),merge(x,i,k-1),merge(x+(1<<k-1),i+(1<<k-1),k-1); for(int i=1;i<=n;i++) if(find(i,0)==i) tot++; LL ans=9ll; for(int i=1;i<tot;i++) ans=ans*10ll%mod; printf("%lld\n",ans); return 0; }