倍增大专题

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//考虑到让一个点走多的路程，两点走短路程
//首先对多种情况画图，可以知道树上三点两两求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级祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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：先求最小生成树。然后求两点路径的最大边权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
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给你一个 nn 个数的序列 aia_i，和 qq 次询问，每次询问一段区间 [l,r][l,r]，问至少要把这个区间分为几个子区间，才能使得每个子区间内的数的乘积等于这个子区间内所有数的 LCMLCM 。

n,ai,q≤105n,a_i,q\le 10^5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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，我们考虑利用倍增转移加速。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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;
}

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// 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;
}