凌乱之风

分类

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

/ 注册

全部文章（共30篇）

[2022 牛客多校4 C] Easy Counting Problem (生成函数 NTT)

题意给定一个正整数 www 及 www 个数 c0,c1,⋯ ,cw−1c_0, c_1, \cdots,c_{w - 1}c0,c1,⋯,cw−1 qqq 组询问，每次询问给定一个正整数 nnn，计算有多少个长度为 nnn 的字符串满足：每个字符只能取数字 0∼w−10 \sim w ...

2022-08-01

4 235

(树形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 487

2021新高考全国Ⅰ卷 22题

题面: 已知函数 f ( x ) = x ( 1 − ln ⁡ x ) 已知函数f(x)=x(1-\ln{x}) 已知函数f(x)=x(1−lnx) ( 1 ) 讨论 f ( x ) 的单调性 (1)讨论f(x)的单调性 (1)讨论f(x)的单调性 ( 2 ) 设 a , ...

2021-11-06

0 666

高数竞赛笔记

1. 已知函数 f ( x ) 连续且 f ( x + 2 ) − f ( x ) = cos ⁡ x , ∫ 0 2 f ( x ) d x = 1 , 求 ∫ − 1 1 f ( x ) d x 1. 已知函数f(x)连续且f(x+2)-f(x)=\cos x,\int^{2}_{0}...

2021-11-06

0 332

数位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 286

最近公共祖先(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 324

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 397

树状数组

树状数组的基本应用： 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 266

线段树

线段树是用于维护区间信息的一种数据结构，可以在 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 271

莫比乌斯反演

前置知识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 149