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

CF512D Fox And Travelling 题意 给定一张 $n$ 个点 $m$ 条边的无向图。 一个点只有当与它直接相连的点中最多只有一个点未被遍历过时才可被遍历。 询问对于每个 $k \in [0,n]$，遍历 $k$ 个点的方案数。 $...

CF576D Flights for Regular Customers 题意 给定一张 $n$ 个点 $m$ 条边的有向图。 一开始你在 $1$ 号节点，你要走到 $n$ 号节点去。 只有当你已经走过了至少 $d_i$ 条边时，你才能走第 $i$ 条边。 问最...

CF505E Mr. Kitayuta vs. Bamboos 题意 给定 $n$ 个数 $h_{1 \dots n}$。 你需要进行 $m$ 轮操作，每轮操作为 $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i - p, 0)$。 每轮操作后每个 $h_...