lxl的数据结构
STL
vector 的 size 是 unsigned 的,-1 会爆炸。
二叉堆查询是 O(1)的。
加点你直接在末尾加然后一路交换父亲和自己。
删点你就把最后的点加到头上然一路顺着儿子找下去,把最小的儿子放上来。
合并果子的证明类似于一棵二叉树,最优方案 $\sum_{i}a_idep_i$。
最小的两堆一定最深。不然交换最深层的某堆更优。
同层的叶子互换无影响。
然后归纳。
经典问题给出正数序列求前 k 小的子区间和。
从堆里挑出一个区间,然后把它的左右两边的扩展加入堆。
并查集bzoj2054区间赋值,一次询问。
经典时间倒流,每个位置只会被修改一次。
LCABJOI2014 大融合支持加边,查经过某条边的简单路径数量。
先离线建树,然后并查集动态维护子树大小,这个可以变成链加,单点查,树状数组dfn维护即可。
P4211q 次求 $\sum_{l\le i\le r}dep(lca(i,z))$
经典结论:深度=点到根之间所有点的数量。
因此我们差分,每次把一个点到根的路径 +1,然后查询 z 到 根的路径。
P4216求第 i-c 时刻 x->y 的和,树 ...
网络流trick总结
网络最大流将流量作为路径,容量作为移动的限制比如 [SCOI2007]蜥蜴 这个题,就是典型的将蜥蜴的移动看成流量。
这是最经典的网络流做法。
这种问题可以处理:
边有限制,问最多几条路径。
最多的不相交路径(等价于第一种)
增量网络流/分层图就是在上一次跑的基础上再新加若干点然后再跑网络流。
复杂度玄学,可以优化常数。
比如 P2754 [CTSC1999]家园 / 星际转移问题 就可以这么做。
这种方法常常和枚举时间放在一起。
多个相同问题最优化个数一个问题是相同的,我来好几个。可以建出一个问题的图,然后完成节点向 $T$ 连边,然后流量设成问题个数。
匹配问题这个没啥好说,就是硬匹配。
但是注意建图的技巧。
二分最值有些时候网络流可以通过最大流检验是否存在完美匹配这种方式来做一些 check 问题,于是就可以二分了。
P2402 奶牛隐藏
拆出入点转二分图网络流比较喜欢处理二分图的问题。
拆出入点这个技巧有两个作用:一个是分层,为了区分我这个流量是从哪里过来的还是就是原本在那里的;还有一个作用就是限制点上的流量。
前缀限制转区间限制CF628F Bear and Fair ...
多项式与生成函数
前言经过一段时间的学习,感觉生成函数主要还是用来优化计数 dp 的,比如你看到一个卷积形式就要想到分治 NTT,看到一个奇怪的图计数或者序列计数就要想到把他的生成函数列出来…
多项式前置知识NTT不打算再学一遍了.
多项式求逆$F(x)\equiv F_0(x)\pmod {x^{n/2}}$
$F^2(x)-2F_0(x)F(x)+F_0^2(x)\pmod {x^n}$
两边同时乘 $G$
$F\equiv2F_0-F_0^2G$
多项式牛顿迭代直接放结论。
$F=F_0-\frac {G(F_0)} {G’(F_0)}$
多项式开根令 $H(F(x))=G^2(x)-F(x)$
有 $F\equiv F_0-\frac{G^2-F_0}{2G}\equiv G/2+F_0/2G$
多项式求 ln两边导,再积分
$\int G’(x)/G(x)=F(x)$
于是求导求逆积分即可。
多项式 exp变形,令 $H(F)=ln(F)-G$
$F=F_0-(ln(F)-G)F_0=(1-ln(F_0)+G)F_0$
多项式带余除法$A=BC+R$
$A^T\equiv B^TC^T\pmo ...
欧拉回路
定义什么的就不说了。
Hierholzer 算法求欧拉回路“逐步插入回路法”。
就是先找到一个回路,然后把回路上一个点替换成一个回路,重复这个操作。
这样暴力做是 $O(m(n+m))$ 的,把找环和 Hierholzer 算法合并可以做 $O(n+m)$
void Hierholzer(int x) { // 关键函数 for (int& i = cnt[x]; i < (int)beg[x].size();) { if (beg[x][i].exists) { edge e = beg[x][i]; beg[x][i].exists = 0; beg[e.to][e.revref].exists = 0; ++i; Hierholzer(e.to); } else { ++i; } } ans.push(x);}
疑问:找边的话,怎么办捏。
欧拉路径编码一个很巧妙的东西。
求一个字符集为 $m$ 的环,使 ...
容斥反演的再探索
容斥原理
|\bigcup_{i=1}^nA_i|=\sum_{S\subseteq \{1,\dots,n\},S\neq \varnothing} |\bigcap_{i\in S}A_i|(-1)^{|S|-1}
\bigcap_{i=1}^{n}A_i=\sum_{S\subseteq\{1,\dots ,n\}}(-1)^{|S|}|\overline{\bigcup_{i\in S} A_i}|其中,我们认为全集 $U={1,\dots, m}$ 当中每一个元素都代表着一个事件(或者用计数题的专有名词,方案)。$m$ 是所有方案的个数。
方案是容斥原理当中的最小单位,它并不类似于期望,是不可分割的。
而 $A_i$ 表示满足条件 $p_i$ 的所有方案构成的集合,$p_i$ 是题目给定的一个限制。
那么原理一可以表述为:所有限制中至少满足一个可以转化为求所有非空限制子集全部满足。
原理二可以表述为:所有限制必须满足可以转化为求所有限制子集都不满足。
这两个东西的本质是 $\sum_{i=0}^n\binom{n}{i}(-1)^i=[n=0]$ 作用到集合当中所有元素的形 ...
cyx的动态规划优化
前言对于最小化问题,二元转移函数 $w(i,j)$ 满足
w(i,j)+w(i+1,j+1)\le w(i,j+1)+w(i+1,j)也就是转移交叉优于转移包含,也就是决策单调性。
性质四边形不等式是二维差分非正。
满足四边形不等式的矩阵,行最小值单调递增。
模型最短路型dpf(i)=\min_{0\le j
后缀自动机
后缀自动机后缀自动机可以简单地理解成是点数最小的自动机,满足这个自动机可以识别任何一个 $S$ 的子串。
$\text{endpos}$ 等价类对于 $S$ 的一个子串 $T$,称 $T$ 的 $\text{endpos}$ 集合为 $S$ 中所有出现 $T$ 的结尾位置。两个 $T$ 是等价的当且仅当它们的 $\text{endpos}$ 集合是相同的。
根据后缀树,可以意识到这个东西和 $\text{startpos}$ 等价类是一样的,所以这个玩意也是最多 $2n-1$ 个($n$ 充分大)。
同样的,一个 $\text{endpos}$ 等价类也由 $[mn,len]$ 表示,即所有位置向前延申 $[mn,len]$ 的长度都在这个等价类里。
显然,你往一个等价类里面扔一个前缀会得到另外一个等价类。
后缀链接我们把每一个 $\text{endpos}$ 等价类退掉一个前缀得到的新等价类作为这个等价类的父节点,连接父子节点的边叫做后缀链接,简称树边。
转移把一个 $\text{endpos}$ 等价类增加一个字符可以得到另一个新的等价类,这种边称为转移,也叫 DAG 边。
根据后 ...
二分图与网络流
思考再三还是打算记一下这个玩意。
知识清单/目录:
二分图概念与判定(会)
二分图最大匹配(会)
二分图最大权匹配(不会)
Hall 定理(不会)
网络最大流(会)
最小费用最大流(会)
上下界网络流(不会)
网络流扩展与建模举例
1.二分图概念与判定
二分图等价于图可以被黑白染色(二染色)。
二分图黑白染色方案数为 $2^c$,其中 $c$ 是连通块个数。
可以被黑白染色等价于图上不存在奇环。
[HNOI 2019] 校园旅行首先有一个 $m^2$ 的经典 BFS,从一个点或一个边出发向外拓展出一条回文链。
考虑把图进行重构,对于 $n\ge 2$ 的同色连通块,如果是二分图,只需要保留一棵生成树,否则需要保留一棵生成树+一条奇环,比如一个自环。
证明是显然的,因为我们其实可以只关心一个点到达另一个点所构成的所有路径的奇偶性。大小为 $1$ 的点是不影响的。
2. 二分图最大匹配
二分图匹配最大当且仅当原图不存在增广路。
匈牙利算法:枚举左部点 $1\dots i$,时刻维护该前缀与所有右部点的最大匹配(在线加点),对于新加进来的 $i$,枚举它连出去的所有边,找增广 ...
曼哈顿与切比雪夫距离
定义
切比雪夫距离: $\max{|x_i-x_j|,|y_i-y_j|}$
直观感受一下,它描述两个位置最大的差量。
曼哈顿距离:$|x_i-x_j|+|y_i-y_j|$
直观感受一下,它描述两个位置的垂直距离。
转化考虑建立直角坐标系。
到原点切比雪夫距离为 $1$ 的点构成一个平行于坐标轴的正方形。
而曼哈顿距离为 $1$ 的点构成了一个斜 $45\degree$ 放置的正方形。
考虑将切比雪夫距离为 $(x,y)$ 的点绕原点旋转 $45\degree$ 然后缩小,即可得到对应的曼哈顿距离。
具体地,考虑
\begin{bmatrix}
\hat i\\
\hat j
\end{bmatrix}
\to \begin{bmatrix}
\hat i + \hat j\over 2\\
\hat i - \hat j\over 2
\end{bmatrix}同理,我们有
\begin{bmatrix}
\hat i\\
\hat j
\end{bmatrix}
\to \begin{bmatrix}
\hat i + \hat j\\
\hat i - \hat j
...
三四元环计数
问题给出 $n,m$ 这样一张图,求图上所有的三、四元环。
定向引理将每条边定向,使得 $u\to v$ 当且仅当 $\deg u\le \deg v$。
有性质:任意点出度不超过 $\sqrt m$。
证明:
Case 1
$\deg u \le \sqrt m$ 时,显然成立
Case 2
$\deg u > \sqrt m$ 时,若 $u\to v$,则 $\deg v>\sqrt m$。而这样的 $v$ 最多 $\sqrt m$ 种。
三元环计数考虑一个定向的三元环:
$1\to 2\quad 2\to 3\quad 1\to 3$
这样的情况是唯一的。
我们暴力枚举 $1\to 2$,再枚举 $2\to 3$,再检查是否存在 $1\to 3$。
实际实现的时候通常采用打 tag 的方式解决第三步。
四元环计数一个四元环的情况会有很多种。
我们先考虑其中度数最大的点,不妨记为 $1$。
那么 $2\to 1\quad 3\to 1$ 分别是两条与 $1$ 相邻的边。
发现 $4$ 需要满足的是它在原图上与 $2,3$ 连边并且 $\deg 4\le ...