笔记

MY OI

NOI2020 加油!!! NOI2014~2019 题目分析 题目类型 题目类型 2014 2015 2016 2017 2018 2019 2020 预测 贪心 2 1 0 1 0 1 0.5 动态规划 1 2 1 1 ...

k-D Tree 学习笔记

k-D Tree 是一种可以高效处理 $k$ 维空间信息的数据结构,在算法竞赛的题目中一般 $k = 2$。 建树 k-D Tree 具有二叉搜索树的形态,二叉搜索树上的每个节点都对应 $k$ 维空间内的一个点。其每个子树中的点...

容斥 学习笔记

小小的知识点,大大的坑。 容斥原理 设集合 $S_{1\dots n}$,有 $$ \left| \bigcup_{i=1}^n S_i \right| = \sum_{k=1}^n(-1)^{k+1}\sum_{1\le p_1 < p_2 < \cdots < p_k \le n} \left| \bigcap_{i...

莫队 学习笔记

莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。 普通莫队 设定块大小 $T$,将 $m$ 个询问 $[l,r]$ 离线下来...

组合计数 学习笔记

其实不是什么学习笔记,只是稍微整理一下。 排列组合 排列 从 $n$ 个元素中有序的选择 $k$ 个元素的方案数: $$ n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} = n^{\underline{k}} $$ 组合 从 $n$ 个...

生成函数 学习笔记

生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。 普通型生成函数 (OGF) 对于一个数列 $f_n$,定义它的普通型生成函数为 $F(x)$。则: $$ F(x) = \sum_{n \ge 0} f_nx^n $$ $$ f_n =...

模拟退火 学习笔记

又是个之前学过现在忘光了的算法。。。 简介 模拟退火是一种随机化算法,在优化型题目(选手得分依赖于其输出结果与最优解的比较)中非常有用,而这类题目通常为提交答案题。 使用条件 方案的数量极大甚...

动态 DP 学习笔记

动态 DP 在 NOIP2018D2T3 考察后风靡 OI 圈,然而我却一直没学。 引入 考虑这样一个问题: 给定一棵 $n$ 个点的树,点有点权 $w_i$。 有 $m$ 次操作,每次操作给定 $x,y$,表示将 $w_x$ 修改为 $y$。...

原根 学习笔记

数论中的一个小概念,也是 NTT 的基础。 阶 若 $\gcd(a,m) = 1$,使 $a^l \equiv 1 \pmod m$ 成立的最小正整数 $l$,称为 $a$ 关于模 $m$ 的阶,记为 $\text{ord}_m a$。 若 $\text{ord}_m a = l$,则 $\t...

后缀自动机 学习笔记

因为 SA 就很有用了,所以一直不想学 SAM。突然不知道为什么就想学了,可能是为了吊打兔兔吧。 后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。 直观上,SAM 可以理解为将字符串的所...