zcmimi's blog
nya~
zcmimi
oier & archlinuxer
avatar
zcmimi
2020-11-16 21:56:14

代码见文末

2010

题目 算法 题解
机器翻译 模拟 直接模拟即可
乌龟棋 动态规划 直接四维dp即可
关押罪犯 并查集 二分图 贪心 并查集做法更为方便,记录敌人并查集,从大到小添加边直到出现矛盾(详见代码)
引水入城 记忆化搜索 bfs 贪心 记忆化
avatar
zcmimi
2020-11-14 21:09:40
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

1/74
Search
search