整除 定义 设$a,b \in \mathbb{Z}$，如果存在$q \in \mathbb{Z}$，使得$b=aq$，那么就可以说$b$可以被$a$整除，记作$a \mid b$，且称$b$是$a$的倍数，$a$是$b$的约数（因数、除数） 性质 $a \mid b \Longleftrightarrow -a \mid b \Longleftr…

最小生成树的介绍 生成树的定义 在一个具有$ n $个点的无向连通图中，选出$ n-1 $条边将$ n $个点连接起来，构成一棵树。 注意：只有连通图才有生成树，非连通图只有生成森林。 最小生成树的定义 我们定义无向连通图的最小生成树为边权和最小的生成树。 最小生成树算法 Kruskal算法 实现 Kruskal算法是一种常见并且好写的最小生成树算…

传送门 题目理解与强调 精简一下题意：本题给出一个字符串，在无视非字母、字母大小写的情况下，字符串 helloword 出现的次数。 题解 读入问题 在无其他问题的情况下，依然过不了，可以尝试我这一套读入程序。 char c; while((c=getchar())!=EOF){ } 解决主体问题 问题很简单，从第一个数字枚举整个字符串，先除去非字…

前置知识 在此之前，你需要学习双端队列 简介 单调队列是用于解决滑动窗口类问题的数据结构，即在一个长度为 $n$ 的序列中求连续 $k$ 个数字中的最值问题，单调队列时间复杂度为 $O(n)$ ，这比「ST表」与「线段树」算法更优化。 更广泛地，在以下两种情况时，可以考虑使用单调队列优化。 状态转移方程形如 $dp_i=\min_{0\le j \…

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。 Treap Treap简介 特点与作用 Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不…

树链剖分简介 链剖分 指对树的边进行划分的一种操作，目的是减少在链上修改、查询等操作的复杂度。链剖分分三类：轻重链剖分、虚实链剖分和长链剖分。 树链剖分思想 通过轻重链剖分将树分为多条链，保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分，节点到重儿子，也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间，把所有重链首尾相接组…