categories/note/共63篇文章

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

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

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

SAT指Satisfiability(可满足性问题)

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

LG 4782 【模板】2-SAT 问题

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

比如「x_1为true或x_3为false」、「x_7为false或x_2为false」。

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

定义

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

prufer序列

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

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

根号分治是一种

练习

LG 5901 [IOI2009]regions

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

例题: LG 2495 [SDOI2011]消耗战

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

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

我们可以每次都把提供

前置知识:

• 迭代加深搜索
• A*

迭代加深搜索

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

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

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

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

概率

定义详见数学课本

条件概率

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

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

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

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

你需要在每次操作之后