C. Constellations 题意 二维平面中有 $n$ 个点，一开始每个点都属于自己的一组。 有 $n-1$ 轮合并过程，每次合并选择距离最近的两组点进行合并，两组点 $A,B$ 之间的距离定义为： $$d(A,B)

介绍 二项式反演是一种特殊的容斥，用来解决 “恰好选 $k$ 个的方案有多少种” 的问题。 一般，我们可以求出 “至多/至

G. Rafting Trip 题意 给定一个 $n \times m$ 的网格，每个网格要么是河流，要么是陆地。 如果是河流，那么它一定是上下左右四个方向之一，代表走到这个位置，下一个位置就

介绍 吉司机线段树可以做到： 区间最大/最小操作（对一个区间内的所有数取 max 或者 min） 维护区间历史最值 我们直接看一道例题： 题意 给定一个数组 $a_1, a_2, …

老是忘，简单记录一下吧。 介绍 一个边权仅为 $0,1$ 的图中跑最短路可以直接用 bfs。 维护一个 deque，每次更新 dis[v] 时就将 v push进去，如果 w(u,v) == 0 就p

介绍 给定一个无向图，找出图中所有的三元环，每个环只能被计一次。(比如 $a,b,c$ 和 $b,a,c$ 都是同一个环)。 我们先处理出每个点的 degree，然后建一个新的图

公平组合游戏 公平组合游戏 Impartial Combinatorial Game (ICG) 满足以下性质： 有 $2$ 名玩家。 $2$ 名玩家轮流操作，在一个游戏集合中选其中一个进行操作。 对于任意一个合法的局面，当前

模版 struct Edge { int from, to, nxt; }; int n; // 变量个数 struct SAT2 { // from[u] 代表 u 所在的SCC编号，scc代表scc编号，sz[scc] 代表对应scc的大小 int dfn[maxn], low[maxn], id, from[maxn], scc = 0,

介绍 我们希望在二进制下枚举所有的 mask，并且枚举每个mask的所有子集。 for (int mask = 0; mask < (1 << n); mask++) { // i 枚举所有物体的选择情况 for (int sub = mask; sub; sub =

介绍 容斥原理用于计算集合的 union 和 intersection 的大小。 集合的 Union: $$|\bigcup_{i=1}^{n} S_i| = \sum_{i} |S_i| - \sum_{i < j} |S_i \cap S_j| + \sum_{i < j < k} |S_i \cap S_j \cap S_k| - … + (-1)^{n-1} |S_1 \cap … \cap S_n|$$ 集合的 Intersection = 全集 - 补集的并集 $$|\bigcap_{i=1}^n