Mai Icy

“2023 年 12 月”

算法学习笔记6——ST表

算法学习笔记(6): Sparse Table (ST 表) 简介 ST 表 是一个数据结构,用于计算RMQ问题,其思想基于动态规划 RMQ问题 RMQ即Range Minimum / Maxi...

算法学习笔记5——异或哈希

算法学习笔记(5): 异或哈希 简介 异或哈希主要利用了异或操作的特殊性,再从特殊性出发,解决阻挡特殊性的问题。 异或操作的特殊性 异或操作是对数字的二进制表示按位相加并对2取余,它的运算十分高...

ACM程序课算法笔记7——母函数

ACM程序课算法笔记7——母函数 定义 母函数实际上就是一个多项式和其系数表达的关系, 对于多项式x2 + 2x + 1就是序列1 2 1的母函数 母函数的基础转化 问题 若有1克、2克、3克、...

算法学习笔记4——莫比乌斯反演前置知识

算法学习笔记(4): 莫比乌斯反演前置知识 数论函数 定义在所有正整数上的函数被称为算数函数(数论函数) 积性函数 当函数f属于数论函数,且 对于任意互质的正整数p,q 有f(pq) = f...

数据库学习笔记1——B+树

用途 B+树的主要目的之一就是存储所有键值对,并确保键的有序性,以便于高效的查找操作。B+树是一种树状数据结构,其中所有的键值对都存储在叶子节点上,而内部节点仅包含用于导航的关键字。 内部节点...

算法学习笔记3——快速傅里叶变换(FFT)

算法学习笔记3——快速傅里叶变换(FFT) 问题: 内容:对于两个多项式快速取得两个多项式的乘积。 对于最基本的解法,便是通过分配率将两个多项式中的每一项都相乘,然后取得计算结果。 对于两个n项...

ACM程序课算法笔记6——二分图匹配

ACM程序课算法笔记6——二分图匹配 前置定义 二分图(Bipartite Graph ):如果一个图的顶点可以分为两个集合X和Y,图的所有边连接的两个点都来自不同的集合,则称该图为“二分图”或...

算法学习笔记2——基环树&字典树

算法学习笔记(2): 基环树&字典树 基环树 若一个图有n个节点,n-1条边,那么这个图一定无环,此时若再增加一条边,必定会出现一条环。 由此可得 n个节点,n条边,必定有个环,去掉这个...

算法学习笔记1——极角排序

算法学习笔记1——极角排序 基础含义 对于一个平面的多个点,选择一个点作为极点O,再从O出去一条射线定为极轴OX(一般把X轴正半轴作为极轴),对于每个平面上的点我们有一种新的表示方法:极坐标(γ...

ACM程序课算法笔记5——组合博弈

ACM程序课算法笔记5——组合博弈 问题引入 问题:一共有10张牌,你与一个人进行游戏,每次只能取走1或2或3张牌,谁取走最后一张,你是先手,如何获胜。 题解:根据以前的经验,我们能保证一轮取走...