Daowuu

分类

动态规划(1) 博弈论(1) 图论(9) 字符串(5) 数学(10) 数据结构(3) 未归档(1) 计算几何(8) 题解(2) 高精度(1)

/ 注册

TA的专栏 37篇文章 0人订阅

14篇文章 1388人学习

8篇文章 1010人学习

10篇文章 1691人学习

5篇文章 935人学习

全部文章（共41篇）

自适应辛普森法来自专栏

二次函数的定积分对于一个二次函数，显然有对于一个奇怪的函数，为了对其求导，我们可以用一个图像近似且容易求导的函数（这里我们使用二次函数）来代替它(拟合)，这样的话精度误差可能会很大，因此我们需要将函数分段拟合。自适应辛普森法显然我们并不知道分成多少段合适，因为段分得越多，精度误差越小，...

计算几何

2020-09-22

0 771

最小割来自专栏

s-t 最小割最小割问题可以形象地理解为：为了不让水从 s 流向 t，怎么破坏水沟代价最小？被破坏的水沟必然是从 s 到 t 的单向水沟。而在有向图流网络 G = (V，E) 中，割把图分成 S 和 T = V - S 两部分，源点 s ∈ S，汇点 t ∈ T，这称为 s - t 割。最大流最小...

图论

2020-09-02

0 858

费用流来自专栏

最小费用最大流假设每条边除了有一个容量限制外，还有一个单位流量所需的费用(cost)。该网络中花费最小的最大流称为最小费用最大流，即总流量最大的情况下，总费用最小的流。证：在残余网络上求最短路是最小费用设有 f 为以以上方式求出的结果，设 f ’ 和 f 流量相同，但是费用更少因为...

图论

2020-08-25

1 1691

最大流来自专栏

概述我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。最大流算法有很多种，基本上分为两类：1.“增广路”算法。例如 Edmonds-Karp 算法、Dinic 算法、ISAP 算法。2.“预流推进”算法。例如 Ford-Fulkerson 增广路方法残...

图论

2020-08-21

0 801

AC自动机来自专栏

#AC自动机时间复杂度： AC自动机是多模匹配算法，能在一个文本串中同时查找多个不同的模式串。注： “fail指针” 、 “蓝色虚点” #include<bits/stdc++.h> using namespace std; const int maxn = 4e5+1; /...

字符串

2020-08-20

0 935

Dirichlet 卷积来自专栏

定义定义两个数论函数 f，g 的 Dirichlet 卷积为：性质 Dirichlet 卷积满足以下运算规律：交换律结合律分配率，其中为 Dirichlet 卷积的单位元（任何函数卷都为其本身）

数学

2020-08-19

0 855

积性函数来自专栏

积性函数：若函数满足且，都有，则为积性函数。完全积性函数：若函数满足且都有，则为完全积性函数。性质若和均为积性函数，则以下函数也为积性函数：设若为积性函数，则有若为完全积性函数，则有例子积性函数欧拉函数...

数学

2020-08-19

0 831

莫比乌斯反演来自专栏

莫比乌斯反演和是定义在非负整数集合上的两个函数，并且满足条件。那么，我们得到结论：证：莫比乌斯函数在上面的公式中有一个莫比乌斯函数，它的定义如下：若，那么若，均为互异素数，那么其他情况下性质对于函数，它有如下的常见性质：设表示...

数学

2020-08-18

0 684

杨辉三角来自专栏

排列：组合：这里把组合数用符号表示，称为二项式系数。杨辉三角（国外称帕斯卡三角）是二项式系数的典型应用。每一行从上一行推导而来。复杂度观察的展开：每一行展开的系数刚好对应杨辉三角每一行的数字。也就是说杨辉三角可以用来定义和计算。二项式系数：，也就是杨辉三角中第 ...

数学

2020-08-18

0 635

素数来自专栏

素数：一个数 n ，若不能在[2,n-1]中找到一个能整除 n 的数 d ，则 n 为素数。试除法判断素数时间复杂度： bool is_prime(int n) { if (n <= 1) return false; for(int i = 2; i * i <=...

数学

2020-08-18

0 570