费用流与模拟费用流
可撤销贪心一般就是带约束的最优性问题。
考虑贪心暴力选,然后把不选这个而选被这个决策约束的其它决策这种方案加入堆里,这么反复。
P1792 [国家集训队]种树
贪心选 $a_i$
选 $a{i + 1} + a{i-1}-a_i$
用一个链表维护这个东西,每次我们选一个点,然后把它左右两侧的点标记为不能选,然后把它变成一个权值为 $a{i+1} + a{i-1} - a_i$ 的新点,并且这个新点的左、右邻居都要分别变成 $i+1,i-1$ 的左、右邻居。
费用流消圈算法判断一个费用流的流法是不是最优的。
我们先对这个流法建立一个残量网络,然后你从 $T$ 开始跑 spfa,如果找到了一个负环,那么你把这个负环上所有边 +1 并且反边 -1 就可以得到一个更优的流(显然满足流量平衡,并且费用流更小)
如果不存在负圈,则一定最优。(我不会证明,但是感觉很有道理)
bonus:可以通过上下界网络流处理带负环的费用流问题,但是我不会。
费用流的凸性根据 EK 算法,增广路会越来越长,因此费用关于流量是凸函数。
费用流因为有凸性所以可以解决一些阴间问题。
结合 wqs 二分
字面意 ...
初等高等数学
微分定义约定
y=f(x)当 $\Delta x \to 0$ 时
\Delta y = f(x_0+\Delta x) - f(x_0)其精确值可表示为($A$ 不依赖 $x$)
\Delta y = A\Delta x+o(\Delta x)那么称 $y=f(x)$ 在 $x_0$ 处可微。
记作 $dy=Adx$ 或 $dy=A\Delta x$(下面取前一种)。
定理:$dy=f’(x)dx$,证明显然。
基本微分公式以下认为 $u,v$ 均是 $x$ 的函数。
\begin{equation*}
\begin{split}
d(u+v) & = (u+v)'dx \\
d(uv) & = (uv)'dx \\
d(u\pm v) & = du\pm dv \\
d(cu) & = cdu \\
d(uv) & = vdu + udv \\
d(\frac u v) & =\frac {vdu-udv}{v^2} = \frac {vu'-uv'}{v^2}dx\\
...
数列通项小记
数列通项平凡一次递推数列
a_n=pa_{n-1}+q对于 $p=1$ 的情况,使用等差数列求和。
对于 $p\ne 1$ 的情况,令 $a_n=b_n+k$
b_n=pb_n+q-k+pk令 $k=pk+q$,解之得
k=\frac {q}{1-k}容易知道
a_n-\frac {q}{1-k}=p^{n-1}(a_1-\frac {q}{1-k})特征方程第一类特征方程对于
a_n=p_1a_{n-1}+p_2a_{n-2}+p_3a_{n-3}+\dots构造方程方法如下:
用 $x^n$ 代替 $a_n$
x^n=p_1x^{k-1}+p_2x^{k-2}+\dots解方程,如果正好有 $k$ 个解,那么通项就是
a_n=A_1x_1^n+\dots + A_nx_k^n其中 $A_i$ 是常数,通过待定系数可解。
第二类特征方程对于有理多项式递推,考虑消去常数项。
如
a_n=\frac {1}{a_{n-1}-1}其特征方程为
x=\frac{1} {x-1}
x=\overline\phi,-\phi令 $a_n=b_n+\overline\phi$ 代入 ...