树上差分 从抽象代数的角度讲，树上差分可以维护所有群上信息。 换句话说，满足结合律，存在「可减性」。 通过差分我们能将一个高纬问题以常数代价转化为低维问题，而问题低一维往往会简单非常多 —— lxl 太 $\textit{Trivial}$ 的我们就不提了。 下文成「前缀」为根到节点的路径。 luogu8201 [yLOI2021] 生活在树上（h…

未完待续 CF1107E Vasya and Binary String 设 $f(i,j,t)$ 为删去区间 $[i,j]$，其中区间右边还有 $t$ 个与 $S[j]$ 相同的字符的最大收益。 $$f(i,j,t) = \max \begin{cases}f(i,j-1,0) + a_{t+1}\\max _{k=i}^{j-1} \Big\{…

区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 $[i,j]$，最后一个元素的来源会对转移产生影响，所以设 $f(i,j,0/1)$ 为考虑区间 $[i,j]$，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单$$f(i,j,0) = [a_i &l…

二分图判定 没啥技巧，最难的是把图论模型建起来。 luogu1330 封锁阳光大学 相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。 图可能不连通，取的是每一张二分图的左右边的较小值。 #include<bits/stdc++.h> using namespace std; #define int …

欧拉路径 定义 从一个点出发，不重不漏地经过图中每一条边的一条路径，允许重复经过节点。 无向图 首先必须是连通图，其次是两种情况。 所有点的度数是偶数。 恰好存在两个点的度数是奇数。 有向图 要求连通。 所有点的入度等于出度。 恰好存在一个节点入度比出度多 $1$，一个节点入度比出度少 $1$。 欧拉回路 定义 起点和终点是一个点的欧拉路径。 无向…

Hankson的趣味题 从质因子的角度考虑。 把 $a,b,c,d$ 都分解了，对于一个质因子 $p_i$，题目给出的条件等价于$$\min \Big( e_{p_i} (x) ,e_{p_i} (a)\Big) =e_{p_i}(c)$$ $$\max \Big( e_{p_i}(x),e_{p_i}(b) \Big) = e_{p_i}(d)$…

质数筛 埃氏筛模板 void prime() { for(int i=2;i<=n;++i) if(!v[i]) { for(int j=i*i;j<=n;j+=i) v[j]=1; // 优化：从i*i开始枚举 } } 线性筛模板 void ora() { for(int i=2;i<=n;++i) { if(!…

[ARC101E] Ribbons on Tree 对于以 $x$ 为根的子树，如果 $(x,fa_x)$ 的边没有被覆盖，那么说明子树内没有任何一个点与子树外的点匹配。 把这些没有被覆盖的边看作特殊边，那么整棵树就被若干特殊边划分成了若干连通块。我们要求的是不含任何特殊边的匹配方案。 考虑容斥。钦定一个边集 $S$，表示 $S$ 内的边一定是特殊…

并查集是一个森林，每棵树表示一个集合，并且这个集合根据某种具有传递性的关系构建起来。 普通并查集关心的信息只有 $x$ 所在集合的根，$fa_x$ 表示的仅仅是一个传递性关系，即 $fa_x$ 与 $x$ 所在集合的根相同。从任意节点往上跳，都能找到它所在集合的根。 使用路径压缩优化，在向上访问节点时，把路径上所有节点的 $fa$ 都改为根，那么就…

图论这一块内容比较多，而且题目涉及的 Trick 也很多，因此分若干篇。 本文略去所有算法本身性质的证明过程。 最短路 Dijkstra和SPFA $\text{Dijkstra}$ 算法基于一个重要的性质：全局最小值不可能再被任何边更新。这样，在边权为非负数的最短路问题中显然满足，在存在负边时不满足。同时，保证了最多从每个节点处扩展 $1$ 次，…