倍增练习(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;
}

原文地址：https://blog.csdn.net/sin1810335764/article/details/142370948

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！