互测第二场

本文主要是介绍互测第二场，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前面好几天没有写题解了，之前的题目很难，没有改完，什么时候改过去了再补上题解吧。

游行

数据范围很网络流,所以考虑网络流。

显然程序中不可能带着 C ,所以向别的方向考虑。

我们可以看成把一条路径看成只有起点不被覆盖的路径,然后未被覆盖的点产生 C 的贡献。

为什么这样是可以的?考虑一条经过环的路,如果要走一遍环然后再从环出去肯定是可以分成走

环和不走环两部分,那么这样的话都花费一个 C ,但是拆开的可以少走一条边,所以更优。

那么我们可以看成在做一个最小路径覆盖,两点之间边权连最短路距离,跑费用流即可。

式子不再推了，考试的时候很容易就推出来了，关键是计算的方式，这个根号分治很妙。

这个就区间逆序对，然后强制在线。

分块之后用个数据结构能过去，一定要用BIT，别的东西会T飞的。

注意尽可能让循环时内存访问连续一些。

这题有不带log的解法，如果不想大力卡常可以看一看。

这篇关于互测第二场的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！