CF578F Mirror Box 题意 在一个 $n \times m$ 的网格中，每个格子里都有一个呈 \ 或 / 状的镜子。 一个合法的网格需要满足从任意一个边界段垂直射进网格中，光线会从相邻的边界段射出，同时网格中的每一段...

Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。 前置知识 高斯消元 在 $\mathcal O(n^3)$ 的时间复杂度下解线性方程组。 【模板】P3389 【模板】高斯消元法 #define Fail r...

CF516E Drazil and His Happy Friends 题意 有 $n$ 个男生 $m$ 个女生，编号分别为 $0 \sim n - 1$ 和 $0 \sim m - 1$。 有 $b$ 个男生和 $g$ 个女生是快乐的，其他人是不快乐的。 在第 $i$ 天，编号为 $i...

数论与图论的结合 基本思想 通过同余构造某些状态，状态之间的关系类似于两点之间的带权有向边。 那么可以以此建图，将某些问题转化为最短路问题，再使用具有优秀时间复杂度的算法求解。 【例题】P3403 ...

CF576E Painting Edges 题意 给定一张 $n$ 个点 $m$ 条边的无向图。 一共有 $k$ 种颜色，一开始，每条边都没有颜色。 定义合法状态为仅保留染成 $k$ 种颜色中的任何一种颜色的边，图都是一张二分图。 有 $...

线段树的一个小应用 核心思想 考虑这样一个问题： 有一些操作，每个操作只在 $l \sim r$ 的时间段内有效。 有一些询问，每个询问某一个时间点所有操作的贡献。 对于这样的询问，我们可以离线后在时间轴...

CF547E Mike and Friends 题意 给定 $n$ 个字符串 $s_{1 \dots n}$。 $q$ 次询问 $s_k$ 在 $s_{l \dots r}$ 中出现了多少次。 $n, \sum |s| \le 2 \times 10^5$，$q \le 5 \times 10^5$。 题解 首先对 ...

CF547D Mike and Fish 题意 给定 $n$ 个整点。 你要给每个点染成红色或蓝色。 要求同一水平线或垂直线上两种颜色的数量最多相差 $1$。 $n,x_i, y_i \le 2 \times 10^5$。 题解 对于每个点，将横纵坐标...

CF575A Fibonotci 题意 $s_{0\dots +\infty}$ 是一个正整数序列。 给定 $s_{0 \dots n - 1}$，对于 $i \ge n$，有 $m$ 个 $i$ 给定 $s_i$，剩下的 $i$ 满足 $s_i = s_{i \bmod n}$。 $f_{0 \dots +\infty}...

CF559E Gerald and Path 题意 有 $n$ 条线段。 每条线段给定其中一端的位置及长度。 求所有线段覆盖的最大长度。 $n \le 100$。 题解 首先对一端位置排序。 考虑 dp，设 $f_{i,j,p}$ 表示考虑前 $i$ ...