搜索结果
查询Tags标签： 倍增，共有 19条记录-
NC51101 Lost Cows
题目链接 题目 题目描述 \(N (2 \leq N \leq 8,000)\) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood watering hole and drank a few too many beers before dinner. When it was time to line…
2023/5/3 18:22:02 人评论 次浏览 -
运用倍增思想实现RMQ（RMQ (Range Minimum/Maximum Query)）问题
本博客大部分是我对这位大佬的文章的个人理解：https://blog.csdn.net/weixin_45697774/article/details/105289810 《倍增》
2022/8/9 6:23:55 人评论 次浏览 -
LCA（树上倍增）
https://www.luogu.com.cn/problem/P3379链式前向星存边 fa[i][j] 代表从i结点向上找 2^i 代的父亲，（i=0代表真父亲） dfs从根结点开始fa[now][i] = fa[fa[now][i - 1]][i - 1];代表当前结点的第2^i代父节点是当前结点2^(i-1)父节点的2^(i-1)代父节点，然后再对其连接到…
2022/7/31 23:42:40 人评论 次浏览 -
LCA在线算法（树状倍增）
对于一棵树里的任意两个节点，若他们的深度相同，显然他们到最近公共祖先的距离是相同的，我 们可以利用这个性质来求最近公共祖先。对于两个深度相同的节点，若此时父亲节点是同一个点，那么最近公共祖先就是父亲节点，如果不 是的话我们就让他们向上跳到自己的父亲节点，…
2022/7/28 1:24:03 人评论 次浏览 -
论RMQ
啥是倍增思想？ 倍增，每次将范围扩大或减少一倍而达到加速的效果 举个栗子，你想要跳到15米远的地方，你怎么找到这个15这个地方，一步一步跳吗，利用倍增的话 预设一个k使2^k>15值 ，这里我们假设k=5， 2^5=32 >15 k- -; k=4; 跳过了，不跳 2^4=16 >15 k- -; k…
2022/7/16 23:46:20 人评论 次浏览 -
324 最近公共祖先 倍增算法
视频链接：// P3379 【模板】最近公共祖先（LCA） #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N=5e5+10; int n,m,s,a,b; vector<int> e[N]; int dep[N],fa[N][20];…
2022/5/29 1:22:57 人评论 次浏览 -
字符串专题-学习笔记：后缀数组
目录一些 Update1. 概述2. 子串3. sa 数组和 Rank 数组1. 定义2. 求 Rank 数组2.1 暴力2.2 倍增算法2.2.1 倍增+快排2.2.2 倍增+基排3. 代码4. height 数组1. 定义2. 求法5. 总结 一些 Update Update 2022/2/8：修正了部分语言，不影响阅读与理解。 1. 概述 后缀数组（SA）…
2022/4/7 23:23:51 人评论 次浏览 -
洛谷P7518 [省选联考 2021 A/B 卷] 宝石
P7518 [省选联考 2021 A/B 卷] 宝石 题目来源 乍一看没有任何思路，于是当年我打了一个模拟程序混了点分就跑路了……然后现在还是得看题解……还得努力啊 这里用主席树+倍增+二分，复杂度O(nlog2 (n)),理解起来较为简单，但是对我来说太难想了。 一、题目初步转化 1.其实…
2022/3/21 6:29:43 人评论 次浏览 -
浅谈倍增LCA
倍增LCALCA：已知一个树和书上两个点，求两个点的最近公共祖先。 倍增：将2的所有次幂排成一个序列，相加可以得到所有正整数，这样就可以在找最近公共祖先时不是一层一层找而是每次找2的幂次方层，大大提高算法效率。 算法思路： 1，用链式前向星存图，找到根节点并从根节…
2022/2/15 23:15:15 人评论 次浏览 -
LCA-最近公共祖先 向上标记法、倍增法、Tarjan
LCA 向上标记法 时间复杂度 O(n∗m)O(n*m)O(n∗m) 如果两个结点不相同，就将较深的结点向上移动，直到移动到相同结点，那么该结点即为公共祖先结点。 代码 //预处理每个结点的深度，以及结点的父结点的编号 void dfs(int u, int father){depth[u]=depth[father]+1;fa[u]=…
2022/2/7 23:12:51 人评论 次浏览 -
蓝桥杯 Day7 java组 倍增
倍增法和二分法是“相反”的算法。二分是每次缩小一倍，从而以 O(logn)的步骤极快地缩小定位到解；倍增是每次扩大一倍，从而以 O(2^n)的速度极快地扩展到极大的空间。所以倍增和二分的效率都很高。 二分法与倍增的应用场景 二分法是缩小区间，最后定位到一个极小的区间，…
2022/1/30 17:04:30 人评论 次浏览 -
[IOI2021]地牢游戏
地牢游戏 题解 首先，我们根据 subtask3,4subtask\,3,4subtask3,4，应该很容易想到一种倍增的做法去解决我们的问题。 对于这几个图，我们的分层是相当少的，所以我们可以将我们整个过程分成至多666个阶段，对于每个阶段单独倍增直到超越这个阶段，或者说抵达我们的终点。…
2021/11/17 23:13:58 人评论 次浏览 -
[IOI2021]地牢游戏
地牢游戏 题解 首先，我们根据 subtask3,4subtask\,3,4subtask3,4，应该很容易想到一种倍增的做法去解决我们的问题。 对于这几个图，我们的分层是相当少的，所以我们可以将我们整个过程分成至多666个阶段，对于每个阶段单独倍增直到超越这个阶段，或者说抵达我们的终点。…
2021/11/17 23:13:58 人评论 次浏览 -
noip模拟70(待补)
A. 暴雨 B. AVL 树 C. 挖掘机 想不到倍增. 已经肯定处理每一行的复杂度都是在 \(O(1)\) ~ \(O(logn)\) 的复杂度了. 也知道应该是处理每个起点之后的东西. 可偏偏不知道应该用什么算法来解决. 哪怕把倍增告诉我也不知道如何处理，太菜... 这个题把没有用的删去之后，确实就…
2021/10/7 6:40:58 人评论 次浏览 -
noip模拟70(待补)
A. 暴雨 B. AVL 树 C. 挖掘机 想不到倍增. 已经肯定处理每一行的复杂度都是在 \(O(1)\) ~ \(O(logn)\) 的复杂度了. 也知道应该是处理每个起点之后的东西. 可偏偏不知道应该用什么算法来解决. 哪怕把倍增告诉我也不知道如何处理，太菜... 这个题把没有用的删去之后，确实就…
2021/10/7 6:40:58 人评论 次浏览
