凌乱之风

算法

AcWing寒假每日一题(41) codeforces(52) VJ比赛(10) 其他(3) 数据结构题(3) 数论题(15) 题解(1)

/ 注册

全部文章 / 算法（共10篇）

(树形DP)最大独立集、最小点覆盖、最小支配集

1. 最大独立集 \large1.最大独立集 1.最大独立集选出最多的点,使得所有点都是不相邻的状态表示： d p i , j dp_{i,j} dpi,j 表示以 i i i 为根的树，如果 j j j 为 0 0 0 ，表示不选这个点，如果 j j j 为 1 1 ...

2021-11-06

0 504

数位DP(DFS)

由于算法提高课的数位DP的非搜索做法比较难想，所以总结一下数位 DP \text{DP} DP的 DFS \text{DFS} DFS写法，个人感觉 DFS \text{DFS} DFS做法才是数位 DP \text{DP} DP的正解。数位DP问题一般给定一个区间 [ L , R ] [L,R...

2021-11-06

0 296

最近公共祖先(LCA)、树上差分

最近公共祖先 (LCA) \text{(LCA)} (LCA)：给定一颗有根树，若节点 z z z既是节点 x x x的祖先，也是节点 y y y的祖先，则称 z z z是 x , y x,y x,y的公共祖先。在 x , y x,y x,y的所有公共祖先种，深度最大的一个称为最近公共祖先，记作...

2021-11-06

0 337

tarjan算法求SCC，e-DCC，v-DCC

在介绍算法之前先引入几个概念：时间戳：在深度优先搜索时，每个点 x x x第一次被访问的顺序为时间戳，记作 d f n [ x ] dfn[x] dfn[x]（从 1 1 1开始）追溯值：从 x x x开始走，所能遍历到的最小时间戳，记作 l o w [ x ] low[x] low[x...

2021-11-06

0 404

树状数组

树状数组的基本应用： O ( log ⁡ n ) O(\log n) O(logn)单点修改、区间查询原理：设区间 [ 1 , R ] [1,R] [1,R]，对区间右端点 R R R做二进制拆分，有： R = 2 x 1 + 2 x 2 + ⋯ + 2 x k R=2^{x_1}+...

2021-11-06

0 274

线段树

线段树是用于维护区间信息的一种数据结构，可以在 O ( log ⁡ n ) O(\log n) O(logn)的复杂度内实现区间修改，区间查询等操作，还可以维护各种满足结合律的信息。原理：线段树的建树：设有数组 a i , i ∈ [ 1 , n ] a_i,i \in[1,n] ai,i...

2021-11-06

0 279

莫比乌斯反演

前置知识1:整除分块 ① : ⌊ a b c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ ①:\lfloor \dfrac{a}{bc} \rfloor = \lfloor \dfrac{\lfloor \dfrac{a}{b} \rfloor}{c} \rfloor ①:⌊bca⌋=⌊c⌊ba⌋...

2021-11-06

0 158

BSGS、exBSGS

BSGS (Baby Step Giant Step) : \text{BSGS (Baby Step Giant Step)}: BSGS (Baby Step Giant Step): 给定正整数 a , b , p , a ⊥ p a,b,p,a \perp p a,b,p,a⊥p ，求满...

2021-11-06

0 277

狄利克雷卷积

定义：对于两个数论函数 f ( x ) , g ( x ) f(x),g(x) f(x),g(x) 那么它们的卷积 h ( x ) h(x) h(x) 记作 f ( x ) ∗ g ( x ) f(x) * g(x) f(x)∗g(x)，式子如下： f ( x ) ∗ g ( x ) ...

2021-11-06

0 501

杜教筛

杜教筛杜教筛可以在 O ( n 2 3 ) O(n ^{\frac{2}{3}}) O(n32) 的复杂度内求解积性函数的前缀和设数论函数 f ( x ) f(x) f(x)，求 ∑ i = 1 n f ( i ) \sum_{i=1}^{n}f(i) i=1∑nf(i) 令 ...

2021-11-06

0 263