倍增大专题

[AHOI2008] 紧急集合 / 聚会 - 洛谷

题意：给定一棵树，多次查询费马点（bushi

费马点的含义是：到三个点的距离之和最小

Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。

//考虑到让一个点走多的路程，两点走短路程
//首先对多种情况画图，可以知道树上三点两两求lca，必然至少两个相同
vector<int> e[N];
int fa[N],son[N],dep[N],siz[N];
int top[N];

void dfs1(int u,int f){ //搞fa,dep,son
  fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
  for(int v:e[u]){
    if(v==f) continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
  }
}
void dfs2(int u,int t){ //搞top
  top[u]=t;  //记录链头
  if(!son[u]) return; //无重儿子
  dfs2(son[u],t);     //搜重儿子
  for(int v:e[u]){
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v); //搜轻儿子
  }
}
int lca(int u,int v){
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);
    u=fa[top[u]];
  }
  return dep[u]<dep[v]?u:v;
}
int dis(int u,int v){
	int mid=lca(u,v);
	return dep[u]+dep[v]-2*dep[mid];
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=m;i++){
		int x,y,z;cin>>x>>y>>z;
		int c1=lca(x,y),c2=lca(x,z),c3=lca(y,z);
		int c=c1^c2^c3;
		int ans=dis(x,c)+dis(y,c)+dis(z,c);
		cout<<c<<" "<<ans<<endl;
	}
}

Codeforces Round 294 (Div. 2)E

题意：给定一棵树，多次查询。每次查询给出两点，求到两个点距离相等点的个数。

Solution：特殊情况，两个点重合，答案是n。再考虑无解情况，如果两个点的距离是奇数，则不存在这样的点，答案是0。最后考虑距离是偶数的点，不妨假设u深度大于v

  • u与v高度不同，则找到中点，找到u的k-1级祖先，也就是中点的包含u的儿子的子树，记这个中点的儿子为son，以son为根的子树包含u。答案是sz[mid]-sz[u】
  • u与v高度相等则两者lca上面的点可以对答案做贡献，考虑求出lca，求出son1,son表示lca的亲子节点，以son1为根的子树包含u，以son2为根的子树包含v。考虑答案是sz[lca]-sz[son1]-sz[son2] + n-sz[lca];

本题用倍增比较合适，可以对距离倍增快速利用get函数找到我们的k级祖先

struct edge{
    int v,w;
};
//思考：要想知道一个数有几个二级制位，直接n=__lg(x)
//我们可以知道<n最近的2的次幂，9最大的是8，8虽然是2的3次方，但要遍历它的每一位
//需要3到0开始，也就是考虑到0的影响，我们可以正好满足偏移。
//2的3次方有四位，也就是__lg(x)就是我们需要的最高位，从它开始往低遍历
vector<edge>e[N];
const int len=__lg(N);
int dep[N];
int d[N];
int f[N][len+2];
 
int sz[N];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;sz[u]=1;
    for(int i=1;i<=len;i++)f[u][i]=f[f[u][i-1]][i-1];
    //预处理倍增数组
 
    for(auto [v,w]:e[u]){
        if(v==fa)continue;
        d[v]=d[u]+w;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int get(int x,int k) {//k级祖先
    for(int i=len;i>=0;i--) if((k >> i) & 1) x = f[x][i];
    return x;
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=len;i>=0;i--){
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
    }
    //跳到相同深度
 
    if(x==y)return y;
    //提提前判本身就是祖先关系
 
//cerr<<x<<" "<<y<<endl;
    for(int i=len;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];y=f[y][i];
        }
       // cerr<<i<<" "<<x<<" "<<y<<endl;
    }
    //cerr<<x<<" "<<y<<endl;
    //倍增一起向上跳，直到父亲就是答案
    return f[x][0];
}
int dis(int u,int v){
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
 
//lca的子树和去掉两个分支，本题需要求未知点祖先，无法使用树链跑分
void solve(){
	cin>>n;//cin>>m;
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		e[u].push_back({v,1});
		e[v].push_back({u,1});
		
	}
	dfs(1,0);
	//for(int i=1;i<=n;i++)cerr<<sz[i]<<" ";
	//cerr<<endl;
	cin>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;int mid=lca(u,v);
	//	cerr<<mid<<endl;
		if(dep[u]<dep[v])swap(u,v);
		int ans=0;
		if(u==v)ans=n;
	else {
		int dist=dis(u,v);
		if(dist%2)ans=0;
		else {
			if(dep[u]==dep[v]){
				int k=dep[u]-dep[mid]-1;
				int s1=get(u,k),s2=get(v,k);
				ans=n-sz[s1]-sz[s2];
			}
			else {
				int k=dist/2-1;
				int s1=get(u,k);int s2=get(u,k+1);
				ans=sz[s2]-sz[s1];
				
			}
		}
	}
	cout<<ans<<endl;
  }
}

Minimum spanning tree for each edge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Cut - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目详情 - 负环 - BZOJ by HydroOJ

校赛亚轴（板子复习

http://oj.daimayuan.top/problem/805最小瓶颈生成树

注意倍增到最后两边都还要再挑一条边

题目：给定一张 n 个点 m 条边的无向图，每条边有一个权值，定义瓶颈路权值为某一条从点 i 到 j 的路径上的最大权值，有 q个询问，每次询问给出两个点 (s,t)，求从 s 到 t 的最小瓶颈路权值

Sol：先求最小生成树。然后求两点路径的最大边权值

int a[N];
struct edge{
    int v;
    int w;
};
vector<edge>e[N];

const int len=__lg(N);
int dep[N];
//int d[N];
int f[N][len+2];//数组多开
int ans[N][len+2];

struct edges{
  int u,v,w;
  bool operator<(const edges &t)const
  {return w < t.w;}   
}ff[M];//结构体存边
struct DSU {
  vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
void add(int u,int v,int w){
	e[u].push_back({v,w});
}
int cnt=0,tmp=0;
bool kruskal(){//返回的是原图的连通性，最小生成树的答案并没有返回，注意自己处理。
  sort(ff+1,ff+m+1);
 DSU dsu(n+1);
 int cnt=0;
  for(int i=1; i<=m; i++){
     int x=(ff[i].u);
     int y=(ff[i].v);
    if(!dsu.same(x,y))
   {
      dsu.merge(x,y);
    add(ff[i].u,ff[i].v,ff[i].w);
     add(ff[i].v,ff[i].u,ff[i].w);
      tmp+=ff[i].w;
      cnt++;
    }
  } 
  return cnt==n-1;
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=len;i++){
    f[u][i]=f[f[u][i-1]][i-1];
    ans[u][i]=max(ans[u][i-1],ans[f[u][i-1]][i-1]);
    //预处理倍增数组
}
    for(auto [v,w]:e[u]){//加边权后增加参数w
        if(v==fa)continue;
       // d[v]=d[u]+w;
       ans[v][0]=w;
        dfs(v,u);
        //sz[u]+=sz[v];
    }
}
int lca(int x,int y){
	int res=0;
	
    if(dep[x]<dep[y])swap(x,y);
    // cerr<<x<<" "<<y<<endl;
  //   bug(res);
    for(int i=len;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]){res=max(res,ans[x][i]);x=f[x][i];}
    }
    //跳到相同深度
//cerr<<x<<endl;
    if(x==y)return res;
    //提提前判本身就是祖先关系


    for(int i=len;i>=0;i--){
        if(f[x][i]!=f[y][i]){
        	 res=max(res,ans[x][i]);
            res=max(res,ans[y][i]);
            x=f[x][i];y=f[y][i];
           
        }
    }
   
    //倍增一起向上跳，直到父亲就是答案
    res=max(res,ans[y][0]);
    return max(res,ans[x][0]);
}

void solve(){
     cin>>n>>m;
     for(int i=1;i<=m;i++){
     	int u,v,w;cin>>u>>v>>w;
     	ff[i]={u,v,w};
     }
     kruskal();
    // cerr<<tmp<<endl;
     dfs(1,0);
    // bug(ans[1][0]);
   // bug(ans[2][0]);
   int q;cin>>q;
     for(int i=1;i<=q;i++){
     	int u,v;cin>>u>>v;
     	cout<<lca(u,v)<<endl;
     }
}

https://www.luogu.com.cn/problem/CF1516D给你一个 $n$ 个数的序列 $a_i$，和 $q$ 次询问，每次询问一段区间 $[l,r]$，问至少要把这个区间分为几个子区间，才能使得每个子区间内的数的乘积等于这个子区间内所有数的 $LCM$ 。

$n,a_i,q\le 10^5$

Sol:先考虑固定L的情况，下一个端点在哪，由于lcm随集合大小单调性和质因数的限制我们可以得到。但最坏我们可能每次只能一步一步跳，所以我们倍增跳，在不超过的边界的情况下跳，最后再跳一步。

int a[N];
int f[N][21];
int v[N];
vector<int>c[N];
bool st[N];
void init(int mm){
	
	   for(int i=2;i<=mm;i++){
	   
	        if(st[i])continue;
	      //  bug(i);
	        c[i].push_back(i);
	        for(int j=i+i;j<=mm;j+=i){
	        	st[j]=true;
	        	c[j].push_back(i);
	        }
	   }
}
void solve(){
	int q;
     cin>>n>>q;
     for(int i=1;i<=n;i++)cin>>a[i];
     f[n+1][0]=n+1;
     memset(v,0x3f,sizeof v);
     for(int i=n;i>=1;i--){
     	 f[i][0]=f[i+1][0];
     	 for(auto j:c[a[i]]){
     	 	f[i][0]=min(f[i][0],v[j]);
     	 	v[j]=i;
     	 }
     }
     for(int i=1;i<=20;i++){
     	for(int j=1;j<=n;j++){
     		if(f[j][i-1]<=n)f[j][i]=f[f[j][i-1]][i-1];
     		else f[j][i]=n+1;
     	}
     }
     while(q--){
     	int l,r;cin>>l>>r;
     	int ans=0;
     	for(int i=20;i>=0;i--){
     		if(f[l][i]<=r){
     			ans+=(1<<i);
     			l=f[l][i];
     		}
     	}
     	ans++;
     	cout<<ans<<endl;
     }
}

对于边带权的有向图 𝐺=(𝑉,𝐸)，请找出一个点数最小的环，使得环上的边权和为负数。保证图中不包含重边和自环。

Sol：不能直接dp，我们考虑利用倍增转移加速。

int n, m;
int f[9][301][301],v[301][301],g[301][301];
//f[k][i][j]:从i到j恰好走k步的边权和最小值
void solve(){
     cin>>n>>m;
     memset(f,0x3f,sizeof f);
     for(int i=1;i<=n;i++)f[0][i][i]=0;
     for(int i=1;i<=m;i++){
     	int x,y,z;cin>>x>>y>>z;
     	f[0][x][y]=z;
     }
     for(int i=1;i<=8;i++){
     	for(int x=1;x<=n;x++){
     		for(int y=1;y<=n;y++){
     			for(int z=1;z<=n;z++){
     				if(f[i-1][x][z]<inf&&f[i-1][z][y]<inf){
     					f[i][x][y]=min(f[i][x][y],f[i-1][x][z]+f[i-1][z][y]);
     				}
     			}
     		}
     	}
     }
     int ans=0;
     memset(v,0x3f,sizeof v);
     for(int i=1;i<=n;i++)v[i][i]=0;
     for(int i=8;i>=0;i--){
     	memset(g,0x3f ,sizeof g);
     	for(int x=1;x<=n;x++){
     		for(int y=1;y<=n;y++){
     			for(int z=1;z<=n;z++){
     				if(v[x][z]<inf&&f[i][z][y]<inf){
     					g[x][y]=min(g[x][y],v[x][z]+f[i][z][y]);
     				}
     			}
     		}
     	}
     
     bool ok=true;
     for(int j=1;j<=n&&ok;j++){
     	if(g[j][j]<0)ok=false;
     }
     if(ok){
     	ans+=(1<<i);
     	memcpy(v,g,sizeof g);
     }
     }
     ans++;
     if(ans>n)cout<<0<<endl;
     else cout<<ans<<endl;
}

题意：给定一张由 $T$ 条边构成的无向图，点的编号为 $1 \sim 1000$ 之间的整数。 求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边（可以重复经过）的最短路。

一道不错广义矩阵乘法的矩阵快速幂

debug：1.起点终点也要换成映射后的值 2。注意边的信息输入顺序，不是所有题都默认

// Problem: 牛站
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/347/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 2e2 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int g[N][N];
int res[N][N];
//对floyd新的认识：一条边一条边考虑，且会连续更新，这对边数没有限制
map<int,int>mp;
int k,s,e;
//注意到：需要走1e6条边，但只有100条边，1000点，这时候往往和数学有关
//最后只有200个点用到，所以为了降低常数，我们选择离散化，并且题目本身
//给出的数据就是随机落在1-1000
//将 temp 数组声明为 static 的意义在于使得 temp 变量在函数调用结束后
//仍然保留其数值，
//而不会被销毁。
void mul(int c[][N],int a[][N],int b[][N]){
	static int tmp[N][N];
	memset(tmp,0x3f ,sizeof tmp);
	 for (int k = 1; k <= n; k ++ )//注意枚举顺序
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                tmp[i][j] = min(tmp[i][j], a[i][k] + b[k][j]);
	memcpy(c, tmp, sizeof tmp);
}
//每做一次，表示res经过a条边，g经过2^k条边，那么得到的res就是经过a+2^k条的
//边的距离
void qmt(){
	memset(res,0x3f ,sizeof res);
	for(int i=1;i<=n;i++)res[i][i]=0;
	//res初始化，o条边的时候，到达自己位0，无法到达别人，记为正无穷
	while(k){
		if(k&1)mul(res,res,g);
		mul(g,g,g);
		k>>=1;
	}
}
void solve(){
	cin>>k>>m>>s>>e;
	memset(g,0x3f ,sizeof res);
	if(!mp.count(s))mp[s]=++n;
	if(!mp.count(e))mp[e]=++n;
	s=mp[s];
	e=mp[e];
	for(int i=1;i<=m;i++){
		int u,v,w;
		//注意信息顺序
		cin>>w>>u>>v;
	//	cerr<<u<<" "<<v<<" "<<w<<endl;
		if(!mp.count(u))mp[u]=++n;
		if(!mp.count(v))mp[v]=++n;
		u=mp[u];v=mp[v];
		//cerr<<u<<" "<<v<<" "<<w<<endl;
		g[u][v]=g[v][u]=min(g[u][v],w);
	}
	qmt();
	cout<<res[s][e]<<endl;
	
}
int main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}