北京笔记Day2

发表于 | 分类于 |

数学 (科普)

1. 求导

  1. 定义

    $ f{}’(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+ \Delta x)-f(x)}{\Delta x} $

  2. 公式

    1. $ (x^{\alpha})’=\alpha x^{\alpha-1} $

    2. $ (e^x)’=e^x $

    3. $ (\ln x)’ = \frac{1}{x} $

    4. $ (sin(x))’=cos(x) $

    5. $ (a^x)’=a^x \ln a $

    6. $ (f(x)+g(x))’=f’(x)+g’(x) $

    7. $ (f(x)-g(x))’=f’(x)-g’(x) $

    8. $ (f(x)g(x))’=f’(x)g(x)-g’(x)f(x) $

    9. $ (f(x)/g(x))’=\frac{f’(x)g(x)-g’(x)f(x)}{g^2(x)} $

  3. 链式法则

  4. 导数求最值

  5. 多元函数求偏导

  6. 例题

    1. BZOJ 3528

    2. 最小二乘法 (没听懂)

2. 积分

  1. 定义

    若有 $F’(x)=f(x) $

    则有 $ \int_{l}^{r}f(x)dx=F(b)-F(a) $

  2. 使用

    1. 杜教筛复杂度证明

    2. 调和级数

      $ \sum_{i=1}^{n} O(\frac{1}{n}) = ? $

      $ \sum_{n=1}^k \, \frac{1}{n} \;>\; \int_1^{k+1} \frac{1}{x}\,dx \;=\; \ln(k+1). $

3. 概率与期望

见PDF

数据结构

1. 莫队

PS:(我也不知道为啥这个算数据结构)

  1. 要求

    1. 若已知 $ [L,R] $ 的信息,可快速求出 $ [L+-1,R] $ 和 $ [L,R+-1] $ 的信息

    2. 离线

    3. 只有询问

    4. 时间复杂度 $ O(n\sqrt n) $

  2. 例题

    1. 小Z的袜子

    2. 作诗(分块)

  3. 在线 (即为分块。。)

2. 莫队扩展

  1. 带修莫队

    1. 做法

      1. 设 $ siz=n^{\frac{2}{3}} $ 或 $ siz=n^{\frac{1}{3}} $

      2. 对询问按 $ (l/s,r/s,t) $ 排序

      3. 乱搞

    2. 复杂度 $ O(n^{\frac{5}{3}}) $

    3. 在线 (即为分块。。)

  2. (莫队上树) 树上莫队

    1. 转为DFS序后在DFS序上莫队

    2. in(a) 表示点a在进入DFS序的第一个位置

    3. 以 $ (in(a)/s,in(b)) $ 排序

3. 动态树 (LCT)