abcttt
abcttt
全部文章
分类
dp(4)
二分(1)
博弈(3)
图论(1)
字符串(3)
数据结构(1)
数论(2)
未归档(14)
板子(17)
树上倍增(1)
树上差分(1)
树状数组(2)
线段树(2)
面试(1)
题解(11)
归档
标签
去牛客网
登录
/
注册
abcttt的博客
TA的专栏
2篇文章
0人订阅
Java模板系列
2篇文章
310人学习
全部文章
(共64篇)
树上倍增板子
树上倍增比起树链剖分代码短,容易查错,时空优,但是广度不如树链剖分. 具体实现 首先开一个n×logn的数组,比如fa[n][logn],其中fa[i][j]表示i节点的第2^j个父亲是谁。 那么就有: fa[i][j]=fa[fa[i][j-1]][j-1] 用文字叙述为:i的第2^j 个父亲 是...
2021-06-26
0
354
树链剖分板子
对点权 例题: 题意描述:给定一棵树和节点上的值,然后执行下面操作: I u,v,value:把u和v路径上的节点的值都加上value; D u,v,value:把u和v路径上的节点的值都减去value; Q u:询问节点u上的值。 #include<cstdio> #include&...
2021-06-26
0
264
CodeForces - 208E Blood Cousins(树上倍增+二分)
题意:好几棵树,询问祖先为点i往上的第k个,且深度与点i相同点有多少个 解法:找点i的祖先很好找,如果这时我们搜索暴力,肯定会超时,所以就想到了二分优化,先预处理dfs序,得出新的编号,并开一个vector分别按深度记录下来,然后在查询祖先为t深度为h的点的个数时,只需要在vector第h层里二分,...
2021-06-26
0
460
马拉车
主要用来求字符串的回文子串 时间复杂度是o(n) 思路是求以i为对称点,最长的回文子串,一开始先在字符串每个字符中间加个字符,使所有回文串成为奇回文串,然后不断推进的结果即可 例题为洛谷模板题,求最长回文子串的长度. #include<cstdio> #include<algor...
2021-06-26
0
425
AC自动机
AC自动机能解决单个母串,多个子串的问题,例如某一个子串出现了多少次,一共出现了几个子串等等. 网上常常说AC自动机是Kmp+字典树 简单来说为三步 1.建立子串的字典树 2建立fail指针,从而添加失败路径 3.跑母串 看一下例题 洛谷AC自动机加强版 题目描述 有N个由小写字母组成的模式串以及...
2021-06-26
0
321
RMQ区间最值问题
因为之前学过树上倍增,还是挺好理解的,不能处理动态的 #include<cstdio> #include<cstring> #include<algorithm> #define M 25 #define N 100005 using namespace std...
2021-06-26
0
240
莫队
先说分块 牛 分块就是将一个序列,分成若干个区间(一般一个区间取sqrt(n)) 于是在进行选择分块策略时,主要解决以下几个问题: 1.针对不完整块如何进行处理? 2.完整的块如何进行处理? 3.需要对每个块维护哪些信息?如何进行预处理? 4.如何合并答案? 例子:给出一个长为 n的数列,以及n ...
2021-06-26
0
339
染色图(数论分块)
题目: 定义一张无向图 G=⟨V,E⟩ 是 k 可染色的当且仅当存在函数 f:V↦{1,2,⋯,k} 满足对于 G 中的任何一条边 (u,v),都有 f(u)≠f(v)。 定义函数 g(n,k) 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说,g(3,1)=0...
2021-06-26
0
337
乘法(二分套二分)
题意:一个长度为n的数列,和一个长度为m的数列,每项相乘的出来的所有结果中第k大的值,其中数列长度为1e5,整数大小1e6 思路:先二分要求的值,再定住每一个矩阵n,去二分另一个矩阵m,得出大于等于这个值的个数,直到找到这个k即可。 时间复杂度(O(nlogn^2)) #include<io...
2021-06-26
0
331
7-5 1E. 树与路径(巧妙的树上差分)
在一棵有根树 T 上,任何两点间的最短路径都能够分为两个阶段: 从起点出发,沿着向根的方向走若干条边。 向着终点,沿着离开根的方向走若干条边。 定义一条路径的权值为向上走的边数乘上向下走的边数。特殊地,当起点等于终点的时候,两阶段的边数都是 0;当起点是终点的祖先的时候,第一阶段的边数是 0;...
2021-06-26
0
391
首页
上一页
1
2
3
4
5
6
7
下一页
末页