文章

考虑令 $f_{i,j}$ 表示前 $i$ 个数，$b$ 的最后一个是 $j$ 时最小段数。转移： $$ f_{i,j}=[j\not=a_i-j]+\min_{1\leq k< a_{i-1}}\left(f_{i-1,k}+[a_i-j\not=k]\right) $$ 注意到后面的转移， 阅读更多…

定义连边 $(u,v,(l,r),w)$ 表示连了一条 $u\rightarrow v$ 的边，流量有下界 $l$ 和上界 $r$，费用为 $w$ 。现在讨论原网络所有的边： 如果 $f\leq c$： 已经流了 $f$ 单位流量了，连边 $(u,v,(f,f),0)$ 。 考虑退流的可能性，连边 阅读更多…

本题不弱于小 Z 的袜子，考虑分块，令 $B$ 为块数。 先考虑单点修改，可以令 $f(x,y)$ 表示从块 $x$ 中选出一个数，然后从块 $y$ 中选出同样的数的方案数，放到平面上，有值的地方就是一个三角形，询问也是询问一个三角形中的 $f(x,y)$ 和。 怎么做修改，对每个颜色维护一个前缀出 阅读更多…

这一类题带有鲜明的套路：分块，然后将跳大块和跳小块分开计算复杂度，跳大块最多跳 $B$ 次，小块最多暴力更新 $\frac{n}{B}$ 次。 同样考虑维护 $b_i$ 表示 $i$ 第一次跳出所在块会跳到哪里去，那么查询的话就可以两个点往前跳，跳到同一个大块后再继续不断跳 $b_i$ 直到相等，撤 阅读更多…

前言 欢迎各位纠错 正文 背包问题，作为 DP 经典问题，也是 OIer 必须掌握的一门算法，一般有 01 背包，完全背包，多重背包。 01 背包 01 背包是背包中最简单也是最基础的，一般用 $w_i$ 表示第 $i$ 个物品的价值，$v_i$ 表示第 $i$ 个物品的体积，而 $f_{i,j}$ 阅读更多…

正文 并查集你可以理解为是族谱森林（一开始每个节点初始化为自己），我们用 $f_i$ 表示 $i$ 的父亲，一般有以下操作：并和查。 先来说查，查就是字面意思：查找 $i$ 的最早祖先，我们可以递归查找，查找 $i$ 的父亲，再查找 $i$ 的父亲的父亲，依次递归，就有了以下代码。 int find 阅读更多…

这种 d1f 绝对是搞人心态的。 因为一条路径走偶数次是没用的，只考虑树的情况的话，$0$ 走的路径是一定的，简单判断一下即可。 由于操作可逆，将 $0$ 所在目标节点移做根，先把 $0$ 移过去。考虑新增一条边能干啥：对于所在的环，​和 $0$ 最近的节点不动，其他的节点按照顺时针或者逆时针不断轮 阅读更多…

定义质数 $i$ 的数链（集合）$S_{i}$ 包含了 $i$ 在 $[1,n]$ 中所有倍数。 那么对于 $p$ 来说，将 $i$ 的 $S_i$ 当作下标集合，满足 $\gcd(p_a,p_b),{a,b}\subseteq S_i$ 。假设这些 $p_a,p_b$ 均为质数 阅读更多…

按照常规做法先将值域分为 $O(n)$ 段。 考虑一个人 $i$ 在第 $j$ 段时，其他的人选择的所有情况的概率，注意到其他的人可以分为三类：1. 选段在 $j$ 前。 2. 选了第 $j$ 段。 3. 选段在 $j$ 后。第一类对排名的贡献固定，第二类可以算概率（每个人等价），第三类不对排名造成 阅读更多…