洛谷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$ 意义下跑同余类最短路（这里最短...
标签 最短路 下的文章
- 首页
- 最短路
JOISC2020 部分题解
先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ ...
CF718E Matvey's Birthday
Codeforces Luogu 分析 首先可以证明图的直径长度不超过 $15$。 先预处理 $f_{i,j}$ 表示 $i$ 走到一个颜色为 $j$ 的点的最短路、$g_{i,j}$ 表示某个颜色为 $i$ 的点走到某个颜色为 $j$ 的点的最短路。这可以通过以每种颜色为起点 BFS 一遍求出。 接着我们枚举 $i$，并试着找到 $j\in[1,i)$ 使得 $dis(i,j)$ 最小。实...
LOJ6252 「CodePlus 2017 11 月赛」大吉大利，晚上吃鸡！
LOJ 分析 先考虑第一个条件。设 $c_i$ 为经过 $i$ 的 $s\to t$ 的最短路数，那么应该有 $c_a+c_b=c_t$。 再考虑第二个条件。我们可以对每个点求出最短路图上不能到达它的且它不能到达的点集，然后存到一个 bitset 里。这可以直接拓扑排序求出。 枚举 $a$，合法的 $b$ 应该满足 $c_t-c_a=c_b$。开一个 map 存下每个 $c$ 对应的点集，再...
洛谷3547 [POI2013]CEN-Price List
Luogu 分析 显然最短路只有三种可能： 全走 $a$ 边。 把两条 $a$ 边看成一条 $b$ 边，如果还剩一条 $a$ 边就走 $a$ 边。 全走 $b$ 边。 前两种只需要简单 0/1 BFS 一遍即可，关键在于第三种如何处理。 有一个显然的 $\mathcal{O}(m^2)$ 思路是，枚举 $u$ 的出边 $v$ 和 $v$ 的出边 $w$，如果 $u,w$ 间没有连边就用 ...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
CF464E The Classic Problem
Codeforces Luogu 分析 显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。 因为边权全部是 $2$ 的幂，...
洛谷5471 [NOI2019]弹跳
Luogu 分析 首先容易看出一个暴力，即每个点向能到达的点连边，然后最短路即可。 然而边数是 $\mathcal{O}(n^2)$ 级别的，我们需要优化连边。由于是向矩形范围内的点连边，所以考虑 KD-Tree 优化连边。 对于城市 $u$ 向矩形连的边，我们在 KD-Tree 上遍历：如果当前节点范围包含在矩形内，则 $u$ 直接向这个节点连边；如果当前节点范围与矩形无交，则直接返回；否...
洛谷4768 [NOI2018]归程
Luogu 分析 考虑把边按海拔从大到小排序并建 Kruskal 重构树。 每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$，则子树 $u$ 中的点是可以开车到达的，找一个到 $1$ 的距离最小的点即可。 一遍 Dijkstra（关于 SPFA：它死了）预处理出每个点到 $1$ 的最短路，在重构树上维护子树最值即可。 代码 // ====================...
洛谷5304 [GXOI/GZOI2019]旅行者
Luogu LOJ 做法一 将所有关键点随机分到两组中，然后新建两个点 $s,t$，从 $s$ 向第一组中所有点连 $0$ 边，从第二组中所有点向 $t$ 连 $0$ 边，求 $s$ 到 $t$ 的最短路即可。这样子的正确率大概是 $\frac{1}{4}$，所以我们只要多做几次就可以过了。 代码没有。 做法二 分析 事实上没有必要随机。我们枚举二进制位 $i$，将所有不含这个二进制位的关键...