abcttt
abcttt
全部文章
板子
dp(4)
二分(1)
博弈(3)
图论(1)
字符串(3)
数据结构(1)
数论(2)
未归档(14)
树上倍增(1)
树上差分(1)
树状数组(2)
线段树(2)
面试(1)
题解(11)
归档
标签
去牛客网
登录
/
注册
abcttt的博客
全部文章
/ 板子
(共17篇)
匈牙利板子+题
板子 计算最大匹配 遍历一个集合 时间复杂度o(nm) #include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn=100005; vector&...
2021-06-26
0
309
树上倍增板子
树上倍增比起树链剖分代码短,容易查错,时空优,但是广度不如树链剖分. 具体实现 首先开一个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
361
树链剖分板子
对点权 例题: 题意描述:给定一棵树和节点上的值,然后执行下面操作: I u,v,value:把u和v路径上的节点的值都加上value; D u,v,value:把u和v路径上的节点的值都减去value; Q u:询问节点u上的值。 #include<cstdio> #include&...
2021-06-26
0
268
马拉车
主要用来求字符串的回文子串 时间复杂度是o(n) 思路是求以i为对称点,最长的回文子串,一开始先在字符串每个字符中间加个字符,使所有回文串成为奇回文串,然后不断推进的结果即可 例题为洛谷模板题,求最长回文子串的长度. #include<cstdio> #include<algor...
2021-06-26
0
431
AC自动机
AC自动机能解决单个母串,多个子串的问题,例如某一个子串出现了多少次,一共出现了几个子串等等. 网上常常说AC自动机是Kmp+字典树 简单来说为三步 1.建立子串的字典树 2建立fail指针,从而添加失败路径 3.跑母串 看一下例题 洛谷AC自动机加强版 题目描述 有N个由小写字母组成的模式串以及...
2021-06-26
0
323
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
340
首页
上一页
1
2
下一页
末页