分类 题解 下的文章
- 首页
- 题解
洛谷4156 [WC2016]论战捆竹竿
Luogu UOJ 分析 求出 $s$ 的所有周期 $l_1, l_2, \cdots, l_k$，那么我们相当于要求有多少个 $x \in [0, w - n]$ 满足存在一组 $\{x_i \geq 0\}$ 使得 $\sum_{i = 1}^k x_i l_i = x$。 发现如果 $x$ 可以，那么 $x + n$ 也一定可以，于是我们可以在模 $n$ 意义下跑同余类最短路（这里最短...
CF383E Vowels
Codeforces 分析 这个数量平方的异或和感觉没有什么性质，那么我们只能想办法对每个集合求出数量。 一个想法是先预处理出集合大小为 $1$ 时的数量，然后做子集和，但是这样子会算重：对于 $abc$，$ab$ 处将其计算了两次。 于是考虑容斥：我们在 $a, b, c$ 处加 $1$，$ab, ac, bc$ 处减 $1$、$abc$ 处加 $1$，那么这样子做子集和求出来的数量就是正...
CF455E Function
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
CF888G Xor-MST
Codeforces 分析 这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块，然后合并。 对于这道题，我们考虑把所有数插入到一棵 Trie 中，那么对于每个节点，其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中，必定是左右子树先分别连通，然后再通过一条边合并在一起。 那么我们只需要知道两个数组间两两异或的最小值，将一...
CF1007E Mini Metro
Codeforces 分析 orz yhx 为了方便我们在最后加一个 $a_i = N, b_i = N, c_i = +\infty$ 的站台，其中 $N$ 是一个很大的数。这样子我们可以保证每辆火车恰好送走 $k$ 个人。 设 $f_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ 时刻最少需要放多少辆火车，$g_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ ...
洛谷5617 [MtOI2019]不可视境界线
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
洛谷5292 [HNOI2019]校园旅行
Luogu LOJ 分析 orz myy 可以发现，一条回文路径左右扩展一个相同字符仍然是一条回文路径。 设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径，转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。 因为我们可以在一条边上反复横跳，所以直觉上这个东西只会和奇偶性有关。 对于连接同色点的边，我们对每个连通块单独考虑：如果构成二分图，则可以只保...