![2023年10月7日模拟赛](/img/20231010231836.jpg)
2023年10月7日模拟赛
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
#逆序对 #树上差分 #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,接下来学习其在费用流中的应用。
- 标题: 2023年10月7日模拟赛
- 作者: 混氏新子
- 创建于 : 2023-10-10 22:52:28
- 更新于 : 2023-10-10 23:19:03
- 链接: https://blog.huasushis.cn/2023/2023年10月7日模拟赛/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。