字符串哈希
核心思想 将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果 模板 typedef unsigned long long ULL;…
Category: ACM笔记
线段树
概念 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在O(log N)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 操作 定义树 pushdown pushup build modify …
高精度除法
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> div(vector<…
高精度减法
#include <iostream> #include <vector> using namespace std; bool cmp(vector<int> &A, vector<int> &B…
Trie树
int son[N][26], cnt[N], idx; // 0号点既是根节点，又是空节点 // son[][]存储树中每个节点的子节点 // cnt[]存储以每个节点结尾的单词数量 // 插入一个字符串 void insert(char *str) { i…
KMP
参考文章 文章链接 模板代码 // s[]是长文本，p[]是模式串，n是s的长度，m是p的长度 求模式串的Next数组： for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] !…
二分
整数二分 bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l …
拓扑排序
拓扑排序的定义 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列…
Acwing – 1497. 树的遍历
题目链接 题目链接 solution 由于给出的是后序遍历与中序遍历，后续遍历的遍历顺序是左右根，中序遍历的顺序是根左右，所以我们先用后序遍历确定根节点，然后再在中序遍历里面找到该节点，然后该节点左边就是左子树，右边就是右子树，左子树的数量就是k - bl +…
并查集
(1)朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n …