学会清单

· · 算法·理论

以后每学会一个新的知识点都要记录下来！方便有需要的时候复习！QAQ

复习的时候也要记得复习做题技巧整理！！！！

啥时候退役了就公开，算是一篇从初三开始为期数年的OI游记吧。

有些之前学的知识点我会找时间再补充的。

2023.3.1

1.拓扑模板：

例题

2023.3.7

今天模拟赛考了期望，果不其然，又双叒不会算了......

求期望：

求法一：

其中 A_i 为对于事件 A 可能发生的事件， Value_i 为事件 A_i 在我们制定的价值衡量规则中的价值。

求法二：

对于每一个等概率事件，若该事件对我们要求期望值的对象的影响是独立的，也就是不受别的事件影响的，那么我们可以直接将求解期望的对象与每一个等概率事件组合，求解在二者的组合中等概率事件对求解对象的期望值的贡献，然后再相加，其实也可以得到求解对象的期望值。

2023.3.8

对于一个 n 次二项式 (x+y)^n 来说，它的第 k 项为：

T_k=C_{n}^{k}\cdot x^{n-k}\cdot y^{k}

且我们易得下式：

(a+b)^k=\sum\limits_{i=0}^{k}C_k^{i}\cdot a^{k-i}\cdot b^i

2023.3.9 有些东西记错到做题技巧哪里去啦！！！QAQ

组合数递推求解

例题：方格计数（组合计数）

组合数取模

哥德巴赫猜想

例题：划分

角谷猜想

例题：空间跳跃

黎曼猜想

所有正整数都可表示为若干质数的乘积。

二维树状数组の求区间和式子推导

式中的 delta 数组为原二维数组的差分数组， sum_{x,y} 表示原数组 1,1 到 x,y 的前缀和。

sum_{x,y} =\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}num_{i,j} =\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}\sum\limits_{i'=1}^{i}\sum\limits_{j'=1}^{j}delta_{i',j'} =\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot (x-i+1)\cdot (y-j+1)

设 a=x+1,b=y+1 ，然后继续推式子：

\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot (x-i+1)\cdot (y-j+1) =\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot (a-i)\cdot (b-j) =\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot a\cdot b-\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot a\cdot j-\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot b\cdot i+\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot i\cdot j =a\cdot b\cdot \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}-a\cdot \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot j-b\cdot \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot i+\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot i\cdot j =(x+1)\cdot (y+1)\cdot \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}-(x+1)\cdot \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot j-(y+1)\cdot \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot i+\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}delta_{i,j}\cdot i\cdot j

所以当我们要做二维树状数组区间求和操作时，我们一共要定义四个二维数组，它们的值分别为上面的多项式中求和符号后的那个单项式。

例题：P4514 上帝造题的七分钟

2023.3.10

\sum\limits_{i=0}^{n}C_{n}^{i}=2^n \sum_{l=0}^n \sum_{r=l}^n C_{r}^{l} =2^0+\cdots+2^n

其中 a_1 为数列的首项， q 为数列的公比。

2^0+\cdots+2^n =\dfrac{1\times (1-2^n)}{-1} =2^n-1

于是我们最终得到杨辉三角局部三角形求和公式：

\sum_{l=0}^n \sum_{r=l}^n C_{r}^{l} =2^n-1

例题：P7976 「Stoi2033」园游会

2023.3.14

离散化

例题：

权值线段树

板题代码（带易错细节）

2023.3.15

状压DP

板题代码（注意复习细节）

2023.3.21

拉格朗日插值法

现有一个多项式 f(x)=a_0+a_1x+\dots+a_nx^{n-1}

那么我们只需要 n 个不同的 x 带入到 f(x) 中得到 n 个函数值。

我们将代入 x_i 得到的 f(x) 的值表示为 y_i 。

那么对于任意实数 k ，我们都有下式成立：

f(k)=\sum\limits_{i=1}^{n}y_i\prod\limits_{j=1,j\neq i}^{n}\dfrac{k-x_j}{x_i-x_j}

模板代码( O(n^2)做法)

2023.3.21

树剖求LCA

模板代码（记得复习细节）

2023.3.28

2023.3.30

几何中的三种两点距离求法：

在同一几何空间中有两点坐标如下：

a(a_1,a_2,\cdots,a_k),b(b_1,b_2,\cdots,b_k) len=\sqrt{\sum\limits_{i=1}^k(a_i-b_i)^2} len=\sum\limits_{i=1}^{k}|a_i-b_i| len=max\left\{|a_i-b_i|\right\}(i\in [1,k])

A^*算法：Blog

ID 算法：Blog

网络流

EK

线性基

平方数求和公式

\sum\limits_{i=1}^ni^2=\dfrac{n(n+1)(2n+1)}{6}