#逆序对 #树上差分 #dp #tarjan #最短路 #spfa #Johnson

[[逆序对]] [[树上差分]] [[dp]] [[tarjan]] [[最短路]] [[spfa]] [[Johnson 全源最短路]]

前言

题目链接

今天早上测试，感觉今天似乎不是很难。

题解

T1

几个01串，排列后求最小逆序对数。

发现影响逆序对的只有相互之间的，然后写一下相邻两个交换的条件就能得到如何排序了。

T2

据说很难想，但是我觉得还是比较好想的，也许是之前有过类似的题目吧。

就是一堆树上的链，选择 K 条路径有公共点的选择数。

比较容易想到差分，进而想到在公共部分最高的地方计算贡献，所以把每条链 lca 的地方标记一下，在 lca 的地方肯定有贡献，然后就容易了。

T3

暴力不是很难，但是第一部分测试点我觉得比较难打。

第二部分暴力想过就是数位 dp 但是后来没打（或许是不想打）。

菊花图容易，链的情况就递推完事，交点数反过来针对不同链交的交点计算出现次数就行，不难发现都是个时种类数个。

正解就是合并子树然后 dp，很神奇，有趣。

T4

最开始觉得这道题很弱，似乎很简单，后来觉得似乎会有地雷，最后发现好像确实不是很难。

题解代码一大堆，还要用 johnson 算法，我用 spfa 乱搞就70分了。

后来被邓老师对拍出了有算法问题，后来仔细检查，发现算法没有问题，是我把打成了（难受）。

正解也不难，就用 tarjan 把强连通分量分开来算就 O 啦。

然后加一个优化，如果一个强连通分量重一个无穷小或者不行，那么整个强连通分量都是这样。

为什么呢？很有趣。

无穷小

首先强连通分量，肯定能回到自己，不管奇偶，还可以经过强连通分量中任意一个点。

其次，有一个点能奇数步负环回到自己。那么上一行的不管奇偶肯定能通过这个负环给它调成奇数的，然后负环。

完成。

不能到达

假设这个分量中有点能有奇环，那么如果这个点走一个经过这个点的环：

• 如果是奇环，那么肯定就不成立。
• 如果是偶环，那么再走一遍这个点的奇环就能变成奇环了，也不成立。

所以假设不成立。所有点都不会有奇环。

十分的巧妙呢。结合上面两种优化，spfa 直接秒了，不需要 Johnson 了。

晚上

做了 dijsktra 的模板测验，3 min 搞定。

准备学习 Johnson 全源最短路算法，用途可以求负权图，还可以让费用流更快。

学习了 Johnson，接下来学习其在费用流中的应用。