洛谷6096 [JSOI2015]地铁线路
Luogu 分析 第一问考虑最短路。对于每条线路建一个点,线路上的站向线路连边权为 $1$ 的边,线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。 第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。 假设一条线路的 $dis$ 为 $d$,则我们可能在 $dis$ 为 $d-1$ 的站上车,在 $dis$ 为 $d...
Luogu 分析 第一问考虑最短路。对于每条线路建一个点,线路上的站向线路连边权为 $1$ 的边,线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。 第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。 假设一条线路的 $dis$ 为 $d$,则我们可能在 $dis$ 为 $d-1$ 的站上车,在 $dis$ 为 $d...
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉,其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$,那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫,维护 ...
Codeforces 分析 题目给的操作就是区间异或。考虑将原数组差分,那么我们相当于每次可以将两个距离为 $a_i$ 的位置异或 $1$,然后求从全 $0$ 数组生成原数组的最小步数。 我们将这个东西反过来,变为求原数组的差分数组生成全 $0$ 数组的最小步数。 注意到原数组的差分数组至多有 $20$ 个 $1$,因此可以考虑状压 DP。 设 $dp_{S}$ 表示 $S$ 中的 $1$...
Luogu 分析 其实就是要求 Voronoi 图的对偶图最短路。 可以通过半平面交求出 Voronoi 图的每个区域,然后对于每条直线连边即可。 然后直接跑 BFS 就好了。 注意特判 $n = 0$。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.c...
Luogu 分析 考虑对网格图进行分治。 假设当前分治的范围是 $(lx,ly)\sim(rx,ry)$ ,询问的范围是 $ql\sim qr$ 。 找到矩形范围的长边,然后用一条中轴线切成两半。 这时每个询问有两种情况: 查询的两点不在中轴线同侧,此时最短路一定经过了中轴线上的某个点。那么对于中轴线上的每一个点,跑最短路,然后更新询问区间内每个询问的答案。 查询的两点在中轴线同侧,此时最...
Luogu 分析 同余类最短路。 设 $a$ 中的最小值为 $k$ 。容易发现,如果能表示出 $xk+t\;(0\leq t<k)$ ,那么也能表示出 $(x+1)k+t$ 。 把 $t$ 看做余数,然后对于每个 $a_i$ ,从 $t$ 向 $(t+a_i) \bmod k$ 连一条边权为 $a_i$ 的边。 然后跑 SPFA 求出最短路,再对每个余数统计答案即可。 代码 //It ...
Luogu 分析 将每种金属看做一个点 $(a_i, b_i)$,那么两点能配出的所有合金一定在两点构成的线段上。 问题转为给出 $m$ 个点,求一个以这 $m$ 个点为顶点的边数最少的多边形包含 $n$ 个关键点。 如果 $n$ 个点都在 $(x,y)$ 左侧,连一条从 $x$ 到 $y$ 的边权为 $1$ 的边,这样子满足条件的多边形就变成了图上的一个圈。 我们需要求最小圈, Floy...
Luogu 分析 斯坦纳树模板题。 设 $f_{i, S}$ 表示 $i$ 号结点,与其它节点连通性为 $S$ 时的最小代价。 转移分两种情况: 由子集转移而来 第二个方程是有后效性的,但是它长得很像三角形不等式,所以可以跑最短路转移。 代码 //It is made by M_sea #include <algorithm> #include <iostream...