首页 > 其他分享 >倍增 && LCA 杂题

倍增 && LCA 杂题

时间：2024-10-12 17:14:37浏览次数：7  
标签：int rint 染色 && LCA vala valb 杂题 id

倍增 && LCA 杂题

倍增

之前没研究过，甚至基础原理搞得都不太懂，只知道背个 ST 表和 LCA 的板子，补题补 2022 CSP 发现 T4 根本学不懂，本来打算不学了，结果 NOIP 2018 还考过类似的。所以补一下这个坑。

倍增，字面意思就是成倍增长，这是指我们在进行递推时如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求。那么我们可以通过成倍增长的方式只递推状态空间中在二的整数次幂位置上的值作为代表。当需要其他位置上的值的时候，通过任意整数可以表示成若干个二的次幂项的和这一性质。使用之前求出代表值拼成所需的值，使用算法的要求是：问题的状态空间关于二的次幂具有可划分性。

大致设计过程，可以令一个 \(p\) 表示倍增的下标，从 \(1\) 开始，每次 \(p *= 2\)，也可以表示倍增的次幂，每次 \(p++\)，这个看习惯就好。\(lazy\) 动态维护需要的变量，可以类比线段树懒标记。还有一种更为常用的，就是 \(f[i][j]\) 表示起点为 \(i\)，经历 \(2^j\) 的操作类后的代表值。

P10455 Genius Acm

首先考虑一个贪心的过程，对于一个集合 \(S\)，要想校验值最大，其实就是取出最大的 \(M\) 个数和最小的 \(M\) 个数，这样 \(2M\) 个数构成的校验值就是最大的。于是从头开始分段，每段的长度要尽量长。

很显然可以二分答案，这个比较好想。但是每次二分复杂度是 \(O(n)\) 的，最坏情况可以被卡到 \(O(n ^ 2 \log n)\)。

考虑倍增，从头开始分段，这个问题的状态空间可划分。

那么问题就变成了每次给定一个左端点 \(L\)，在满足 \(a[L]\)~\(a[R]\) 的校验值不超过 \(T\) 的前提下，求 \(R\) 最大能取到的位置

这里可以用一个倍增的思想来寻找右端点：

  • 初始化 \(p = 1, R = L\)
  • 求出 [L, R + p * 2] 这一段区间的校验值，若校验值 <= T，则 R += p * 2, p *= 2，否则 p /= 2
  • 重复直到 \(p\) 的值变为 \(0\)，\(R\) 即为所求

正常时限这个算法的复杂度是 \(O(n \log ^ 2n)\)，按理来说是够了，但是数据被加强了，无论在 acwing 还是洛谷都会被卡一个点。

对于特殊数据特殊处理显然可以通过此题，但是考虑继续优化我们的原算法。每次求校验值都需要进行排序，但是每次除了新增的一段，前面的几段都是排过序的，因此可以进一步优化，每次只排序新增的一段，然后通过归并排序的合并来将前几段和新增的一段进行排序，会省去很多无用的排序。归并排序库里有 merge ，直接调就可以。复杂度 \(O(n \log n)\)
。足以通过。

int n, m, t;
int a[N], b[N], c[N];
//a[] 表示原数组
//b[] 表示排序后的数组
//c[] 表示合并后的数组

bool check(int l, int r, int mid) 
{
	if (r > n) return 0;
	for (rint i = mid; i <= r; i++) b[i] = a[i];
	
	sort(b + mid, b + r + 1);
	merge(b + l, b + mid, b + mid, b + r + 1, c + l);
	
	int sum = 0, cnt = 0;
	for (rint i = l, j = r; i < j && ++cnt <= m; i++, j--)
		sum += (c[i] - c[j]) * (c[i] - c[j]);
	if (sum > t) return 0;
	for (rint i = l; i <= r; i++) b[i] = c[i];
	return 1;
}

signed main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) 
	{
		cin >> n >> m >> t;
		for (rint i = 1; i <= n; i++) cin >> a[i];
		int l = 1, r = 1;
		int cnt = 0, p = 1;
		b[1] = a[1];
		while (r <= n) 
		{
			if (!p) 
			{
				cnt++;
				l = r + 1;
				r = l;
				p = 1;
			}
			if (check(l, r + p * 2 - 1, r + 1))
			{
				r = r + p * 2 - 1;
				p *= 2;				
			}
			else p /= 2;
		}
		cout << cnt << endl;
	}
	return 0;
}

P6902 [ICPC2014 WF] Surveillance

题目大概的意思是给定一个长度为 \(n\) 的环，有 \(k\) 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。

按照第一种写法以 \(p\) 为起点的话，发现并不好维护。所以采用 \(f[i][j]\) 的定义，定义同开头。显然要破环为链然后预处理出每一个点会跳到哪个位置。接着往后跳这个用倍增求即可。然后直接计算答案就可以了。

record

LCA 杂题

P4281 [AHOI2008] 紧急集合

奖励自己一个板子题放松一下

LCA 板子题，直接敲板子，然后找一个节点 \(u\)，使得给定三个点 \(A, B, C\) 到 \(u\) 的距离和最小。

可以发现节点 \(u\) 的最优情况只会在 \(A, B, C\) 中任意两点的最近公共祖先里选择。

因此可以求一遍 \(A, B, C\) 中任意两点的最近公共祖先 \(p_1, p_2, p_3\)，对这三个点求一边距离和，取最小值即可。

record

while (m--) 
{
	int a, b, c;
	cin >> a >> b >> c;

	int p1 = lca(a, b); //a 和 b 的最近公共祖先
	int d1 = get_dist(p1, c) + get_dist(a, b); //a, b, c 到 p1 的距离和

	int p2 = lca(a, c); //a 和 c 的最近公共祖先
	int d2 = get_dist(p2, b) + get_dist(a, c); //a, b, c 到 p2 的距离和

	int p3 = lca(b, c); //b 和 c 的最近公共祖先
	int d3 = get_dist(p3, a) + get_dist(b, c); //a, b, c 到 p3 的距离和

	//取最小值
	if (d1 > d2) d1 = d2, p1 = p2;
	if (d1 > d3) d1 = d3, p1 = p3;

	cout << p1 << " " << d1 << endl;
}

P3533 [POI2012] RAN

乍一看，是不是有点唬人？

只看第一个限制貌似不是很难，但是后边连跟三个限制就感觉有点离谱了。处理方法也很简单，用 pair<int, int> 来存，再写个选择答案的函数就可以了。

pii cmp(pii a, pii b) 
{
	if (max(a.x, a.y) < max(b.x, b.y)) return a;
	if (max(a.x, a.y) > max(b.x, b.y)) return b;
	if (min(a.x, a.y) < min(b.x, b.y)) return a;
	if (min(a.x, a.y) > min(b.x, b.y)) return b;
	return a.x >= a.y ? a : b;
}

对于答案为 \(-1\) 的情况，跑拓扑排序再 BFS 一次维护一些信息这个题就做完了。

维护 pos[] ，表示 所在子树在环上的根节点；维护 id[] ，连通性，具体的，对于 \(y∈x\), id[y]=id[x]。对于不在同一棵基环树上，就是 pos[id[x]] != pos[id[y]]；在同一棵子树中，即 id[x] == id[y]。对于在同一颗基环树上且在环上不同结点的子树内这个情况最后特殊处理：

while (m--) 
{
	int x, y;
	cin >> x >> y;
	if (pos[id[x]] != pos[id[y]]) puts("-1 -1");
	else if (id[x] == id[y]) 
	{
		int p = lca(x, y);
		cout << d[x] - d[p] << " " << d[y] - d[p] << endl;
	} 
	else 
	{
		pii a, b;
		int sx = s[id[x]], sy = s[id[y]], now = len[pos[id[x]]];
		a.x = d[x] + (sy - sx + now) % now;
		a.y = d[y];
		b.x = d[x];
		b.y = d[y] + (sx - sy + now) % now;
		pii ans = cmp(a, b);
		cout << ans.x << " " << ans.y << endl;
	}
}

record

P8820 [CSP-S 2022] 数据传输

看的 donkeys 哥哥的题解，感觉是最清晰的一篇了。

类比 LCA 来维护。f[i][j] 表示从节点 \(i\) 向上跳 \(2^j\) 步。

对于一条起点 \(a\)，终点 \(b\) 的链，需要两端选择的机器到 \(a,b\) 的距离。并不好解决，但是数据范围会给我们答案，\(k\le3\)。那么思路有了，状态设计：g[i][j][a][b] 表示对于 g[i][j] 这一条链，最下面的机器距端点的距离为 \(a\)，最上面的机器距端点的距离为 \(b\) 的最小代价。
两个状态的合并，枚举合并后区间的 \(a,b\) 和一个区间的输出信号强度 \(x\)， \(\min_{x<k}\{g[a][x]+g[x][b]\}\) 就是合并后的值。

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 2e5 + 5;
const int M = 4e6 + 5;
const int inf = 1e18;

int n, q, k;
struct node 
{
	int a[4][4];
	void clear() 
	{
		memset(a, 0x3f, sizeof a);
		a[0][0] = 0;
	}
	void ext() 
	{ 
		for (rint i = 0; i < k - 1; i++)
			for (rint j = k - 1; ~j; j--)
				a[i + 1][j] = min(a[i + 1][j], a[i][j]);
		for (rint i = 0; i < k; i++)
			for (rint j = k - 1; j > 0; j--)
				a[i][j - 1] = min(a[i][j - 1], a[i][j]);
	}
    void init(int x) 
	{
		memset(a, 0x3f, sizeof a);
		a[0][k - 1] = x;
		for (rint i = 1; i < k; i++) a[i][i - 1] = 0;
	}
} g[N][20], vala, valb;
int f[N][20], d[N];
int val[N];
int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs(int x, int father) 
{
	d[x] = d[father] + 1, f[x][0] = father;
	for (rint i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		if (y == father) continue;
		dfs(y, x);
	}
}

void solve(int x) 
{
	g[x][0].init(val[x]);
	if (k == 3)
	{
		for (rint i = h[x]; i; i = ne[i])
		{
			int y = e[i];
			g[x][0].a[1][1] = min(g[x][0].a[1][1], val[y]);				
		}	
	}
	g[x][0].ext();
}

void merge(node &p, node f, node g) 
{
	for (rint a = 0; a < k; a++)
	{
		for (rint b = 0; b < k; b++) 
		{
			int x = inf;
			for (rint j = 0; j < k; j++) x = min(x, f.a[a][j] + g.a[j][b]);
			p.a[a][b] = x;
		}		
	}
}

int LCA(int x, int y) 
{
	vala.clear(), valb.clear();
	if (d[x] > d[y]) swap(x, y), swap(vala, valb);
	for (rint i = 18; i >= 0; i--)
	{
	    if (d[f[y][i]] >= d[x])
	    {
	    	merge(valb, valb, g[y][i]);
			y = f[y][i];
		}		
	}
	if (x == y) return x;
	for (rint i = 18; i >= 0; i--)
	{
		if (f[x][i] != f[y][i])
		{
			merge(vala, vala, g[x][i]); 
			merge(valb, valb, g[y][i]);
			x = f[x][i], y = f[y][i];					
		}
	}
	merge(vala, vala, g[x][0]);
	merge(valb, valb, g[y][0]);
	return f[x][0];
}

signed main() 
{
	cin >> n >> q >> k;
	for (rint i = 1; i <= n; i++) cin >> val[i];
	for (rint i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	dfs(1, 0);
	for (rint i = 1; i <= n; i++) solve(i);
	for (rint j = 1; j <= 18; j++)
	{
		for (rint i = 1; i <= n; i++) 
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
			merge(g[i][j], g[i][j - 1], g[f[i][j - 1]][j - 1]);
		}		
	}
	while (q--)
	{
		int s, t;
		cin >> s >> t;
		int lca = LCA(s, t);
		merge(vala, vala, g[lca][0]);
		int ans = inf;
		for (rint i = 0; i < k; i++)
			ans = min(ans, vala.a[0][i] + valb.a[0][k - i - 1]);
		cout << ans << endl;
	}
	return 0;
}

P5024 [NOIP2018 提高组] 保卫王国

给一棵树染色，每个节点染色需要一定的花费，要求相邻两个节点至少要有一个被染色，给出一些限制条件，求满足每个限制条件的最小花费为多少。

\(f1[i][1/0]\) 表示以 \(i\) 为根的子树当 \(i\) 染色/不染色时的最小花费

\(f2[i][1/0]\) 表示整棵树减去以 \(i\) 为根的子树当 \(i\) 染色/不染色时的最小花费

\(dp[i][1/0][1/0]\) 表示以 \(lca(a,b)\) 为根的子树减去以 \(i\) 为根的子树当 \(i\) 染色/不染色及 \(i\) 的父节点染色/不染色时的最小花费。

从 \(a,b\) 一直 dp 到 \(lca(a,b)\) 计算答案。特别地，当前状态无解，值设定为 inf。

树上倍增优化 \(dp\)数组，\(dp[i][j][0/1][0/1]\) 表示以 \(i\) 的 \(2^j\) 辈祖先为根的子树减去以 \(i\) 为根的子树当 \(i\) 染色/不染色及 \(i\) 的 \(2^j\) 辈祖先染色/不染色时的最小花费。

record

标签：int,rint,染色,&&,LCA,vala,valb,杂题,id
From： https://www.cnblogs.com/spaceswalker/p/18460917

相关文章

  • 线段树分治略解&杂题解析
    可能做到好题之后会再更新吧。总叙线段树与离线询问结合技巧又被称为线段树分治。使用线段树分治维护的信息通常会在某一个时间段内出现，要求在离线的前提下回答某一个时刻的信息并，则可以考虑使用线段树分治的技巧。以下是线段树分治的基本模板：change将信息按时间段覆盖在线......
  • pakencamp 杂题选刷
    2023Day1GMST(Easy)\(\color{green}\checkmark\)给定序列\(a(|a_i|\le10^6)\)，构造\(n(n\le2\cdot10^5)\)个点的无向图，点\(i,j\)的边权是\(a_ia_j\)，求图的最小生成树。唐氏。首先给\(a\)排序，显然没有影响。考察\(a_i\ge0\)怎么做：显然答案就是\(a_1\c......
  • 求 LCA 方法总结
    求LCA方法总结前言求LCA是十分基础的东西，但是方法众多。此篇介绍OI中常用的求法。倍增求LCA蒟蒻最先学的求LCA方法就是倍增求LCA。预处理和查询时间复杂度均为单\(\log\)。优点为好理解，比较简单，且便于处理路径数据。树剖LCA重链剖分。优点是预处理是线性复杂度，......
  • LCA
    \(\color{purple}{1.暴力}\)#include<iostream>#include<bits/stdc++.h>usingnamespacestd;constintmaxn=5e5+10;vector<int>vec[maxn];intf[maxn];intdep[maxn];voiddfs(intnow,intfa);intgt(inta,intb);intmain()......
  • 【笔记】杂题选讲 2024.10.5（DNF）
    十一杂题选讲-VirtualJudge(vjudge.net)/mnt/e/codes/contests/20241008/sol.md目录[AGC004F]Namori[1406E]DeletingNumbers[1081G]MergesortStrikesBack[1033E]HiddenBipartiteGraph[1254E]SendTreetoCharlie[1012E]Cyclesort[1284F]NewYearandSocialN......
  • 「杂题乱刷2」CF1372D
    题目链接CF1372DOmkarandCircle(*2100)解题思路发现问题等价于在环上砍一刀形成一个序列然后取其中不相邻的数字使得和最大。如果这是一个序列，我们只需要取奇数位上的数字和和偶数位上的数字和的最大值即可。我们发现你砍掉一刀等价于把后缀拿到最前面来。于是我们可以直......
  • 杂题选练
    一些杂题但可以记录下的。IP5300[GXOI/GZOI2019]与或和首先我们拆位，然后枚举每一个点\((i,j)\)，考虑将该点作为矩阵的右下角的贡献，先考虑\(AND\)，只有矩阵中的值都为\(1\)时才造成贡献，所以我们考虑记录\((i,j)\)左上方最大全为\(1\)的从左到右单调非严格递减的图形......
  • Codeforces 杂题
    CF1994E\(*2000,\texttt{Tag:}\)贪心，位运算题意：给出一片森林，每次你可以选择一个点删去它的子树，求所有删去的子树大小的按位或结果的最大值。Solution按位或可以看做在二进制下的不进位加法，因此，若一棵树不管怎么拆分，它拆分出来的子树大小或的结果不会大于它本身。若一棵树......
  • 「杂题乱刷2」CF1227D2
    题目链接CF1227D1OptimalSubsequences(HardVersion)*1600CF1227D2OptimalSubsequences(HardVersion)*1800解题思路本篇题解分D1，D2两个部分来写。D1sol：我们容易发现有以下两点性质：要想子序列和最大，必须选择前\(k\)大的数字。比第\(k\)大的数字还要大......
  • 「杂题乱刷2」CF1433F
    题目链接CF1433FZeroRemainderSum(*2100)解题思路简单dp，只是状态有点多。首先我们根据题目里的定义，可以构造\(dp1_{i,j,a,b}\)表示考虑到第\(i\)行前\(j\)列当前所选数之和模\(k\)为\(a\)且此时选了\(l\)个数的最大选取数字之和。那么这样，我们就可以求出每......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99