莫队 学习笔记

莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。 普通莫队 设定块大小 $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 =...

《整型溢出》修订版修改内容

本文只记录客观上的修改内容,并不给出任何主观结论。 原版 修订版 Page 5 第 7 章的标题由各方面的敌人修改为四面楚歌。 Page 8~9 删除了一部分“杜子德”。 Page 35 涞阳八中修改为衡阳八中,涞阳...

模拟退火 学习笔记

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

动态 DP 学习笔记

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