笔记

有向图强连通分量 几个有向图连通性的概念 强连通分量 强连通图：若对于一个有向图中任意两个节点 x,yx, yx,y，既存在从 xxx 到 yyy 的路径，也存在从 yyy 到 xxx 的路径，则称该有向图为「强连通图」。（注意是路径不是边...

思想 先搜索前一半的状态，再搜索后一半的状态，再记录两边状态相结合的答案。 暴力搜索的时间复杂度通常是 O(2n)O(2^{n})O(2n) 级别的。但折半搜索可以将时间复杂度降到 O(2×2n2)O(2 \times 2^{\frac{n...

栈 栈是 OI 中常用的一种线性数据结构。 栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。 下文均使用名为 st ，栈底为 st[1] ，栈顶为 st[top] ...

P1993 小 K 的农场 查分约束的主要思想在于建边。 观察 nnn 个未知数组成的不等式组： 给定 nnn 个数和 mmm 个约束条件（如 xi−xj≤cx_i - x_j \leq cxi​−xj​≤c），求一组解。 约束条件可以转化...

树状数组 简介 树状数组用于处理较简单的区间操作。 优点：码量比线段树小，效率比线段树高。 缺点：功能有限，复杂的区间操作问题无法解决。 一般来说，能用树状数组解决的问题，就没有必要使用线段树。 这张来自 OI Wiki 的图展示了树状数组...

挖坑

拓扑排序的英文名是 Topological sorting。 拓扑排序要解决的问题是给一个图的所有节点排序。 拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。 ——OI-WiKi 拓扑排序是在 DAG（...