倍增
分类:
IT文章
•
2024-07-05 10:36:43
很久之前就学习过的算法，但是最近发现很多题目都可以用倍增的方法解决，并且十分好写，所以总结一下。
noip2013 货车运输
题目大意：n各点构成一个无向图，每条边有一个最大负载，有q辆货车，分别从不同的点到不同的点，求每辆货车最大运载量。
思路：为了满足最大负载，肯定是走图的最大生成树上的路径，并且答案就是每次路径上的最小边权。用倍增维护最小边权就可以了。
![]()
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct use{
int xx,yy,va;
}r[50001];
int next[100001]={0},point[10001]={0},en[100001]={0},fa[10001]={0},f[10001][15]={0},
g[10001][15]={0},dep[10001]={0},val[100001]={0};
int my_comp(const use &x,const use &y)
{
if (x.va>y.va) return 1;
else return 0;
}
int rool(int x)
{
if (fa[x]!=x) fa[x]=rool(fa[x]);
return fa[x];
}
void dfs(int x,int i)
{
int j,y;
dep[x]=i;
for (j=1;j<=13;++j)
{
f[x][j]=f[f[x][j-1]][j-1];
g[x][j]=min(g[f[x][j-1]][j-1],g[x][j-1]);
}
y=point[x];
while (y!=0)
{
if (dep[en[y]]==0)
{
f[en[y]][0]=x;
g[en[y]][0]=val[y];
dfs(en[y],i+1);
}
y=next[y];
}
}
int work(int x,int y)
{
int i,j,t,ans;
if (dep[x]>dep[y])
{
t=x;x=y;y=t;
}
ans=2100000000;
for (i=13;i>=0;--i)
{
if (dep[x]<=dep[f[y][i]])
{
ans=min(ans,g[y][i]);
y=f[y][i];
}
}
if (x==y) return ans;
for (i=13;i>=0;--i)
if (f[x][i]!=f[y][i])
{
ans=min(ans,min(g[x][i],g[y][i]));
x=f[x][i];y=f[y][i];
}
ans=min(ans,min(g[x][0],g[y][0]));
return ans;
}
int main()
{
int r1,r2,n,m,q,i,j,x,y,tot=0;
cin>>n>>m;
for (i=1;i<=m;++i)
scanf("%d%d%d",&r[i].xx,&r[i].yy,&r[i].va);
sort(r+1,r+m+1,my_comp);
for (i=1;i<=n;++i)
{
fa[i]=i;
}
for (i=1;i<=m;++i)
{
r1=rool(r[i].xx);
r2=rool(r[i].yy);
if (r1!=r2)
{
++tot;
next[tot]=point[r[i].xx];
point[r[i].xx]=tot;
en[tot]=r[i].yy;
val[tot]=r[i].va;
++tot;
next[tot]=point[r[i].yy];
point[r[i].yy]=tot;
en[tot]=r[i].xx;
val[tot]=r[i].va;
fa[r1]=r2;
}
}
for (i=1;i<=n;++i)
if (dep[i]==0)
dfs(i,1);
cin>>q;
for (i=1;i<=q;++i)
{
scanf("%d%d",&x,&y);
if (rool(x)!=rool(y))
printf("%d
",-1);
else printf("%d
",work(x,y));
}
}
View Code
水果姐逛水果街
题目大意：树上的一条路径，在使后面的权值减去前面的差最大。（变形1：可以修改权值；变形2：可以增加结点。）
思路：对于这种题目倍增或者链剖都可以解决。但是要十分注意信息（最大值、最小值、正着的最大差和反着的最大差）更新的顺序。（变形1：只能用链剖，可以很快的修改和查询；变形2：只能用倍增，因为倍增中，新加入一个点只需要用父亲的信息修改这个点的信息就可以了，不需要改动父亲，所以可以很快的求出。）
可是如果这两种变式结合在一起，该用什么呢？
![]()
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxnode 200005
#define inf 2100000000LL
using namespace std;
int fa[maxnode][20]={0},maxn[maxnode][20]={0},minn[maxnode][20]={0},zcha[maxnode][20]={0},tot=0,
fcha[maxnode][20]={0},ai[maxnode]={0},point[maxnode]={0},next[maxnode*2]={0},en[maxnode*2]={0},
dep[maxnode]={0};
struct use{
int maxn,minn;
};
void add(int u,int v)
{
++tot;next[tot]=point[u];point[u]=tot;en[tot]=v;
++tot;next[tot]=point[v];point[v]=tot;en[tot]=u;
}
void ins(int u,int faa)
{
int i;
fa[u][0]=faa;dep[u]=dep[faa]+1;maxn[u][0]=max(ai[u],ai[faa]);minn[u][0]=min(ai[u],ai[faa]);
zcha[u][0]=max(0,ai[faa]-ai[u]);fcha[u][0]=max(0,ai[u]-ai[faa]);
for (i=1;i<=18;++i)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
zcha[u][i]=max(zcha[u][i-1],max(zcha[fa[u][i-1]][i-1],maxn[fa[u][i-1]][i-1]-minn[u][i-1]));
fcha[u][i]=max(fcha[u][i-1],max(fcha[fa[u][i-1]][i-1],maxn[u][i-1]-minn[fa[u][i-1]][i-1]));
maxn[u][i]=max(maxn[u][i-1],maxn[fa[u][i-1]][i-1]);
minn[u][i]=min(minn[u][i-1],minn[fa[u][i-1]][i-1]);
}
}
void dfs(int u,int faa)
{
int i,j;
ins(u,faa);
for (i=point[u];i;i=next[i])
if ((j=en[i])!=faa) dfs(j,u);
}
int ask(int u,int v)
{
int i,j,ans=0;
use ans1,ans2;
ans1.maxn=ans1.minn=ai[u];ans2.maxn=ans2.minn=ai[v];
if (dep[u]>dep[v])
{
for (i=18;i>=0;--i)
if (dep[fa[u][i]]>=dep[v])
{
ans=max(ans,max(zcha[u][i],maxn[u][i]-ans1.minn));
ans1.maxn=max(ans1.maxn,maxn[u][i]);
ans1.minn=min(ans1.minn,minn[u][i]);
u=fa[u][i];
}
}
else
{
for (i=18;i>=0;--i)
if (dep[fa[v][i]]>=dep[u])
{
ans=max(ans,max(fcha[v][i],ans2.maxn-minn[v][i]));
ans2.maxn=max(ans2.maxn,maxn[v][i]);
ans2.minn=min(ans2.minn,minn[v][i]);
v=fa[v][i];
}
}
if (u==v) return ans;
for (i=18;i>=0;--i)
{
if (fa[u][i]!=fa[v][i])
{
ans=max(ans,max(zcha[u][i],max(maxn[u][i]-ans1.minn,
max(fcha[v][i],ans2.maxn-minn[v][i]))));
ans1.maxn=max(ans1.maxn,maxn[u][i]);
ans1.minn=min(ans1.minn,minn[u][i]);
ans2.maxn=max(ans2.maxn,maxn[v][i]);
ans2.minn=min(ans2.minn,minn[v][i]);
u=fa[u][i];v=fa[v][i];
}
}
ans=max(ans,max(zcha[u][0],maxn[u][0]-ans1.minn));
ans1.maxn=max(ans1.maxn,maxn[u][0]);
ans1.minn=min(ans1.minn,minn[u][0]);
ans=max(ans,max(fcha[v][0],ans2.maxn-ans1.minn));
return ans;
}
int main()
{
freopen("lct.in","r",stdin);
freopen("lct.out","w",stdout);
int n,m,i,j,q,ans=0,kk,u,v;
scanf("%d",&n);
for (i=1;i<=n;++i) scanf("%d",&ai[i]);
for (i=1;i<n;++i)
{
scanf("%d%d",&u,&v);add(u,v);
}
dfs(1,0);scanf("%d",&m);
for (i=1;i<=m;++i)
{
scanf("%d%d%d",&kk,&u,&v);
if (kk==1)
{
u^=ans;v^=ans;ans=ask(u,v);printf("%d
",ans);
}
else
{
v^=ans;ai[++n]=u;ins(n,v);
}
}
fclose(stdin);
fclose(stdout);
}
View Code
bzoj2815 灾难
题目大意：给定不同生物的食用关系（保证无环），求每种生物的灾难值（即它灭绝之后不能存活的生物的个数）。
思路：听他们说这叫灾难树？其实就是考虑这张有向图中某个点所能到的所有点最后汇集到的那个点及那个点的灾难就是它的灾难。所以我们可以从被吃的向吃的拓扑，然后对于拓扑到的点用反向边的终点找到lca就是这个点到的所有点最后汇集的那个灾难，把这个点作为它灾难的儿子，那么一个点的子树大小-1就是这个点的灾难值了。
![]()
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxm 100000
#define maxe 1000000
#define up 21
using namespace std;
int tot=0,n,point[maxm]={0},en[maxe]={0},next[maxe]={0},du[maxm]={0},siz[maxm]={0},
que[maxm],fa[maxm][up]={0},point1[maxm]={0},en1[maxe]={0},next1[maxe]={0},
point2[maxm]={0},next2[maxe]={0},en2[maxe]={0},dep[maxm]={0};
void add(int u,int v){
next[++tot]=point[u];point[u]=tot;en[tot]=v;++du[v];
next1[tot]=point1[v];point1[v]=tot;en1[tot]=u;
}
void add2(int u,int v){next2[++tot]=point2[u];point2[u]=tot;en2[tot]=v;}
int lca(int a,int b){
int i,j;if (dep[a]<dep[b]) swap(a,b);
for (i=20;i>=0;--i)
if (dep[fa[a][i]]>=dep[b]) a=fa[a][i];
if (a==b) return a;
for (i=20;i>=0;--i)
if (fa[a][i]!=fa[b][i]){
a=fa[a][i];b=fa[b][i];
}return fa[a][0];
}
void dfs(int u,int ff){
int i,v;siz[u]=1;
for (i=point2[u];i;i=next2[i])
if ((v=en2[i])!=ff){
dfs(v,u);siz[u]+=siz[v];
}
}
void work(){
int i,j,u,v,head=0,tail=0,ll;que[++tail]=n+1;dep[n+1]=1;
while(head!=tail){
u=que[++head];
for (i=point[u];i;i=next[i]){
--du[v=en[i]];
if (!du[v]){
que[++tail]=v;
for (j=point1[v],ll=en1[j];j;j=next1[j])ll=lca(ll,en1[j]);
add2(ll,v);fa[v][0]=ll;dep[v]=dep[ll]+1;
for (j=1;j<=20;++j) fa[v][j]=fa[fa[v][j-1]][j-1];
}
}
}dfs(n+1,0);
}
int main(){
int i,j,u;scanf("%d",&n);
for(i=1;i<=n;++i){
j=0;
while(scanf("%d",&u)==1){
if (!u) break;add(u,i);++j;
}if (!j) add(n+1,i);
}tot=0;work();
for (i=1;i<=n;++i) printf("%d
",siz[i]-1);
}
View Code
题目大意：给定n个城市排成一排，只能从1～n的方向走，定义两个城市的距离是高度差。两个人开一辆车去旅行，A先开选次近的点，B选最近的点，两人交替开车，这里距离的定义是：如果距离相等，选高度小的更近。求：1）从任意城市出发，给定x（走的最远的距离），A开的路程/B开的路程最小是多少，B的路程为0是认为是无穷大，且无穷大认为相等，如果有多个城市满足条件，输出海拔最高的；2）m组询问，每次询问给定s（起点）和x（走的最远的距离），尽量远走求A和B走的距离分别是多少。
思路：如果把A和B各开一次看作一次操作的话，可以预处理出从每个节点做一次操作的距离（A走多少、B走多少），然后倍增一下。然后我们在处理的时候就可以在倍增的数组上走了，最后判断一下A能不能再走一次就可以了。
![]()
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxm 100005
#define up 20
#define LL long long
#define inf 2100000000
#define linf 0x7fffffffffffffffLL
#define eps 1e-9
using namespace std;
struct use{
int ll,rr;
}tree[maxm*4]={0};
struct uu{LL da,db;};
int fa[maxm][up+1]={0},est[maxm]={0},er[maxm]={0},n,siz;
LL fi[maxm][up+1]={0},gi[maxm][up+1]={0},ai[maxm]={0},bi[maxm]={0},xi;
use updata(use x,use y){
use c;
c.ll=(x.ll ? x.ll : y.ll);
c.rr=(y.rr ? y.rr : x.rr);
return c;
}
LL ab(LL x){return x<0 ? -x : x;}
int cmp(double x,double y){
if (x-y>eps) return 1;
if (y-x>eps) return -1;
return 0;
}
void ins(int i,int l,int r,int x,int y){
if (l==r){tree[i].ll=tree[i].rr=y;return;}
int mid=(l+r)>>1;
if (x<=mid) ins(i<<1,l,mid,x,y);
else ins(i<<1|1,mid+1,r,x,y);
tree[i]=updata(tree[i<<1],tree[i<<1|1]);
}
int pree(int i,int l,int r,int ll,int rr){
if (ll<=l&&r<=rr) return tree[i].rr;
int mid=(l+r)>>1;int ans1=0,ans2=0;
if (ll<=mid) ans1=pree(i<<1,l,mid,ll,rr);
if (rr>mid) ans2=pree(i<<1|1,mid+1,r,ll,rr);
return (ans2 ? ans2 : ans1);
}
int succ(int i,int l,int r,int ll,int rr){
if (ll<=l&&r<=rr) return tree[i].ll;
int mid=(l+r)>>1;int ans1=0,ans2=0;
if (ll<=mid) ans1=succ(i<<1,l,mid,ll,rr);
if (rr>mid) ans2=succ(i<<1|1,mid+1,r,ll,rr);
return (ans1 ? ans1 : ans2);
}
void pre(){
int i,j,nest,ner,pnest,pner;LL c1,c2;
for (i=n;i;--i){
nest=pnest=ner=pner=0;c1=c2=linf;
if (ai[i]>1){
nest=pree(1,1,siz,1,ai[i]-1);
if (ai[nest]>1) pnest=pree(1,1,siz,1,ai[nest]-1);
}if (ai[i]<siz){
ner=succ(1,1,siz,ai[i]+1,siz);
if (ai[ner]<siz&&ner) pner=succ(1,1,siz,ai[ner]+1,siz);
}if (nest&&bi[ai[i]]-bi[ai[nest]]<c1){
c1=bi[ai[i]]-bi[ai[nest]];est[i]=nest;
}if (ner&&bi[ai[ner]]-bi[ai[i]]<c1) est[i]=ner;
if (nest&&est[i]!=nest&&bi[ai[i]]-bi[ai[nest]]<c2){
c2=bi[ai[i]]-bi[ai[nest]];er[i]=nest;
}if (pnest&&bi[ai[i]]-bi[ai[pnest]]<c2){
c2=bi[ai[i]]-bi[ai[pnest]];er[i]=pnest;
}if (ner&&est[i]!=ner&&bi[ai[ner]]-bi[ai[i]]<c2){
c2=bi[ai[ner]]-bi[ai[i]];er[i]=ner;
}if (pner&&bi[ai[pner]]-bi[ai[i]]<c2){
c2=bi[ai[pner]]-bi[ai[i]];er[i]=pner;
}ins(1,1,siz,ai[i],i);fa[i][0]=est[er[i]];
if (er[i]) fi[i][0]=ab(bi[ai[er[i]]]-bi[ai[i]]);
else fi[i][0]=inf;
if (est[er[i]]) gi[i][0]=ab(bi[ai[est[er[i]]]]-bi[ai[er[i]]]);
else gi[i][0]=inf;
for (j=1;j<=up;++j){
fa[i][j]=fa[fa[i][j-1]][j-1];
fi[i][j]=fi[fa[i][j-1]][j-1]+fi[i][j-1];
gi[i][j]=gi[fa[i][j-1]][j-1]+gi[i][j-1];
}
}
}
uu get(int x){
int i,j;LL ans=0;uu ci;ci.da=ci.db=0LL;
for (i=up;i>=0;--i)
if (ans+fi[x][i]+gi[x][i]<=xi){
ans+=fi[x][i]+gi[x][i];
ci.da+=fi[x][i];ci.db+=gi[x][i];
x=fa[x][i];
}
if (ans+fi[x][0]<=xi){
ans+=fi[x][0];ci.da+=fi[x][0];
}return ci;
}
int main(){
int m,i,j,si;uu ci;
double ans=inf*1.0,cc;scanf("%d",&n);
for (i=1;i<=n;++i){scanf("%I64d",&ai[i]);bi[i]=ai[i];}
sort(bi+1,bi+n+1);siz=unique(bi+1,bi+n+1)-bi-1;
for (i=1;i<=n;++i) ai[i]=upper_bound(bi+1,bi+n+1,ai[i])-bi-1;
pre();scanf("%I64d%d",&xi,&m);
for (si=0,i=1;i<=n;++i){
ci=get(i);
if (ci.db==0) cc=inf*1.0;
else cc=(double)ci.da*1.0/(double)ci.db;
if (cmp(cc,ans)==0&&ai[i]>ai[si]) si=i;
if (cmp(cc,ans)<0){ans=cc;si=i;}
}printf("%d
",si);
for (i=1;i<=m;++i){
scanf("%d%I64d",&si,&xi);
ci=get(si);printf("%I64d %I64d
",ci.da,ci.db);
}
}
