某某君，记叙文，带下标大写字母，2e5

· · 算法·理论

0 秒猜出出题人国籍。

偶遇喜茶塞我神秘题单，拼尽全力我靠我不会写。

其实是 JOI 特训。

P5100 [JOI 2017 Final] 足球 / Soccer

人话：我草我概括不动太史了这个题面。

发现某种边权是高贵的一次函数，直接做做不动。

那间接做就做得动了吗，当然不。

考虑球的状态：

然后建三层图，第一层到第二、三层对应踢出去，边权为常数 B，然后第二、三层内部连边权为 A 的边，这样就把那个高贵的一次函数解决了。

第一层内部连边权为 C 的边，表示带球走。第三层向第一层连边权为 C\times k 的边，k 为距离这个位置最近的球员，多源 bfs 板子。

幻视 cxk（）

P11791 [JOI 2017 Final] 准高速电车 / Semiexpress

题目保证了 B<C<A，所以优先走 B，然后 B 将数轴划分为若干块。

对于每一块内，先走 A，然后对于 A 走不到的地方，就从起点到这个位置拉一条 C，接着继续尝试走 A，再拉 C，直到走到块的右端。

考虑一开始不用 C，把每个块只用 A 走的信息扔进优先队列，每次取收益最大的，每做一次跳一次 C，再扔进优先队列，做 K-M 次。

P11792 [JOI 2017 Final] JOIOI 王国 / Kingdom of JOIOI

题目很他吗不说人话啊，题意是：你要把一个网格沿一个非严格楼梯状边界划分成两部分，使两部分各自极差的较大值最小。

首先，答案有一个上界是整个网格的极差，所以考虑把网格的最大值和最小值分在两个不同区域，这样答案不劣于上界。

然后题目能用的只有“楼梯”这个形状了，但是好像不能直接做。考虑二分答案，把“楼梯”用于判合法。

对每个点分类讨论，看看它到底是在最大值那边、最小值那边、两者均可、还是两者均不可。

下面只讨论相对位置是左上右下的情况，其余情况可以旋转做四遍。

对于每一行，维护分隔点的取值范围，大概就是根据上面的分类讨论确定 l,r。然后问题就变成若干变量，每个变量有取值范围，判断是否可以取出一个单调不增序列，这个贪心取最大能取到的值就可以。

P11795 [JOI 2016 Final] 铁路票价 / Train Fare

题面人话：边权都为 1 的无向图，q 次操作，每次把一条边的边权从 1 改成 2（已经改过的不会改），问每次改完后最短路改变的路径条数（包括前面已经处理过的修改的贡献）。

发现把一个边权改成 2 那肯定聪明的不走这条边，相当于删边。

建出最短路图，相当于问删边后有几个点和 1 号点相离。

这个时候可能有人要问，那存不存在情况适当换边使得最短路不变？这是不可能的，根据最短路图的性质，不走在最短路图上的边必不可能得到最短路，此时长度也更新了。

每次删边判断当前点入度是否为 0，如果是，则以它为起点做拓扑排序，删掉相关边，更新哪些点被分出去。

时间复杂度线性。

P7669 [JOI 2018 Final] 月票购买 / Commuter Pass

人话：无向图，问将 S 到 T 最短路上的一段边权置 0 后 U 到 V 的最短路的最小值。

先跑四遍最短路，因为是无向图所以不用建反图了（笑）。

考虑枚举 S 到 T 最短路上的两个点 X,Y，用 d_{U,X}+d_{Y,V} 更新答案，然后这是 O(n^2) 的。

考虑把所有可能在 S 到 T 最短路上的边提出来，建一个图，这个图是最短路图的子图，同时显然可从 S 到 T，因此是 DAG。

在 DAG 上 dp，对于上述平方算法，考虑每个 Y 其计入贡献的必然是能到达其的点中 d_{U,X} 最小的 X，可以直接维护。

然后就做完了。

P7407 [JOI 2021 Final] 机器人 / Robot

人话：你需要改变一些边的颜色，使得存在这样一条路径 a，对于 a_i 到 a_{i+1}，这条边的颜色在与 a_i 相邻的边中唯一，修改每条边的代价不同。

首先这题有个很好的性质，只要决定改边就不用担心改重复，因为颜色有 m 种，而边只有 m 条。

讨论需要改边的情况，对于边 (u,v)，颜色为 c，记 s_{u,c} 为所以与 u 相连的边中颜色为 c 的边权和，两种情况：

但是可能有错，比如说一个长度为 3 的链 x\rightarrow y\rightarrow z，两条边颜色相同，然后在第一条用第一种策略，在第二条用第二种策略，那贡献会多算，因为在第二步时第一条边颜色已经改变了，实际贡献应该是：s_{y,c}-w_{y,z}。

所以考虑对 x\rightarrow z 连边，特殊计算这种情况的贡献，然后你发现复杂度炸了。

然后呢？不会呐。

优化建图的意义是，当题目存在多种情况且我们不能一一列举时，优化建的图上跑最短路会帮助我们自动枚举这些情况。

来考虑一下优化建图，一个经典的优化建图 trick 是：一堆点向另一堆点连边，可以建一个虚点，把两堆点分别向虚点连边，这样的图是等价的。

然后我们枚举中间点 y，对每个 y 建出颜色虚点，再把和 y 相连的点按相应颜色连虚点，连向虚点无需有边权，虚点连出来的边权按上面讨论的连。同时一开始的两条边不需要删掉，因为不优会被最短路自动筛选掉。

P9525 [JOIST 2022] 团队竞技 / Team Contest

牛魔，诈骗题。

三维拆开扔优先队列，然后贪心取队头，如果三个不来自同一个人直接输出答案，如果有两个来自同一个人，则这个人不可能存在于答案中，直接打标记，后续队列弹到是直接跳过。

如果队列空了都找不到就是无解了。