倍增练习(1)

A - ST 表 && RMQ 问题

 

题目思路:st表的板子题用于静态区间求最值,通过倍增的思想,先通过预处理将各个区间的最大值通过转移式求出f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);然后再进行重叠查询查询,k = log2(r - l + 1);,max(f[l][k], f[r - (1 << k) + 1][k]).

实现代码:

#include<bits/stdc++.h>
using namespace std;
#define N 2000005
typedef long long ll;
ll n, m, t, a, b, c, k, d, r, l;
ll f[N][32], dp[N];
ll ans, maxx, minn = 1e9;
inline int read()
{int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }return x * f;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) f[i][0] = read();for (int j = 1; j <= 20; j++) {for (int i = 1; i + (l << j) - 1 <= n; i++) {f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}for (int i = 1; i <= m; i++) {l = read(), r = read();k = log2(r - l + 1);cout << max(f[l][k], f[r - (1 << k) + 1][k]) << '\n';}return 0;
}

P3379 【模板】最近公共祖先（LCA）

 

题目思路:dep[u]存u点的深度,f[u][i]存从u点向上提哦啊2^i层的祖先节点,首先通过dfs进行倍增递推打表,从小到大枚举,然后跑一边lca进行二进制拆分,从大到小枚举.用快读读取,卡时间

代码实现:

#include<bits/stdc++.h>
using namespace std;
#define N 2000005
typedef long long ll;
ll n, m, t, a, b, c, k, d, r, l;
ll f[N][30], dep[N];
ll ans, maxx, minn = 1e9;
vector<ll>v[N];
inline int read()
{int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }return x * f;
}
void dfs(ll u, ll father) {dep[u] = dep[father] + 1;f[u][0] = father;for (int i = 1; i <= 20; i++) {f[u][i] = f[f[u][i - 1]][i - 1];}for (ll v : v[u]) {if (v != father)dfs(v, u);}
}ll lca(ll u, ll v) {if (dep[u] < dep[v]) swap(u, v);for (int i = 20; i >= 0; i--)if (dep[f[u][i]] >= dep[v])u = f[u][i];if (u == v) return v;for (int i = 20; i >= 0; i--) {if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];}return f[u][0];
}
int main()
{cin >> n >> m >> t;for (int i = 1; i <= n-1; i++) {a = read(), b = read();v[a].push_back(b), v[b].push_back(a);}dfs(t, 0);for (int i = 1; i <= m; i++) {a = read(), b = read();cout << lca(a,b) << '\n';}return 0;
}