zcmimi's blog

categories/note/共63篇文章

avatar
zcmimi
2020-10-10 19:06:08

分块是一种非常好用的根号算法,本质上是暴力优化技巧

原理是将序列分成\sqrt n块,预处理出每个块的结果,在查询时只需要在完整块的基础上枚举散块更新答案即可

复杂度\mathcal O(n\sqrt n)

avatar
zcmimi
2020-10-02 23:34:21

SAT指Satisfiability(可满足性问题)

k-SAT指每个限制有k个条件,而当k>2时该问题为NP完全的,只能暴力

LG 4782 【模板】2-SAT 问题

n个布尔变量x_1,x_2,\dots,x_n,另有m个需要满足的条件,每个条件的形式都是「x_itrue/falsex_jtrue/false」.

比如「x_1truex_3false」、「x_7falsex_2false」。

2-SAT问题的目标是给每个变量赋值使得所有条件得到满足。

avatar
zcmimi
2020-10-01 16:21:19

定义

H_n = \begin{cases} \sum_{i=1}^n H_{i-1} H_{n-i} & n \ge 2 \\ 1 & n = 0, 1 \end{cases}

avatar
zcmimi
2020-09-28 14:07:23

prufer序列

这是一种将带标号的树用一个唯一的整数序列表示的方法.

很多与度数有关的树上计数问题,都可以用它以及它的性质来解决

avatar
zcmimi
2020-09-25 20:10:32

根号分治是一种

练习

LG 5901 [IOI2009]regions

avatar
zcmimi
2020-09-25 14:51:21

虚树是一种统计树上信息的技术

例题: LG 2495 [SDOI2011]消耗战

如果树的点数很少,可以直接树上dp

可以发现\sum k_i \le 5 \times 10^5

我们可以每次都把提供

avatar
zcmimi
2020-09-23 17:16:30

前置知识:

  • 迭代加深搜索
  • A*

迭代加深搜索

迭代加深搜索是一种每次限制搜索深度的深度优先搜索。

首先设定一个较小的深度作为全局变量,进行DFS

每进入一次DFS,将当前深度加一,当发现大于设定的深度就返回。

如果在搜索的途中发现了答案就可以回溯

avatar
zcmimi
2020-09-09 18:14:00

概率

定义详见数学课本

条件概率

P(B|A)A发生的前提下,B发生的可能性

P(B|A)=\dfrac{P(AB)}{P(A)}

乘法公式

P(B|A)P(A)=P(AB)=P(A|B)P(B)

全概率公式

设$\forall i

avatar
zcmimi
2020-09-03 21:35:00

LG 4719 【模板】"动态 DP"&动态树分治

给定一棵n个点的树,点带点权。

m次操作,每次操作给定x,y,表示修改点x的权值为y

你需要在每次操作之后

avatar
zcmimi
2020-09-02 07:35:00
1/7
Search
search