Loner


  • 首页

  • 归档

  • 搜索

  • 隐藏背景动画

    显示背景动画

北京笔记Day2

发表于 2018-01-12 | 分类于 笔记 |

数学 (科普)

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)

北京笔记Day1

发表于 2018-01-12 | 分类于 笔记 |

分治

(略)

复杂度分析

$ T(n)=2 * T(n/2)+O(kn) \Rightarrow O(kn*logn) $

CDQ分治

  1. 适用条件:

    1. 离线算法

    2. 每次修改操作对答案贡献独立,操作互不干扰

  2. 简易模型

    计算 $ [mid+1,r] $

    计算 $ [mid+1,r] $

  3. 三维偏序 $ (a,b,c) $

    1. 按 $ a $ 属性排序

    2. 用两个指针扫 $ b_{i}\leq b_{j} $

    3. 用树状数组维护 $ c $ 属性

  4. 例题 (玄学时间)

    1. BZOJ 1176

      …

    2. BZOJ 2716

      …

    3. HDU 5127

      …

    4. Cash

      …

    5. BZOJ 4137

整体二分

  1. 条件:

    1. 答案具有二分性

    2. 修改独立,修改对询问独立

    3. 离线算法

  2. 形如: $ solve(l,r,S) $

  3. 例题:

    1. 静态区间第K小 (主席树)

    2. BZOJ 3110

      1. 线段树套平衡树 (愚蠢的做法)

      2. 权值线段树套线段树

      3. 整体二分

    3. BZOJ 2527

Meet in the middle

  1. 其实就是双向搜索

  2. 例题

    1. 给出一个DAG,求一个点A到另一个点B路径长度为L的方案数

      1. 求出从A和B出发的距离为 L/2 的点及其方案数

      2. ans=集合交集乘积的和

    2. ABCDEF

    3. A

1…56
Zhang_RQ

Zhang_RQ

In solitude, where we are least alone.

27 日志
8 分类
32 标签
友链
  • KingSann
© 2021 Zhang_RQ
由 Hexo 强力驱动
|
主题 — NexT.Pisces v6.0.1