区间形态的扩展 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 …

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

满足「结合律」的静态信息 CF1175E Minimal Segment Cover 预处理 $rt_x$ 表示点 $x$ 经过一条线段能到达的最右边的点。 跳区间显然是满足结合律的，可以倍增之，复杂度 $O(n \log_2 n)$。 这类题目有一个重要的小技巧：为了满足最优性，倍增时跳到不能到达 $y$ 的最远的点 $p$，然后判断能一次跳过 …