更佳的阅读体验：2023 国庆集训 Day 5B 笔记，本文同步发表于 洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

最短路

洛谷 P4667 - [BalticOI 2011 Day1] Switch the Lamp On

  • 更优的复杂度：$O(NM)$。
  • 每个格子看作点。
  • 如果当前电线是左上到右下，建边权为 $0$ 的边；
    如果当前电线是右上到左下，建边权为 $1$ 的边，表示需要改变。
  • 反之亦然。
  • 01 最短路，用队列维护。

洛谷 P1462 - 通往奥格瑞玛的道路

  • 最大值最小？二分！
  • 保留二分值以下的边，跑最短路，检查是否能活着到达 $n$ 号点。

洛谷 P1144 - 最短路计数

洛谷 P1119 - 灾后重建

  • Floyd 理解。

洛谷 P4822 - [BJWC2012] 冻结

  • 分层图。
  • 分层图，建 $k + 1$ 层点跑最短路。
  • 另一视角：动态规划。

洛谷 P9402 - [POI2020-2021R3] Droga do domu

  • 分层图。
  • 按照 $k$ 分层，设 $f[k][i]$ 表示换乘了 $k$ 次，到达第 $i$ 个点最早什么时间到。
  • 如何转移？因为公交车线路经过哪些点是有顺序的，我们枚举每条线路，从前向后走即可。

洛谷 P2371 - [国家集训队] 墨墨的等式

  • 同余最短路。
  • 考虑 $b \mod a_1 = \sum_{i = 2}^n a_i x_i \mod a_1$。
  • 以 $a_1$ 为中心视角，如果 $b$ 能拼出来，那么 $b + a_1$，$b + 2a_1$，$b + ka_1$ 都能拼出来。
  • 也就是 $\mod a_1$ 同余的从一个开头开始，后面都能拼了。
  • 我们考虑用 DP / 最短路求出这个开头是多少。
  • 设 $f[i]$ 表示用 $a_2, \cdots, a_n$ 拼出最小 $\mod a_1 = i$ 的数是多少，转移，$f[i] = \min_{j = 2}^n f[i - a_j \mod a_1]$。

AT_arc084_b - [ABC077D] Small Multiple

  • 如同余最短路。

洛谷 P5304 - [GXOI/GZOI2019] 旅行者

  • 随机分组或二进制分组。
  • 分成两组 ，求出从 $A$ 某个点到 $B$ 某个点的最短路。
  • 新建超级原点和超级终点即可。

差分约束

洛谷 P3385 - 【模板】负环

  • 负环。

洛谷 P5590 - 赛车游戏

  • 差分约束。

洛谷 P3530 - [POI2012] FES-Festival

  • $A$ 恰好比 $B$ 快 $1$ 秒，可以用两个不等式来约束，$A \le B - 1$，$A \ge B - 1$。
  • 我们发现所有关系都可以用不等式来约束，所以考虑差分约束。
  • 对于强连通分量，任意两个点都有约束，我们找到最短路最大的两个点 $+ 1$ 即为此连通分量的答案，不同联通分量的答案不影响。
  • 连通分量内部，由于此题两点距离是 $1$，所以如果存在一个最短路，那么最短路的所有值都可以取到。
  • 连通分量之间由于只有单向关系，可以令一个无限小，一个无限大，使得不同连通分量处于不同的值域。

拓扑排序

洛谷 P1983 - [NOIP2013 普及组] 车站分级

洛谷 P5603 - 小 C 与桌游

洛谷 P3243 - [HNOI2015] 菜肴制作

洛谷 P6286 - [COCI2016-2017#1] Cezar

  • 比较两个字符串字典序大小，我们只需考虑第一个不一样的位置即可。
  • 假设第一个不一样的字符分别为 $s_1$，$s_2$，并且 $s_1$ 所在字符串字典序更小，那么一定有 $a < b$，连边跑拓扑序即可。

洛谷 P3243 - [HNOI2015] 菜肴制作

  • 倒着求字典序最大的拓扑序即可。

练习

最后修改：2024 年 02 月 14 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏