整除 定义 设$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,又叫做树堆,它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性,输入的序列不…
树链剖分简介 链剖分 指对树的边进行划分的一种操作,目的是减少在链上修改、查询等操作的复杂度。链剖分分三类:轻重链剖分、虚实链剖分和长链剖分。 树链剖分思想 通过轻重链剖分将树分为多条链,保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分,节点到重儿子,也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间,把所有重链首尾相接组…